akhauriyash/Code-Regression huggingface dataset:
/// Zhupengfei 2018
/// Hereby declare: this program is in public domain.

/// Solution for problem: ARC070D

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>

using namespace std;

#pragma pack(1)
struct data{
	int value0, value1, value2;
};
#pragma pack()

int dp_cache[5001][5001]= {};
int a[5001]= {};
vector<data> use[5001]= {};
vector<int> use2[5001]={};
bool v[5001][5001]= {};
bool tmpv[5001] ={}; 
int parsev[5001] ={};
int parsev2[5001] ={};

int n, K;

__attribute__((optimize("-O3")))
int dp(int i, int k) {
    if(i==0) return 0;
    int &cache = dp_cache[i][k];
    if(cache!=-1) return cache;
    
    int ans=dp(i-1, k);
	
    
    if(k>a[i]) {
        int xx = dp(i-1, k-a[i]);
        if(xx>0){
	        ans+=xx;
			use[k].push_back({k-a[i], use[k-a[i]].size()-1, use2[k-a[i]].size()-1});
            use2[k].push_back(i);
        	if(a[i]>=k) {
        		ans++;
        		return cache=ans;
			}
    	}
    } 
	if(a[i]>=k) {
        ans++;
        use2[k].push_back(i);
    }

    return cache=ans;
}

void parse(int k, int r1, int r2) {
	//cout<<"parsing "<<k<<", "<<r<<endl;
	int l = max(0, parsev[k]+1);
	for(int i=l;i<=r1;i++){
		const auto& x=use[k][i];
			parse(x.value0, x.value1, x.value2);
	}
	parsev[k]=max(parsev[k], r1);
	int l2 = max(0, parsev2[k]+1);
	for(int i=l2;i<=r2;i++){
		tmpv[use2[k][i]]=1;
	}
	parsev2[k]=max(parsev2[k], r2);
}

int ans=0;

__attribute__((optimize("-O3")))
int main() {
	//freopen("1_010.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>K;
    long long sum=0;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        sum+=a[i];
    }
    sort(a+1, a+n+1);
    for(int i=0; i<=n; i++)
        for(int j=0; j<=K; j++)
            dp_cache[i][j]=-1;
           
    if(n==1) {
        if(a[1]>=K) cout<<0<<endl;
        else cout<<1<<endl;
        return 0;
    }
    if(sum<K) {
        cout<<n<<endl;
        return 0;
    }
    if(sum==K) {
        cout<<0<<endl;
        return 0;
    }
    if(sum<K) {
        cout<<n<<endl;
        return 0;
    }
	dp(n, K);
	for(int i=0;i<=K;i++) parsev[i]=parsev2[i]=-1; 
	parse(K, use[K].size()-1, use2[K].size()-1);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(!tmpv[i]) {
			ans++;
		}
	}
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 220160
#include <bits/stdc++.h>
using namespace std;

void solve(long long N, std::string S, std::string T)
{
    for (size_t i = 0; i < N; i++)
    {
        cout << S[i] << T[i];
    }
    cout << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    solve(N, S, T);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  cin >>H>>W;
  vector<char> vec(W+2);
  for(int i=0;i<W+2;i++){
    vec.at(i)='#';
  }
   for(int i=0;i<W+2;i++){
  cout << vec.at(i);
  }
  cout <<endl;
  /*ここまでで一段目の＃を出力*/

 for(int k=0;k<H;k++){
  vector<char> vect(W+2);
    vect.at(0)='#';
    vect.at(W+1)='#';
  for(int i=1;i<W+1;i++){
    cin >>vect.at(i);
  }
    for(int i=0;i<W+2;i++){
      cout <<vect.at(i);
  }
   cout <<endl;
  
}
  /*ここから最後の談の＃を出力する*/
 for(int i=0;i<W+2;i++){
   cout <<vec.at(i);
 }
  cout <<endl;
  
}

Measured memory_bytes: 256
using System;

namespace ABC059_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var a = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            var ans1 = 0L;
            var ans2 = 0L;
            var sum1 = 0L;
            var sum2 = 0L;
            for (var i=0;i<n;i++)
            {
                sum1 += a[i];
                if(i%2 == 0)
                {
                    if(sum1<=0)
                    {
                        ans1 += Math.Abs(sum1) + 1;
                        sum1 = 1;
                    }
                }
                else
                {
                    if(sum1>=0)
                    {
                        ans1 += sum1 + 1;
                        sum1 = -1;
                    }
                }
            }
            for(var i=0;i<n;i++)
            {
                sum2 += a[i];
                if (i % 2 == 0)
                {
                    if (sum2 >= 0)
                    {
                        ans2 += sum2 + 1;
                        sum2 = -1;
                    }
                }
                else
                {
                    if (sum2 <= 0)
                    {
                        ans2 += Math.Abs(sum2) + 1;
                        sum2 = 1;
                    }
                }
            }
            var ans = Math.Min(ans1, ans2);
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 29276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
typedef pair<ll,pii> ipii;
#define MOD 1000000007
#define mod(a) ((a)%MOD)
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define dbg(x) cerr<<#x<<" = "<<x<<"\n"
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<"\n"
#define dbg3(x,y,z) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<" , "<<#z<<" = "<<z<<"\n"
#define INF (1LL<<60)
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;*/
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(),v.end()
#define endl '\n'
ll gcd(ll a,ll b){if(a==0) return b; return gcd(b%a,a);}
ll powm(ll base,ll exp,ll mod=MOD) {base%=mod;ll ans=1;while(exp){if(exp&1LL) ans=(ans*base)%mod;exp>>=1LL,base=(base*base)%mod;}return ans;}
 
 


