原点回帰？

よく考えよう。
僕の合宿まであと一年もあるじゃないか。
合宿過去問はゆっくりとけばいい。
だから僕は本選に原点回帰する。

Books

今までにカンニングをさんざんしてきたので、解法を覚えてしまったので、やっぱり一発ACしないとダメですよね。
ローカルでテストしているときgeditの罠にはまっていました

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,k;
vector<int> val[10];
int dp[2001];
int main() {
    scanf("%d%d",&n,&k);
    for (int i=0; i<n; i++) {
        int c, g; scanf("%d%d",&c,&g);
        val[g-1].push_back(c);
    }
    for (int i=0; i<10; i++) {
        sort(val[i].rbegin(),val[i].rend());
        for (int j=1; j<val[i].size(); j++) {
            val[i][j]+=val[i][j-1]+j*2;
        }
    }
    for (int i=0; i<10; i++) {
        if (val[i].size()!=0) {
            for (int j=k; j>0; j--) {
                for (int l=1; l<=min(j,(int)val[i].size()); l++) {
                    dp[j]=max(dp[j], dp[j-l]+val[i][l-1]);
                }
            }
        }
    }
    printf("%d\n",dp[k]);
}

1172

Twitterでつぶやかれていたので見てみたら簡単な素数問題だったから解いた

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
bool isprime[1000001];
vector<int> prime;
int main() {
    fill(isprime, isprime+1000001, true);
    isprime[0]=isprime[1]=false;
    for (int i=2; i<1000001; i++) {
        if (isprime[i]) {
            prime.push_back(i);
            for (int j=i+i; j<1000001; j+=i) isprime[j]=false;
        }
    }
    int n;
    while (scanf("%d",&n)) {
        if (!n) break;
        printf("%d\n",upper_bound(prime.begin(),prime.end(),2*n)-upper_bound(prime.begin(),prime.end(),n));
    }
}