IOI TC Oddsort Solution

#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
int main(){
    int n,a[5001],dp[5001],sum=0,ma;
    n=scan();
    for(int i=0;i<n;a[i++]=scan(),sum+=a[i-1]);
    for(int i=0;i<n;i++){
        dp[i]=a[i];
        for(int j=0;j<i;j++){
            if(a[i]>=a[j]){
                dp[i]=max(dp[j]+a[i],dp[i]);
            }
        }
        ma=max(ma,dp[i]);
    }
    printf("%d",sum-ma);
}

INOI 2013 Calvins Game solution.

#include<bits/stdc++.h>
using namespace std;
#define s(x) scanf("%lld",&x)
int n;
long long a[1000001]={0};
long long dp[1000001][2];
#define mini INT_MIN
long long rec(int i,bool phase){
    if(dp[i][phase]==-1){
    long long x,y,p=-mini,q=-mini;
    if(i>2){
        x=rec(i-1,0)+a[i-1];
        y=rec(i-2,0)+a[i-2];
    }
    else if(i>1){
        x=rec(i-1,0)+a[i-1];
        y=-mini;
    }
    else{
         x=0;
         y=0;
    }
    if(phase){
        if(i<n-1){
            p=rec(i+1,1)+a[i+1];
            q=rec(i+2,1)+a[i+2];
        }
        else if(i<n){
            p=rec(i+1,1)+a[i+1];
        }
    }
    dp[i][phase]= max(max(p,q),max(x,y));
    }
    return dp[i][phase];
   
}
int main(){
    int k;
    s(n);
    s(k);
    for(int i=1;i<=n;i++){
        s(a[i]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld",rec(k,1));
}

INOI Sequence Land solution

#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
int main(){
    int n=scan();
    int k=scan();
    vector<int> a[301];//which person has ith id
    vector<int> arr[301];//ids the ith person has
    for(int i=1;i<=n;i++){
        int id=scan();
        while(id--){
            int x=scan();
            arr[i].push_back(x);//ith person has the id (x)
            a[x].push_back(i);//x id is with ith person
        }
    }//makin the graph O(n^3)
    vector<int> v[301];
    for(int i=1;i<=n;i++){//ith person
        int temp[301]={0};//number of ids common between the ith person and others
        int x=arr[i].size();
        for(int j=0;j<x;j++){
            int id = arr[i][j];
            int y=a[id].size();
            for(int l=0;l<y;l++){
                int person = a[id][l];
                temp[person]++;
                if(temp[person]>=k){
                    v[i].push_back(person);
                }
            }
        }
    }
    //bfs;
    queue<int> q;
    bool visited[301]={0};
    int ans=0;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(!visited[u]){
            ans++;
        }
        visited[u]=1;
        int x=v[u].size();
        for(int i=0;i<x;i++){
            int node = v[u][i];
            if(!visited[node]){
                q.push(node);
            }
        }
    }
    cout<<ans;
}