struct matrix{
     int sz;
     ll **arr;

     matrix(int sz){
          this->sz=sz;
          arr = new ll*[sz];
          for(int j=0;j<sz;j++) arr[j] = new ll[sz];
          
     }

      void iden(){
           for(int i=0;i<sz;i++)
              for(int j=0;j<sz;j++)
                   arr[i][j] = (i==j);
      } 
 
      matrix operator*(const matrix &b){
           matrix c(sz);
           for(int i=0;i<sz;i++){
               for(int j=0;j<sz;j++){
                     for(int k=0;k<sz;k++)
                      c.arr[i][j] = mod(c.arr[i][j]+mod(arr[i][k]*b.arr[k][j]) );
               }
           }

             return c;
      }

      matrix operator+(const matrix &b){
           matrix c(sz);
           for(int i=0;i<sz;i++)
                for(int j=0;j<sz;j++) c.arr[i][j]=mod(arr[i][j]+b.arr[i][j]);
           return c;
      }

};



matrix fastexpo(matrix &a,ll p){
         matrix c(a.sz);
         c.iden();
         while(p){
              if(p&1){
                  c=a*c;
                  p--;
              }
              a=a*a;
              p/=2;
         }
           return c;
}



int main(){
      sync;
      ll n,k;
      cin>>n>>k;
      matrix m(n);
      for(ll i=0; i<n; i++){
          for(ll j=0; j<n; j++){
                 cin>>m.arr[i][j];              
           }            
      }
 
     
     matrix r = fastexpo(m,k);
     ll ans=0;
     for(int i=0;i<n;i++){
         for(int j=0;j<n;j++) ans=mod(ans+r.arr[i][j]);
     }

             cout<<ans<<endl;

}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i< (n);i++)
using namespace std;
typedef long long ll;

int main(){
    ll N,M;cin>>N>>M;
    vector<ll> cards(N,0);
    rep(i,N)cin>>cards[i];
    vector<pair<ll,ll>> A;
    rep(i,M){
        ll B,C;cin>>B>>C;
        A.push_back(make_pair(C,B));
    }
    sort(cards.begin(),cards.end());
    sort(A.begin(),A.end());
    auto it_A = A.end()-1;
    auto it_cards = cards.begin();
    while(!A.empty() && it_cards != cards.end()){
        bool flg = 0;
        for(ll i=0;i<(*it_A).second;i++){
            if(*it_cards > (*it_A).first){
                flg = 1;
                break;
            }else{
                *it_cards = (*it_A).first;
                it_cards++;
            }
        }
        it_A--;A.pop_back();
        if(flg == 1)break;
    }
    ll ans = 0;
    for(ll i=0;i<cards.size();i++){
        ans += cards[i];
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define F(i,s,e) for(int i=s;i<e;++i)

int main(){
    int a,b;
    char ch;
    cin >> a >> ch >> b;
    if(ch=='+') cout << a+b << endl;
    else if(ch=='-') cout << a-b << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}
//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

int main(){
    ll x;
    cin >> x;

    for(int i=-119;i<118;i++){
        for(int j=-119;j<=119;j++){
            if(pow(i,5)-pow(j,5)==x){
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 4056
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define int long long
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int,int>
#define INF 100000000000000000
#define EPS 1e-9

int32_t main()
{
    int n;
    cin>>n;
    int arr[n];
    int sum = 0;
    map<int, vector<int> > mp;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
        mp[sum].pb(i);
        //cout<<sum<<" ";
    }
   // cout<<"\n";
    int pref = 0;
    int ans = 0;
    for(int i=0;i<n;i++)
    {
       //cout<<i<<" "<<pref<<" "<<mp[pref].size()-(int)(lower_bound(mp[pref].begin(),mp[pref].end(),i) - mp[pref].begin())<<"\n";
        ans += mp[pref].size()-(int)(lower_bound(mp[pref].begin(),mp[pref].end(),i) - mp[pref].begin());
        //mp[pref].pop_back();
        pref += arr[i];
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 23680
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mod = 1000000007;
int n, m;
vector<vector<int> > vi;
int visited[100007];
int dp[100007];
int dfs(int start){
    if(vi[start].size() == 0){
        return 1;
    }
    if(dp[start] > 0) return dp[start];
    int mx = 1;
    for(auto j:vi[start]){
        if(!visited[j]){
            visited[j] = 1;
            int l = 0;
            l = dfs(j);
            mx = max(mx, l);
        }
        else mx = max(mx, dp[j]);
    }
    
    return dp[start] = mx+ 1;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    int a, b;
    //visited.assign(n+1, false);
    memset(visited, 0, sizeof(visited));
    memset(dp, -1, sizeof(dp));
    vi.resize(n+1);
    for(int j=0; j<m; j++){
        cin >> a >> b;
        --a; --b;
        vi[a].push_back(b);
    }
    int mx = -1;
    //cout<<"mx="<<mx<<endl;
    for(int i=0; i<n; i++){
        int h = 0;
        //cout << i << " " << vi[i].size() << endl;
        if(!visited[i]){
            h = dfs(i);
            //cout << h << " : " << i << endl;
            mx = max(mx, h);
        }
    }
    cout << mx-1 << endl;
}

Measured memory_bytes: 8576
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

//n以下の素数列
void LF_Prime_Sequence(const long &n, vector<long> &viPrime){
    if(n < 2){
        return;
    }
    viPrime.clear();
    vector<char> aiType(n + 1,0);
    for (long i = 2; i * i <= n; i++){
        for(long j = 2; j * i <= n; j++){
            aiType[j * i] = 1;
        }
    }
    for (long i = 2; i <= n; i++){
        if(aiType[i] == 0){
            viPrime.push_back(i);
        }
    }
    return;
}

int main(){
    long n;
    scanf("%ld", &n);
    vector<long> viPrime;
    LF_Prime_Sequence(n/2, viPrime);
    long nCountTwo=0,nCountFour=0,nCountFourteen=0,nCountTwentyfour=0,nCountSeventyfour=0;
    for(int i=0; i<viPrime.size();i++){
        
        long k = viPrime[i];
        long nCountk = 0;
        long nTmp = n;
        while(nTmp >= k){
            nTmp /= k;
            nCountk += nTmp;
        }
        if(nCountk >= 2){
            nCountTwo++;
        }
        if(nCountk >= 4){
            nCountFour++;
        }
        if(nCountk >= 14){
            nCountFourteen++;
        }
        if(nCountk >= 24){
            nCountTwentyfour++;
        }
        if(nCountk >= 74){
            nCountSeventyfour++;
        }
    }
    long nAns = 0;
    nAns += nCountSeventyfour;
    nAns += nCountTwentyfour * (nCountTwo - 1);
    nAns += nCountFourteen * (nCountFour - 1);
    nAns += nCountFour * (nCountFour - 1) * (nCountTwo - 2) / 2;
  
    printf("%ld\n", nAns);
    return 0;
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>wq1,wq2;
int main()
{
    int g,h,t,z,lo2,hi2,m2;
    ll q,x,sp,lo1,hi1,m1,ntz=0;
    scanf("%d %lld",&t,&q);
    for(g=0;g<t;g++){
        scanf("%d",&z);
        if(z>0)wq1.push_back(z);
        else if(z<0)wq2.push_back(z);
        else ntz++;
    }
    sort(wq1.begin(),wq1.end());
    sort(wq2.begin(),wq2.end());
    lo1=-1e18, hi1=1e18;
    while(lo1<hi1){
        m1=(lo1+hi1)>>1;
        if(m1<0)for(g=sp=0;g<wq2.size();g++){
            lo2=0, hi2=wq1.size()-1;
            while(lo2<=hi2){
                m2=(lo2+hi2)>>1;
                x=1LL*wq2[g]*wq1[m2];
                if(x<=m1)hi2=m2-1;
                else lo2=m2+1;
            }
            sp+=(wq1.size()-hi2-1);
        }
        else if(m1>0){
            sp=1LL*wq2.size()*wq1.size();
            sp+=ntz*(wq1.size()+wq2.size());
            sp+=(ntz*(ntz-1))>>1;
            for(lo2=0,hi2=wq1.size()-1;lo2<hi2;lo2++){
                while(lo2<hi2&&1LL*wq1[lo2]*wq1[hi2]>m1) hi2--;
                sp+=hi2-lo2;
            }
            for(lo2=0,hi2=wq2.size()-1;lo2<hi2;hi2--){
                while(lo2<hi2&&1LL*wq2[lo2]*wq2[hi2]>m1) lo2++;
                sp+=hi2-lo2;
            }
        }
        else{
            sp=1LL*wq2.size()*wq1.size();
            sp+=ntz*(wq1.size()+wq2.size());
            sp+=(ntz*(ntz-1))>>1;
        }
        if(sp>=q)hi1=m1;
        else lo1=m1+1;
    }
    printf("%lld\n",hi1);
    return 0;
}


Measured memory_bytes: 4308
//
// Created by Hideaki Imamura on 2020-03-07.
//
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair <ll, ll> l_l;
typedef pair<int, int> i_i;

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

# define EPS (1e-7)
# define INF (1e9)
# define PI (acos(-1))
//const ll mod = 1000000007;

int N, P;
string S;

int main() {
    cin >> N >> P >> S;
    ll ans = 0;
    if (P == 2 || P == 5) {
        for (int i = 0; i < N; ++i) {
            if ((S[i] - '0') % P == 0) ans += i + 1;
        }
    } else {
        map<int, int> mp;
        int idx = 0;
        mp[idx]++;
        ll U = 1;
        for (int i = N-1; i >= 0; --i) {
            idx = (idx + (S[i] - '0') * U) % P;
            ans += mp[idx];
            mp[idx]++;
            U = U * 10 % P;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 900
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> v[100001];
queue<int> q;
int n,m,x,y,tmp,in[100001],dp[100001],ans;

int main()
{Tie
	cin>>n>>m;
	for(int i=0;i<m;i++)
		cin>>x>>y,v[x].pb(y),in[y]++;
	for(int i=1;i<=n;i++)
		if(!in[i])
			q.push(i);
	while(!q.empty())
	{
		tmp=q.front(),q.pop();
		ans=max(ans,dp[tmp]);
		for(int i:v[tmp])
		{
			dp[i]=max(dp[i],dp[tmp]+1),in[i]--;
			if(!in[i])
				q.push(i);
		}
	}
	cout << ans<<'\n';
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,a;
	cin>>n;
	vector<int>v(n+1);
	for(int i=0;i<n;i++){
		cin>>a;
		v[i]=a;
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		if(v[v[i]-1]==i+1){;
		cnt++;
		}
	}
	cout<<cnt/2<<endl;
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
//#define double long double
const int maxn=2e5+10;
const int mod=998244353;
double dis[1005];
vector<pair<int,double>>E[1005];

struct ac
{
    double x,y,r;
};
ac a[1005];




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    double sx,sy,ex,ey;
    cin>>sx>>sy>>ex>>ey;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
       cin>>a[i].x>>a[i].y>>a[i].r;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            double temp=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
            temp-=a[i].r+a[j].r;
            if(temp<0)
                temp=0;
            E[i].pb({j,temp});
            E[j].pb({i,temp});
        }
    }
    double t=sqrt((sx-ex)*(sx-ex)+(sy-ey)*(sy-ey));
    E[0].pb({n+1,t});
    E[n+1].pb({0,t});
    //dis[n+1]=t;
    for(int i=1;i<=n;i++)
    {
        double temp=sqrt((sx-a[i].x)*(sx-a[i].x)+(sy-a[i].y)*(sy-a[i].y));
        double temp2=sqrt((ex-a[i].x)*(ex-a[i].x)+(ey-a[i].y)*(ey-a[i].y));
        temp-=a[i].r;
        temp2-=a[i].r;
        if(temp<0)
            temp=0;
        if(temp2<0)
            temp2=0;
        E[i].pb({0,temp});
        E[0].pb({i,temp});
        E[n+1].pb({i,temp2});
        E[i].pb({n+1,temp2});

    }
    priority_queue<pair<double,int>>q;
    for(int i=1;i<=n+1;i++)
    {
        dis[i]=1e10;
    }
    dis[0]=0;
    q.push({0,0});
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        //cout<<"here"<<'\n';
        for(auto &v:E[u])
        {
            if(dis[v.first]>dis[u]+v.second)
            {
                dis[v.first]=dis[u]+v.second;
                q.push({-dis[v.first],v.first});
            }
        }
    }
    cout<<fixed<<setprecision(10)<<dis[n+1]<<'\n';



}


Measured memory_bytes: 23836
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  long long o = 0;
  int r[2019], k = 1, p, n = s.length();
  memset(r, 0, sizeof(int) * 2019);
  r[0]++, r[p = s[n - 1] - '0']++;
  for(int i = n - 2; i >= 0; i--)
    r[p = (p + (s[i] - '0') * (k = k * 10 % 2019)) % 2019]++;
  for(int i = 0; i < 2019; i++)
    if(r[i] > 1) o += r[i] * (r[i] - 1) / 2;
  printf("%lld\n", o);
}

Measured memory_bytes: 3796
n=int(input())
a=list(map(int,input().split()))

f=''
ans=1
for i in range(1,n):
    if a[i-1]==a[i]:
        continue
    if a[i-1] < a[i]:
        if f=='>':
            ans+=1
            f=''
        else:
            f='<'
    else:
        if f=='<':
            ans+=1
            f=''
        else:
            f='>'
print(ans)


Measured memory_bytes: 14252
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define light ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ll long long
#define ld long double
#define endl "\n"
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i,a,b) for(ll i = a; i < b; i++)
#define REPE(i,a,b) for(ll i = a; i <= b; i++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b) / gcd(a, b)
#define bins(v, x) binary_search(v.begin(), v.end(), x)
const double pi = 2*acos(0.0);
const int INF = 1e9+1;
const int mod = 1e9+7;
const int mod1 = 998244353;
 
ll modExp(ll base, ll exp, ll mod) {
   ll res = 1;
   while (exp > 0) {
    	if (exp % 2 == 1) {
        	res= (res * base) % mod;
		}
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}

ll inverse(ll base, ll exp, ll mod) {
   return modExp(base, exp - 2, mod);
}

bool compare(const pair<int, int>&i, const pair<int, int>&j) {
   return (i.S > j.S || (i.S == j.S && i.F > j.F));
}

void test() {
   int n;
   cin >> n;
   if(n % 1000 == 0) cout << 0;
   else {
      int x = n/1000 + 1;
      cout << 1000*x-n;
   }
}

int main() {
   //freopen("input.txt","r",stdin);
   //freopen("output.txt","w",stdout);
   light;
   cout.precision(15);
   cout << fixed;

   int t = 1;
   //cin >> t;
   while(t--) {
      test();
   }
   return 0;
}


Measured memory_bytes: 3636
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<Integer>[] a = new ArrayList[n];
		for(int i=0; i<n; i++){
			a[i] = new ArrayList<Integer>();	
		}
		for(int i=0; i<m; i++){
			int ta = sc.nextInt() - 1;
			int tb = sc.nextInt() - 1;
			a[ta].add(tb);
			a[tb].add(ta);
		}
		sc.close();
		
		int nume = 1, numo = 0;
		boolean[] use = new boolean[n];
		boolean[] odd = new boolean[n];
		boolean[] even = new boolean[n];
		ArrayDeque<Integer[]> que = new ArrayDeque<Integer[]>();
		que.add(new Integer[]{0, 0});
		even[0] = true;
		while(!que.isEmpty()){
			Integer[] cur = que.poll();
			for(int i=0; i<a[cur[0]].size(); i++){
				Integer next = a[cur[0]].get(i);
				if(cur[1] == 0 && !odd[next]){
					que.add(new Integer[]{next, 1});
					numo++;
					odd[next] = true;
				}else if(cur[1] == 1 && !even[next]){
					que.add(new Integer[]{next, 0});
					nume++;
					even[next] = true;
				}
			}
		}

		boolean loop = false;
		for(int i=0; i<n; i++){
			if(odd[i] && even[i]) loop = true;
		}
		if(loop){
			System.out.println((long)(n-1)*(long)n/2 - m);
		}else{
			long ans = 0;			
			for(int i=0; i<n; i++){
				if(odd[i]){
					ans += nume - a[i].size();
				}else{
					ans += numo - a[i].size();
				}
			}
			System.out.println(ans / 2);
		}
	}
}


Measured memory_bytes: 103576
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
using lint = long long;

int sgn(int n) { return n ? 1 : -1; }

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	struct para { 
		lint x, y, z; 
		para() :x(0), y(0), z(0) {};
		para operator += (const para &rhs) { x += rhs.x, y += rhs.y, z += rhs.z; return *this; }
		lint pabs() { return abs(x) + abs(y) + abs(z); };
	};
	vector<para> cake(N);
	for (int i = 0; i < N; i++) cin >> cake[i].x >> cake[i].y >> cake[i].z;

	lint ans = 0;

	for (int bit = 0b0; bit < 8; bit++) {
		para sum;
		sort(cake.begin(), cake.end(), [&](para a, para b) { 
			return sgn(bit&4)*a.x + sgn(bit&2)*a.y + sgn(bit&1)*a.z > sgn(bit&4)*b.x + sgn(bit&2)*b.y + sgn(bit&1)*b.z;
		});
		for (int i = 0; i < M; i++) { sum += cake[i]; }
		ans = max(ans, sum.pabs());
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

int N,M,H,W,K,A,B;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

const int MOD = 1000000007;


int main() {
    cin>>N>>M;
    mat dp(N,vec(M,0));
    vector<string> grid(N);
    rep(i,N) cin>>grid.at(i);
    dp.at(0).at(0) = 1;
    rep(i,N){
        rep(j,M){
            if(i == 0 && j == 0)continue;
            ll &ndp = dp.at(i).at(j);
            if(i > 0) (ndp+=dp.at(i-1).at(j))%=MOD;
            if(j > 0) (ndp+=dp.at(i).at(j-1))%=MOD;
            if(grid.at(i).at(j) == '#') ndp = 0;  
        }
    }
    /*rep(i,N){
        rep(j,M){
            cout<<dp.at(i).at(j)<<' ';
        }
        cout<<endl;
    }*/
    cout<<dp[N-1][M-1]<<endl;
}

Measured memory_bytes: 9216
#include <iostream>

char ch;
int n;
int cnt;

int main() {
std::cin>>n;
for(int i=0;i<n;++i){
std::cin>>ch;
if(ch=='R') ++cnt;
}
if(cnt>n-cnt) std::cout<<"Yes"<<std::endl;
else std::cout<<"No"<<std::endl;
return 0;
}

Measured memory_bytes: 256
import collections
n = int(input())

arr = map(int,raw_input().split())
l = len(arr)
counter = collections.Counter(arr)

c = 0

for item in counter.items() :
	if item[1] > 2:
		if item[1] % 2 == 1 :
			l -= item[1] - 1

		else:
			l -= item[1] - 2

	if item[1] % 2 == 0 :
		c += 1

if c % 2 == 0:
	l -= c

else :
	l -= c+1

print l


Measured memory_bytes: 20284
def main(N=None, K=None):
    if not N:
        N, K = map(int, input().split())
    ans = (K-N-2)*(2*K*K-K*(N+2)-N*N-N-6)//6
    ans %= 10**9+7
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 10
    # assert main(200000, 200001) == 1
    # assert main(141421, 35623) == 220280457
    main()


Measured memory_bytes: 9080
#include <stdio.h>
int main(void){
    // Your code here!
    char n[8];
    scanf("%s",n);
   int lsee=0;
   
    int i,j;
   
    for(i=0;i<4;i++){
        for (j=0;j<4;j++){
        
            if(n[i]==n[j]){
                lsee++;
                
            }
            //printf("%d\n",lsee);
           
            
        }
        
        
    }
    if(lsee==8){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return (0);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
            #include<iostream>
            #include<cstdio>
            #include<vector>
            #include<queue>
            #include<map>
            #include<cstring>
            #include<string>
            #include <math.h>
            #include<algorithm>
        //    #include <boost/multiprecision/cpp_int.hpp>
            #include<functional>
 //    #define int long long
            #define mod  1000000007
            #define pa pair<int,int>
            #define ll long long
            #define pal pair<double,int>
            #define ppa pair<int,pa>
            #define ssa pair<string,int>
            #define  mp make_pair
            #define  pb push_back
            #define EPS (1e-10)
            #define equals(a,b) (fabs((a)-(b))<EPS)
     
            using namespace std;
     //priority_queue<int, vector<int>, greater<int> > que;
            class Point{
            	public:
            	double x,y;
            	Point(double x=0,double y=0):x(x),y(y) {}
            	Point operator + (Point p) {return Point(x+p.x,y+p.y);}
            	Point operator - (Point p) {return Point(x-p.x,y-p.y);}
            	Point operator * (double a) {return Point(x*a,y*a);}
            	Point operator / (double a) {return Point(x/a,y/a);}
            	double absv() {return sqrt(norm());}
            	double norm() {return x*x+y*y;}
            	bool operator < (const Point &p) const{
            		return x != p.x ? x<p.x: y<p.y;
            	}
            	bool operator == (const Point &p) const{
            		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
            	}
            };
            typedef Point Vector;
     
            struct Segment{
            Point p1,p2;
            };
     
        double hen(Vector a){
        if(fabs(a.x)<EPS && a.y>0) return acos(0);
        else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0);
        else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0);
        else if(fabs(a.y)<EPS && a.x>0) return 0.0;
        else if(a.y>0) return acos(a.x/a.absv());
        else return 2*acos(0)+acos(-a.x/a.absv());
     
        }
     
string itos( int i ) {
ostringstream s ;
s << i ;
return s.str() ;
}

int gcd(int v,int b){
	if(v>b) return gcd(b,v);
	if(v==b) return b;
	if(b%v==0) return v;
	return gcd(v,b%v);
}
            double dot(Vector a,Vector b){
            	return a.x*b.x+a.y*b.y;
            }
            double cross(Vector a,Vector b){
            	return a.x*b.y-a.y*b.x;
            }
        
double distans(double x1,double y1,double x2,double y2){
	double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	return sqrt(rr);
	
}
 /*
int beki(int a, int r){
	if(r==0)return 1;
	if(r==1) return a%mod; 
	if(r%2==1){
		int y=beki(a,r-1);
		return(y*a)%mod;
		
	}
	int yy=beki(a,r/2);
	return (yy*yy)%mod;
}
 */
 int inf=mod*2;
            //----------------kokomade tenpure------------

int n,k;
int a[1010][105][105]={0};
int b[1010][3];
    signed  main(){
string s;
    	cin>>s;
    	for(int i=0;i<s.length();i++){
    		if(s[i]==',') s[i]=' ';
    	}
    	cout<<s<<endl;
    	return 0;
    }
    //printf("%d %.10f %.10f\n",i,xx/ri,yy/ri);

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main() {
    int n,s=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        for(int i=x;i<=y;i++)
        a[i]=1;
    }
    for(int i=1;i<=100000;i++)
    if(a[i]==1)++s;
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <cmath>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <cstdio>
#include <cctype>
#include <queue>
#include <complex>
#include <climits>

typedef long long ll;

using namespace std;

ll gcd(ll a, ll b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

ll lcm(ll a, ll b){
	return a*b/gcd(a, b);
}

int main(){
	ll a, b;
	while(cin >> a >> b){
		cout << gcd(a, b) << " " << lcm(a, b) << endl;
	}

    return 0;
}

Measured memory_bytes: 1156
from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())

D = {chr(ord('a') + i): [] for i in range(26)}

for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue

        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x

    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)

            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)

            if ri - li > 0:
                ans += 1

        print(ans)


Measured memory_bytes: 100480
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll n; cin >> n;
    vector<ll> x(n);
    rep(i, n) cin >> x[i];
    vector<ll> y(x.begin(), x.end());
    sort(all(y));
    ll cand1 = y[y.size()/2-1], cand2 = y[y.size()/2];
    if (cand1 == cand2) {
        rep(i, n) cout << cand1 << endl;
        return 0;
    }
    ll isok1 = (count(all(y), cand1) > 1), isok2 = (count(all(y), cand2) > 1);
    rep(i, n) {
        ll num = x[i];
        if (num <= cand1) {
            cout << cand2 << endl;
        } else if (cand2 <= num) {
            cout << cand1 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    string S;
    cin >> S;
    string ans;
    if(S=="ABC"){
        ans = "ARC";
    }else{
        ans = "ABC";
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, m; cin >> n >> m;
  vector<vector<pair<int, int>>> adj(n);
  for (int i = 0; i < m; ++i) {
    int a, b, c; cin >> a >> b >> c; --a, --b;
    adj[a].emplace_back(b, c);
  }
  for (int i = 0; i < n - 1; ++i) {
    adj[i + 1].emplace_back(i, 0);
  }
  const long long INF = (long long)1e18L;
  vector<long long> dist(n, INF);
  priority_queue<pair<long long, int>, 
    vector<pair<long long, int>>,
      greater<pair<long long, int>>> pq;
  pq.emplace(0, 0);
  dist[0] = 0;
  while (!pq.empty()) {
    int node; long long cost; tie(cost, node) = pq.top(); pq.pop();
    if (dist[node] < cost) continue;
    if (node == n - 1) {
      cout << cost << endl;
      return 0;
    }
    for (auto &p : adj[node]) {
      int x, c; tie(x, c) = p;
      if (cost + c < dist[x]) {
        dist[x] = cost + c;
        pq.emplace(dist[x], x);
      }
    }
  }
  cout << "-1\n";

  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Measured memory_bytes: 7932
#include <iostream>
#include <cstdio>
#include<list>
#include<iomanip>
#include<cmath>
#include <random>
#include<queue>
#include <functional>
#include<stdio.h>
#include<assert.h>
#include<stack>
#include<sstream>
#include <cstdlib>
#include<map>
#include<algorithm>
#include<iostream>
#include<set>
#include<utility>
#include<memory.h>
#include<string>
#include<vector>
#include <unordered_map>
#include<numeric>
using namespace std;
#define ios std::ios_base::sync_with_stdio(false);
#define ll  long long
#define pb push_back
#define fi(ss) freopen (ss,"r",stdin)
#define fo(ss) freopen (ss,"w",stdout)
#define sz(v)               ((int)((v).size()))
#define all(x)          (x).begin(),(x).end()
#define REP(i, v)       for(int i=0;i<sz(v);i++)
#define ld long double
#define lp(i,n) for(int i = 0 ; i < n ; ++i)
typedef pair<double,double> pii;
typedef pair<pii,int> tri;
using namespace std;

int main() {
	ios
	int n; cin >> n;
	vector<int> v(n);
	int x = -1;
	for (int i = 0 ; i < n ; ++i) {
		cin >> v[i];
	}
	int ans = 0;
	for (int i = 1 ; i < n ; ++i) {
		if (v[i] == v[i - 1]) {
			v[i] = x;
			ans++;
		}
	}
	cout << ans << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

void solve(int H,int W,int D,vvi& a, int Q,vi& l,vi& r) {
    vector<ii> loc(H*W+1);
    rep(r,H) rep(c,W) {
        int x = a[r][c];
        loc[x] = ii(r,c);
    }
    vi d_(H*W+1, 0);
    for (int i=1; i<=H*W-D; ++i) {
        d_[i] = abs(loc[i].first - loc[i+D].first) + abs(loc[i].second - loc[i+D].second);
    }
    vector<ll> da(H*W+1+D, 0);
    for (int b=0; b<D; ++b) {
        for (int i=b; i<=H*W-D; i+=D) {
            da[i+D] = da[i] + d_[i];
        }
    }

    rep(i,Q){ // 1e5
        // int score = 0;
        // for (int x=l[i]; x!=r[i]; x+=D) { // can be 9e4
        //     // x -> x+D
        //     score += d_[x];
        // }
        ll score = da[r[i]] - da[l[i]];
        cout << score << endl;
    }

}

int main() {
    int H,W,D; cin >>H>>W>>D;
    vvi a(H, vi(W));
    rep(h,H) rep(w,W) cin >> a[h][w];
    int Q; cin >>Q;
    vi l(Q), r(Q);
    rep(i,Q) cin >> l[i] >> r[i];
    solve(H,W,D,a, Q,l,r);
    return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,s,n) for(int i = s; i < n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using Graph = vector<vector<int>>;
const int INF = 1000000007;
int main(){
  ll n,x,t;
  cin >> n >> x >> t;
  if(n % x == 0)cout << n / x * t << endl;
  else cout << n / x * t + t << endl;
  return 0;
}


Measured memory_bytes: 3612
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int c1 = in.nextInt();
			int c2 = in.nextInt();
			int c3 = in.nextInt();
			int p = 20 - (c1 + c2);
			boolean isYes;
			if (10 <= p) {
				isYes = true;
			} else {
				int under = p;
				if (p >= c1) {
					under--;
				}
				if (p >= c2) {
					under--;
				}
				if (p >= c3) {
					under--;
				}
				isYes = under >= 4;
			}
			System.out.println(isYes ? "YES" : "NO");
		}
	}
}

Measured memory_bytes: 17204
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef unsigned long long ulint;
#define MOD 1000000007

int main(){
    multiset<lint> edge;
    set<lint> chk;
    int N;
    cin >> N;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        if(chk.find(a)!=chk.end()){
            edge.insert(a);
            chk.erase(chk.find(a));
        }
        else chk.insert(a);
    }

    if(edge.size()<2) cout << 0 << endl;
    else{
        auto it=edge.end();
        lint ans=*(--it);
        ans*=*(--it);
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 4992
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100025;
ll dp[maxn],arr[maxn];
int main()
{
    int n;
	cin>>n;
    for(int i = 1;i<=n;++i)
	cin>>arr[i];
    for(int i = 2;i<=n;++i)
    {
        if(i==2) 
		dp[i]=dp[i-1]+abs(arr[i]-arr[i-1]);
        else 
		dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 5180
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
using P = pair<int,int>;

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main()
{
    int K; string S; cin >> K >> S;
    if(S.size() <= K) cout << S << endl;
    else{
        rep(i,K) cout << S[i];
        cout << "..." << endl;
    }
}

Measured memory_bytes: 3580
#include <iostream>
using namespace std;

typedef long long ll;

int main()
{
	int n;
	ll l[87];
	l[0] = 2;
	l[1] = 1;
	
	cin >> n;
	
	if(n == 0) {
		cout << 2 << endl;
		return 0;
	}else if(n == 1) 
	{
		cout << 1 << endl; 
		return 0;
	}
	
	for (int i = 2; i <= n; ++i)
	{
		l[i] = l[i-1] + l[i-2];
	}
	
	cout << l[n] << endl;
	return 0;
}


Measured memory_bytes: 256
/**
 *  Author1: low-equipped w_udixixi
 *  Author2: Sher丶lock
 *  Date :2019-08-20
 **/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define pi 3.14159265358979323846
#define mem(a,x) memset(a,x,sizeof a)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=2e6+7;
const int INF=1e9;
const ll INFF=1e18;
int w[maxn];
int val[maxn];
int dp[maxn];
int main()
{
    int n,vol,sum=0;
    scanf("%d%d",&n,&vol);
    rep(i,1,n)
    {
        scanf("%d%d",&w[i],&val[i]);
        sum+=val[i];
    }
    rep(i,1,sum)
    {
        dp[i]=INF;
    }
    dp[0]=0;
    rep(i,1,n)
        for (int j=sum;j>=val[i];j--)
            dp[j]=min(dp[j],dp[j-val[i]]+w[i]);
    for (int i=sum;i>=1;i--)
    {
        if (dp[i]<=vol)
        {
            cout<<i<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_N = 2e5 + 2;
vector<ll> adj[MAX_N];
vector<ll> used(MAX_N,0);
vector<ll> path;
vector<ll> cycle;
ll cycle_start;
void dfs(ll cur)
{
    used[cur] = 1;
    path.push_back(cur);
    if(used[ adj[cur][0] ] == 1)
    {
        path.push_back(adj[cur][0]);
        cycle_start = adj[cur][0];
        return;
    }
    else
    {
        dfs(adj[cur][0]);
    }
}
void dfs2(ll cur)
{
    cycle.push_back(cur);
    if( adj[cur][0] == cycle_start)
    {
        return;
    }
    else dfs2(adj[cur][0]);
}
int main()
{
    ///freopen("sub1_21.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,k;
    ll u0,v0;
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
    {
        cin>>u0;
        adj[i].push_back(u0);
    }
    dfs(1);
    dfs2(cycle_start);
    if(k <= (path.size()-1))
    {
        cout<<path[k]<<endl;
        return 0;
    }
    k-=(path.size()-1);
    k%=cycle.size();
    cout<<cycle[k]<<endl;
}
///1 3 4


Measured memory_bytes: 26016
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
typedef long long ll;

int main(){
    ll n,k;
    cin >> n >> k;
    vector<double> e(n);
    rep(i, n){
        ll tmp;
        cin >> tmp;
        e.at(i) = (double)(tmp+1)/2;
    }

    
    // cusum
    vector<double> s(n+1,0);
    rep(i, n) s.at(i+1) = s.at(i) + e.at(i);
    double ans=0;
    for(int i=k;i<n+1;i++){
        double partsum= s.at(i)- s.at(i-k);
        if(ans < partsum) ans=partsum;
    }

    cout << fixed << setprecision(12) << ans << endl;
    return 0;
}

Measured memory_bytes: 3328
N, K = map(int,input().split())
MOD = 10**9 + 7
ans = 0
for k in range(K,N+2):
    t = N*(N+1)//2 - (N-k)*(N-k+1)//2
    s = k*(k-1)//2
    ans += t-s+1
    ans %= MOD
print(ans)


Measured memory_bytes: 9176
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
static const ll maxLL = (ll)1 << 62;
 
int main() {
    int a,b;
    cin>>a>>b;
    
    int x;
    if(b==100) x=1000*a+b;
    else if(b>=10 && b<100) x=100*a+b;
    else x=10*a+b;
    
    bool can=false;
    rep(i,0,340) {
        if(i*i==x) can=true;
    }
    if(can) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
#define ll long long int
#define MOD 1000000007
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

vector <ll> h,dp;
ll n;
ll rec(ll idx)
{
    if(dp[idx]!=-1) return dp[idx];
    // if(idx==n) return 0;
    if(idx>=n)return MOD; 
    if(idx==n-1)return 0;
    if(idx<n)
    {
    dp[idx]=min(rec(idx+1)+abs(h[idx]-h[idx+1]),rec(idx+2)+abs(h[idx]-h[idx+2]));
    }
    return dp[idx];
}
int main()
{ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
    ll c,a;
    cin>>n;
    for(ll i=0;i<n;i++)
    {
        cin>>a;
        h.push_back(a);
    }
    h.push_back(MOD);
    vector<ll> v(n,-1);
    dp=v;
    c=rec(0);
    cout<<c;
}


Measured memory_bytes: 5108
import sys

input=sys.stdin.readline

N=int(input())
A=[]
B=[]
for i in range(N):
    a,b=map(int,input().split())

    A.append(a)
    B.append(b)

if N%2==1:
    k=N//2
    A.sort()
    B.sort()
    small=A[k]
    large=B[k]
    print(large-small+1)

else:
    k=N//2
    A.sort()
    B.sort()
    small=A[k-1]+A[k]
    large=B[k-1]+B[k]
    print(large-small+1)

Measured memory_bytes: 89816
#include <bits/stdc++.h>
using namespace std;
 
//long long
using ll = long long;
 
// pair<int, int>
using PII = pair<int, int>;
 
//最大値、mod
const int MOD = 1000000007;
const int INF = 1000000000;
const long long LINF = 1e18;
const int MAX = 510000;
 
//出力系
#define print(x) cout << x << endl
#define prints(x) cout << fixed << setprecision(10) << x << endl
#define printc(x) cout << setw(2) << setfill('0') << x << endl;
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()
 
//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
 
//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
 
// 最小公倍数
unsigned lcm(unsigned a, unsigned b){
    return a / gcd(a, b) * b; 
}
 
// a = max(a, b), a = min(a, b)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
// 階乗(MODをとる)
ll pow_mod(ll num, ll pow, ll mod) {
    ll prod = 1;
    num %= mod;
    while (pow > 0) {
        if (pow & 1) prod = prod * num % mod;
        num = num * num % mod;
        pow >>= 1;
    }
    return prod;
}
 
 
 
// 二項係数(MODとる、1 ≦ k ≦ n ≦ 10^7 程度)
// COMinit()
// COM(x, y)
// とコンビで使う
 
// テーブルを作る前処理
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int main(){
  double L;
  cin >> L;
  double a = L / 3;
  double ans = a * a * a;
  prints(ans);
  return 0;
}


Measured memory_bytes: 256