akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep0(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

bool solve(int i, int m, const vector<int> &a)
{
    if (m == 0)
    {
        return true;
    }

    if (i == a.size())
    {
        return false;
    }

    return (solve(i + 1, m, a) || solve(i + 1, m - a[i], a));
}

int main()
{
    int n = 0;
    cin >> n;

    vector<int> a(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    int q = 0;
    cin >> q;

    vector<int> m(q, 0);
    for (int i = 0; i < q; i++)
    {
        cin >> m[i];
    }

    for (int i = 0; i < q; i++)
    {
        cout << (solve(0, m[i], a) ? "yes" : "no") << endl;
    }

    return 0;
}


Measured memory_bytes: 3104
#include<bits/stdc++.h>
using namespace std;
     
int n,a[100001],cnt,f;     
int main(){
 cin>>n;
 for(int i=0;i<n;i++)scanf("%d",&a[i]);
 
 for(int i=0;i<n-1;i++)
  if(f==0){
   if(a[i]>a[i+1])f=1;
   else if(a[i]<a[i+1])f=2;
  }
  else if(f==1 && a[i]<a[i+1]){f=0;cnt++;}
  else if(f==2 && a[i]>a[i+1]){f=0;cnt++;}
       
 cout<<cnt+1<<endl;
 return 0;
}

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

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

int N;
ll A[2005];
ll dp[2005][2005];
ll cnt = 0;

ll dfs(int a, int b){
	if(dp[a][b] != -1)return dp[a][b];
	cnt++;
	//cout << a << " " << b << endl;
	if(a == b) return 0;

	int a1 = a,b1 = b;

	if(A[a] > A[b]) a1 = (a+N+1)%N;
   	else b1 = (b+N-1)%N;

	if(a1 == b1) return dp[a][b] =  A[a1];

	ll ret = -1;

	int na = (a1+N+1)%N;
	int nb = b1;
	if(na == nb) ret = max(ret,A[a1]);
	else ret = max(ret, dfs(na,nb)+A[a1]);

	na = a1;
	nb = (b1+N-1)%N;
	if(na == nb) ret = max(ret,A[b1]);
	else ret = max(ret, dfs(na,nb)+A[b1]);
	//cout << a << " " << b << " " << dp[a][b] << endl;

	return dp[a][b] = ret;

}

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

	cin >> N;

	for (int i = 0;i < N;i++){
		cin >> A[i];
	}

	for (int i = 0;i < N; i++){
		for (int j = 0;j < N;j++){
			dp[i][j] = -1;
		}
	}

	ll ans = -1;

	for (int i = 0;i < N;i++){
		ans = max(ans, dfs((i+1+N)%N,(i-1+N)%N)+A[i]);
	}

	cout << ans << endl;
	//cout << cnt << endl;

	return 0;

}



Measured memory_bytes: 34620
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;


int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};



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

	cin >> a;
	vector<int>ans(a);
	vector<int>data(a);

	rep(i, 0, a) {
		cin >> data[i];
		ans[i] = data[i];
	}

	sort(ans.begin(), ans.end());
	rep(i, 0, a) {
		if (data[i] >= ans[a / 2]) {
			cout << ans[a / 2 - 1] << endl;
		}
		else {
			cout << ans[a / 2] << endl;
		}
	}
	
	
	
	


}
	

Measured memory_bytes: 3840
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

int main(){
    int a,b,c,k;
    cin >> a>> b>> c>> k;
    int ans=0;
    if(k>a){
        ans+=a;
        k-=a;
    }else{
        cout<<k<<endl;
        return 0;
    }
    if(k>b){
        k-=b;
    }else{
        cout<<ans<<endl;
        return 0;
    }
    ans-=k;
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3636
#include<stdio.h>
int main()
{
	int W, H, x, y, r;
	scanf("%d", &W);
	scanf("%d", &H);
	scanf("%d", &x);
	scanf("%d", &y);
	scanf("%d", &r);
	if (0 <= x - r & x + r <=W & 0 <= y - r & y + r <= H)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}


Measured memory_bytes: 2700
#include "bits/stdc++.h"

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back



int main(){
   int n;
   while(cin>>n){
       if(n==-1)break;
       
       long double seta=0;
       for(int i=1;i<n;i++){
           seta+=atan(1.0/sqrt(i));
           while(seta>=2*M_PI)seta-=2*M_PI;
       }
       double l=sqrt(n);
       
       printf("%.20Lf\n",l*cos(seta));
       printf("%.20Lf\n",l*sin(seta));

       
   }
   
   return 0;
}

Measured memory_bytes: 1252
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
  int n,k,x[100000],ans=1000000000;
  scanf("%d %d",&n,&k);
  for(int i=0;i<n;i++)
    scanf("%d",&x[i]);
  for(int i=0;i<n-k+1;i++){
    if(x[i]>0)
      ans=min(ans,x[i+k-1]);
    else if(x[i+k-1]<0)
      ans=min(ans,-1*x[i]);
    else
      ans=min(x[i+k-1]-x[i]+min(-1*x[i],x[i+k-1]),ans);
  }
  printf("%d\n",ans);
}

Measured memory_bytes: 512
N = int(input())

# initialize
ans = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    a = list(map(int, input().split()))
    id = a[0]
    jisu = a[1]
    for j in range(jisu):
        c = a[j+2]
        ans[i][c-1] = 1

for i in range(N):
    for j in range(N):
        if j != N-1:
            print(ans[i][j], end=" ")
        else:
            print(ans[i][j])

            

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


#define f(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define char_f(i,a) for(int i=(int)(a);(char)s[i]!='\0';i++)
#define rf(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define llf(i,a,b) for(long long int i=(long long int)(a);i<=(long long int)(b);i++)
#define llrf(i,a,b) for(long long int i=(long long int)(a);i>=(long long int)(b);i--)



#define ll long long
#define fi first
#define se second
#define pb push_back
#define pop pop_back
#define mem(ara) memset((ara),0,sizeof(ara))
#define memn(ara) memset((ara),-1,sizeof(ara))
#define b begin()
#define e end()
#define em emplace
#define eb emplace_back





#define si set<int>
#define sd set<double>
#define sll set<long long int>
#define ss set<string>
#define sc set<char>

#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pcl pair<char,long long int>
#define plc pair<long long int,char>

#define pss pair<string,string>
#define pcc pair<char,char>

#define pis pair<int,string>
#define psi pair<string,int>
#define pls pair<long long int,string>
#define psl pair<string,long long int>
#define pdd pair<double,double>
#define pcs pair<char,string>
#define psc pair<string,char>



#define vi  vector<int>
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vii vector<pii>



#define mod 1000000007
#define mx (1<<30)-1
#define llmx (1ll<<62)
#define n_size 100005
#define g_size 10000005
double PI=acos(-1);



///unsigned int uMAX=4294967295;
///unsigned ll int ullMAX=18446744073709551615;





int arr[g_size];



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n,m,T,res;

	int maxi=-mx,mini=mx,count=0;

	int i,j,k;

	bool flag;

	string s1,s2,s3;

	char s[100000];

	int ara[n_size],ara2[n_size];

	cin>>s1>>s2>>s3;

    //cout<<s1[s1.length()-1]<<" "<<s2[0]<<" "<<s2[s2.length()-1]<<" "<<s3[0]<<endl;

	if(s1[s1.length()-1]==s2[0]  && s2[s2.length()-1]==s3[0]){
        cout<<"YES"<<endl;
	}
	else cout<<"NO"<<endl;



}


Measured memory_bytes: 256
#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(){
    int N,Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> l(Q),r(Q);
    rep(i,Q){
        cin >> l[i] >> r[i];
        l[i]--;r[i]--;
    }
    vector<int> cnt(N);
    rep(i,N-1){
        if(S[i]=='A'&&S[i+1]=='C'){
            cnt[i+1]=cnt[i]+1;
        }else{
            cnt[i+1]=cnt[i];
        }
    }
    rep(i,Q){
        cout << cnt[r[i]]-cnt[l[i]] << endl;
    }
    return 0;
}

Measured memory_bytes: 2176
n = int(input())
p = [0]*(n+1)
flag = 0
if n==1:
    print(1)
    exit()
for i in range(1,n+1):
    p[i] = i + p[i-1]
    if p[i] > n:
        flag = i
        break
r = p[flag] -n
for i in range(1,flag+1):
    if i!=r:
        print(i)
    else:
        continue

Measured memory_bytes: 81652
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;

int main(void) {
  int nQuery;
  scanf("%d", &nQuery);
  
  ll bsum = 0;
  priority_queue<ll> q1; // 大きい順に出る
  priority_queue<ll, vector<ll>, greater<ll> > q2; // 小さい順に出る
  ll sum1 = 0;
  ll sum2 = 0;

  REP(iQuery, nQuery) {
    int type;
    scanf("%d", &type);
    if(type == 1) {
      ll a, b;
      scanf("%lld%lld", &a, &b);
      bsum += b;
      if(q1.size() == q2.size()) {
        q2.push(a);
        sum2 += a;
        ll t = q2.top(); q2.pop();
        sum2 -= t;
        q1.push(t);
        sum1 += t;
      } else {
        q1.push(a);
        sum1 += a;
        ll t = q1.top(); q1.pop();
        sum1 -= t;
        q2.push(t);
        sum2 += t;
      }
    } else {
      if(q1.empty()) {
        assert(false);
      } else {
        ll a = q1.top();
        ll sum = bsum;
        sum += a * (int)q1.size() - sum1;
        sum += sum2 - a * (int)q2.size();
        printf("%lld %lld\n", a, sum);
      }
    }
  }
    
  return 0;
}


Measured memory_bytes: 3956
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <string>
#include <vector>
#include <vector>

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void)
{
  int n; cin >> n;
  vector<int> a(n);
  vector<int> x(n);
  int sum = 0;
  x[0] = sum;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    sum += a[i];
    if (i % 2 == 1) {
      x[0] -= 2 * a[i];
    }
  }

  x[0] += sum;

  for (int i = 0; i < n; ++i) {
    if (i != 0) {
      x[i] = 2 * a[i - 1] - x[i - 1];
    }
    cout << x[i];
    cout << " ";
  }

}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
//const int64_t INF = 1LL << 60;
//const int INF = 1 << 29;
//const int MODINF = 1000000007;
using namespace std;

int main(){
    int N;
    cin >> N;
    int ans = 1;
    while(ans* 2 <= N){
        ans *= 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int i,j;
    int H,W;
    
    while(1){
        scanf("%d %d", &H, &W);
        if(H==0 && W==0) break;
        
        for(i=1; i<=H; i++){
            for(j=1; j<=W; j++){
                if(i%2 == 1){
                    if(j%2 == 1)printf("#");
                    else printf(".");
                }
                else{
                    if(j%2 == 1)printf(".");
                    else printf("#");
                }
            }
            printf("\n");
        }
        printf("\n");
        
    }
    
}



Measured memory_bytes: 2056
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
#define fin {cout<<-1<<endl;return 0;}
//template
int pw(int n,int k){
  int res=1;
  while(k){
    if(k&1)res*=n;//res%=MOD;
    n*=n;//n%=MOD;
    k>>=1;
  }
  return res;
}
//main
signed main(){
  //解説AC
  int N;cin>>N;
  std::vector<int> x(N),y(N);
  for(int i=0;i<N;i++)cin>>x[i]>>y[i];
  for(int i=0;i<N-1;i++)if(((x[i]+y[i])&1)!=((x[i+1]+y[i+1])&1))fin
  bool even=((x[0]+y[0])%2+1)%2;
  cout<<32+even<<endl;
  for(int k=pw(2,31);k;k/=2){
    if(k<pw(2,31))cout<<" ";
    cout<<k;
  }
  if(even)cout<<" "<<1;cout<<endl;
  for(int i=0;i<N;i++)x[i]-=even;
  std::vector<int> u(N),v(N);//u=x+y,v=x-y 45rotate
  for(int i=0;i<N;i++)u[i]=x[i]+y[i];
  for(int i=0;i<N;i++)v[i]=x[i]-y[i];
  for(int i=0;i<N;i++){
    string ans;
    int k=pw(2,31);
    while(k){
      if(u[i]>0&&v[i]>0){ans+="R";u[i]-=k;v[i]-=k;}
      else if(u[i]>0&&v[i]<0){ans+="U";u[i]-=k;v[i]+=k;}
      else if(u[i]<0&&v[i]>0){ans+="D";u[i]+=k;v[i]-=k;}
      else{ans+="L";u[i]+=k;v[i]+=k;}
      k/=2;
    }
    cout<<ans;if(even)cout<<"R";cout<<endl;
  }
}


Measured memory_bytes: 256
import math
from fractions import gcd
 
def number_calc(A,B,x):
    if A%x == 0:
        left = A//x
    else:
        left = A//x + 1
    right = B//x
    res = max(right-left+1,0)
    return res
 
A,B,C,D = map(int,input().split())
 
ans = B-A+1
ans -=number_calc(A,B,C)
ans -=number_calc(A,B,D)
lcm = (C*D)//gcd(C,D)
ans +=number_calc(A,B,lcm)
 
print(ans)

Measured memory_bytes: 5048
#include  <iostream>
#include  <stdio.h>
#include <algorithm>
#include <map>
#include <math.h>

using namespace std;
#include <vector>
#define rep(i,n) for (ll i = 0; i < (n) ; i++)
#define INF 1e9
#define llINF 1e18
#define base10_4 10000      //1e4
#define base10_5 100000     //1e5
#define base10_6 1000000    //1e6
#define base10_7 10000000   //1e7
#define base10_8 100000000  //1e8
#define base10_9 1000000000 //1e9

#define MOD 1000000007
#define pb push_back
#define ll long long
#define ld long double
#define ull unsigned long long
#define vint vector<int>
#define vll vector<ll>

//#include <stack>
//#include <queue>

// #include <iomanip>
//  cout << fixed << setprecision(15) << y << endl;

string ans_Yes = "Yes"; 
string ans_No = "No"; 
string ans_yes = "yes"; 
string ans_no = "no"; 

vll A;
vll B;
ll C;
ll N;
ll M;
ll K;

ll ltmp;
string stmp;
double dtmp;

class UnionFind {
public:
    vector<ll> parent; // parent[i]:iの親の番号　(例) parent[3] = 2 : 3の親が2
    vector<ll> groupsize;
    UnionFind(ll N){ //最初は全てが根であるとして初期化
        for(ll node_i = 0; node_i < N; node_i++){
            ll parent_i = node_i;
            parent.push_back(parent_i);
            groupsize.push_back(1);
        }
    }
    ll getRoot(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (parent[x] == x) return x;
        return parent[x] = getRoot(parent[x]);
    }
    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = getRoot(x); //xの根をrx
        ll ry = getRoot(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        parent[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        groupsize[ry]+=groupsize[rx];
    }
    ll getSize(ll x){
        return groupsize[getRoot(x)];
    }
    bool isSameRoot(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = getRoot(x);
        ll ry = getRoot(y);
        return rx == ry;
    }
};
ll llmin(ll a,ll b){
    if(a>=b) return b;
    return a;
}
ll llmax(ll a,ll b){
    if(a<=b) return b;
    return a;
}
int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    cin >> M;

    rep(mi,M){
        cin >> ltmp;
        ltmp--;
        A.push_back(ltmp);

        cin >> ltmp;
        ltmp--;
        B.push_back(ltmp);
    }

    UnionFind uf(N);
    rep(mi,M){
        uf.unite(A[mi],B[mi]);
    }

    ll ans = 0;
    rep(ni,N){
        ltmp = uf.getSize(ni);
        ans = llmax(ans,ltmp);

    }    

    cout << ans << endl;    

}

Measured memory_bytes: 17500
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void)
{
	int i,a,n,d,min=1000;
	char s[11];
	int len;
	scanf("%s",s);
	len=strlen(s);
	for(i=0;i<len-2;i++){
		n=(s[i]-'0')*100+(s[i+1]-'0')*10+s[i+2]-'0';
		d=abs(n-753);
		if(d<min)
			min=d;
	}
	
	printf("%d",min);
	return 0;
}
	

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

int main()
{
  ll N; cin >> N;
  ll ans = 0;
  rep(i,N){
    if(i%3 != 0 && i%5 != 0) ans += i;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3636
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
count = Hash.new(0)
ans = 0
a.each do |i|
  count[i] += 1
end
count.each do |key,value|
  if key.to_i <= value
    ans -= key.to_i
  end
end
puts n+ans

Measured memory_bytes: 15492
#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long int
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vl(p) vector<p>
#define W while
#define For(i,s,x) for(i=s;i<x;i++)
#define Fore(i,s,x) For(i,s,x+1)
#define FoR(i,s,x) for(i=s-1;i>=x;i--)
#define ForE(i,s,x) FoR(i,s+1,x)
#define fi(i,s,x) for(int i=s;i<x;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define in insert
#define sz size()
#define F first
#define S second
#define nl cout<<"\n"
#define pr(a) cout<<a<<" "
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define prA(a,m,n) fi(z,m,n+1) pr(a[i]); nl 
#define trace2(x, y)             cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)       cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;
#define trace5(a, b, c, d, e)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<endl;
#define mod 1000000007
#define MAX 200005

int main() {
    FASTIO;
    ll t=1, i, j, k, l;
    // cin>>t;
    W(t--) {
        ll n, M;
        cin>>n>>M;
        ll w, v, dp[M+1], ans=0;
        memset(dp,-1,sizeof(dp));
        dp[0]=0;
        For(i,0,n) {
            cin>>w>>v;
            ForE(j,M,w) {
                if(dp[j-w]!=-1) {
                    dp[j]=max(dp[j],dp[j-w]+v);
                    ans=max(ans,dp[j]);
                }
            }
        }
        cout<<ans;
        nl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	int h,m,s;
	long x,a;
	scanf("%d",&x);
	h=x/3600;
	a=x%3600;
	m=a/60;
	s=a%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}


Measured memory_bytes: 2140
s=int(input())
a=list(map(int,input().split()))
c=0
for x in range(1,s-1):
    if a[x-1]<a[x] and a[x]<a[x+1]:c+=1
    if a[x-1]>a[x] and a[x]>a[x+1]:c+=1
print(c)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int main() {

	string s;
	cin >> s;

	rep(i, 0, s.size()) {
		if (s[i] == 'C') {
			rep(j, i + 1, s.size()) {
				if (s[j] == 'F') {
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdarg>
#include <valarray>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <deque>
#include <locale>
#include <memory>
#include <stdexcept>
#include <exception>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <iostream>
#include <bitset>

using namespace std;

#define int long long

int hell = 1e9 + 7;

int count(int xCurr, int yCurr, int xFin, int yFin, vector< vector<char> > &A, vector< vector<int> > &dp)
{
	if(xCurr > xFin || yCurr > yFin)
		return 0;
	if(xCurr == xFin && yCurr == yFin)
		return 1;
	if(A[xCurr][yCurr] == '#')
		return 0;
	if(dp[xCurr][yCurr] != -1)
		return dp[xCurr][yCurr];
	dp[xCurr][yCurr] = (count(xCurr+1,yCurr,xFin,yFin,A,dp) + count(xCurr,yCurr+1,xFin,yFin,A,dp))%hell;
	return dp[xCurr][yCurr];
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int m, n, i, j;
	cin>>m>>n;
	vector< vector<char> > A(m, vector<char>(n));
	for(i = 0; i < m; i++)
		for(j = 0; j < n; j++)
			cin>>A[i][j];
	vector< vector<int> > dp(m, vector<int>(n,-1));
	cout<<count(0,0,m-1,n-1,A,dp)<<endl;

	return 0;
}

Measured memory_bytes: 9344
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e15;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
// __uint128_t
const ll MOD = 1e9+7;



vector<ll> Eratosthenes(ll N){
    vector<bool> is_prime(N+1);
    for(int i = 0; i <= N; i++)is_prime[ i ] = true;
    vector<ll> P;
    for( int i = 2; i <= N; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= N; j += i ) is_prime[ j ] = false;
            P.emplace_back( i );
        }
    }
    return P;
}


int main(){
    ll N; cin >> N;
    ll ans = 0;
    vector<ll> P, D(N+1), V(N+1); D[1] = 1;
    
    vector<bool> is_prime(N+1);
    for(int i = 0; i <= N; i++)is_prime[ i ] = true;
    for( int i = 2; i <= N; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= N; j += i ) {
                is_prime[ j ] = false;
                D[j] = i;
            }
            D[i] = i;
            P.emplace_back( i );
        }
    }

    for(int i = 2; i < N; i++){
        map<ll, ll> M;
        ll X = i;
        while(X != 1){
            M[D[X]]++;
            X /= D[X];
        }
        ll temp = 1;
        for(auto m : M) temp *= (m.second+1);
        V[i] = temp;

    }

    



    for(int C = 1; C < N; C++){
        ll X = N-C;
        ans += V[X];
    }
    cout << ans+1 << endl;

}


Measured memory_bytes: 19964
#define rep(i, n) for(int i=1; i<=n; i++)
#include <bits/stdc++.h>
using namespace std;

void solve() {
	int N; cin >> N;
	double res = 0;
	rep(i, N) {
		if (i % 2 != 0) res++;
	}
	cout << res / N << endl;
}

int main(void) {
	solve();

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
const int MAXN = 1e5 + 10;
const int INF = 2*1e9;

int dp[MAXN];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<int> h(n);
	for(int i{}; i<n; i++) cin >> h[i];
	dp[1] = abs(h[1]-h[0]);
	for(int i{2}; i<n; i++){
		// i'ye gelmek icin olan deger
	dp[i] += min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
		}

	cout << dp[n-1] << "\n";





}


Measured memory_bytes: 4100
num_choice = int(raw_input())
price=list(map(int,raw_input().split()))
base_cal = int(raw_input())
topping_cal = []
for i in range (num_choice):
	topping_cal.append(int(raw_input()))
topping_cal.sort()
topping_cal.reverse()
average_cal = int(base_cal / price[0])
for i in range (num_choice):
	new_average = int((sum(topping_cal[:i+1]) + base_cal) / (price[0] + price[1] * (i+1)) )
	if new_average >= average_cal:
		average_cal = new_average
	else:
		break
print average_cal

Measured memory_bytes: 6352
def func():
    pass


def main():
    k, a, b = map(int, input().split())

    # i = 0
    # c = 1
    # while i < k:
    #     if c >= a and (k - i - 1) >= 2:
    #         # print("2:", i, c)
    #         c = c - a + b
    #         i += 1
    #     else:
    #         # print("3:", i, c)
    #         c += 1
    #     i += 1
    #
    # print(max(c, k))

    x = k - (a - 1)
    y = x // 2

    # 2,3 を y回繰り返す
    # y * (b-a)まい増える

    # print(x, y, y * (b - a) + (k - ((a - 1) + 2 * y)))
    q = (y * (b - a) + (k - ((a - 1) + 2 * y)))
    print(max((q + a), k + 1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <cctype>
#include <functional>
#include <climits>
 
using namespace std;
#define pr(...) do { _ost << #__VA_ARGS__ << " = "; ~(_ost,__VA_ARGS__); } while(0);
ostream & _ost = cout;
template <class T>
ostream &operator,(ostream& ost, const T& value) { return ost << value << ","; }
ostream &operator~(ostream& ost) { return ost << endl; }
template <class T>
string tos(const T& var){ ostringstream ss; ss << var; return ss.str(); }
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
 
typedef vector<int> vi;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long ul;
typedef unsigned long long ull;
 
const int mod = 1000000007;
const int INF = 1000000;
const double EPS = 1e-10;

int n;

int main(){
    while(cin>>n,n){
        bool f=0;
        int c=0;
        FOR(i,0,n){
            int k;cin>>k;
            if(k>=2)f=1,c++;
            else if(k)c++;
        }
        if(f)cout<<c+1<<endl;
        else cout<<"NA"<<endl;
    }
}
  

Measured memory_bytes: 1160
N, M = map(int, input().split())
F = [1]+[2]+[0]*100000

for i in range(2, 100002):
    F[i] = F[i-1] + F[i-2]

ans = 1
cur = 0
pre = 0
for i in range(M):
    broken = int(input())
    if pre == broken:
        continue
    pre = broken
    if cur == broken:
        print(0)
        break
    elif broken - cur == 1:
        cur = broken + 1
    else:
        ans *= F[broken - cur - 2]
        ans %= 1000000007
        cur = broken + 1
else:
    if N > cur:
        ans *= F[N - cur - 1]
    print(ans % 1000000007)


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

double dp[105][105];

int main() {
    vector<double> res;
    int N, T, L, B;
    while (cin >> N >> T >> L >> B and N) {
        vector<bool> l(N + 1, false), b(N + 1, false);
        for (int i = 0; i < L; i++) {
            int x;
            cin >> x;
            l[x] = true;
        }
        for (int i = 0; i < B; i++) {
            int x;
            cin >> x;
            b[x] = true;
        }
        for (int i = 0; i <= T; i++) {
            for (int j = 0; j <= N; j++) {
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1.0;
        for (int i = 0; i < T; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 1; k <= 6; k++) {
                    int to = j + k;
                    if (to >= 2 * N) {
                        to %= N;
                    } else if (to > N) {
                        to -= (to % N) * 2;
                    }
                    //cout << "Turn: " << i << " Current: " << j << " To:" << to << endl;
                    if (l[j]) {
                        if (b[to]) {
                            dp[i + 2][0] += dp[i][j] / 6.0;
                        } else {
                            dp[i + 2][to] += dp[i][j] / 6.0;
                        }
                    } else {
                        if (b[to]) {
                            dp[i + 1][0] += dp[i][j] / 6.0;
                        } else {
                            dp[i + 1][to] += dp[i][j] / 6.0;
                        }
                    }
                }
            }
        }
        double cnt = 0.0;
        for (int i = 0; i <= T; i++) {
            cnt += dp[i][N];
        }
        res.push_back(cnt);
    }
    for (int i = 0; i < (int)res.size(); i++) {
        printf("%.12lf\n", res[i]);
    }
    return 0;
}



Measured memory_bytes: 3268
#include <iostream>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;

int comp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

int main() {
	char a, b;
	cin >> a >> b;
	if(a == 'H'){
		if(b == 'H'){
			cout << "H" << endl;
		}else{
			cout << "D" << endl;
		}
	}else{
		if(b == 'H'){
			cout << "D" << endl;
		}else{
			cout << "H" << endl;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>

using namespace std;
typedef long long int ll;
void sayYes() { cout << "Yes" << endl; };
void sayNo() { cout << "No" << endl; };
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }                   // 最大公約数
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };                      // 最小公倍数
ll getDigit(ll num) { return log10(num) + 1; }                         // 桁数
ll digitSum(ll n) { return (n < 10) ? n : digitSum(n / 10) + n % 10; } // 各桁の和
#define rep(i, n) for (ll i = 0; i < n; i++)

void Main()
{
    // int n;
    // cin >> n;
    // vector<int> a(n);
    // rep(i, n)
    // {
    //     cin >> a[i];
    // }

    int n;
    cin >> n;
    vector<string> s(n);
    rep(i, n)
    {
        cin >> s[i];
    }

    int ans = 0;
    set<string> s2(s.begin(), s.end());

    ans = s2.size();
    cout << ans << endl;
    return;
}

signed main(void)
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 25028
/*~~~~~~~~~~~~~~~~~~~~~~~~*
 *  Jeevan ek rahasya hai *
 *     slow_processor     *
 * Author-maskman_lucifer *
 *~~~~~~~~~~~~~~~~~~~~~~~~*/
#include <bits/stdc++.h>                                        
#define ll long long 
#define mpr make_pair
#define pll pair<ll,ll>
#define pb push_back
#define M 1000000007
#define PI 3.141592653589793
#define lc '\n'
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll dp[n+1];
    for(ll i=1;i<=n;i++)
    {
        dp[i]=0;
    }
    for(ll i=0;i<n-1;i++)
    {
        ll x;
        cin>>x;
        dp[x]++;
    }
    for(ll i=1;i<=n;i++)
    {
        cout<<dp[i]<<lc;
    }
    return 0;
}

Measured memory_bytes: 5224
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

int main()
{
	long long int nn, mm, tmp, sum = 0;
	scanf("%lld %lld", &nn, &mm);
	for(int ii = 0;ii < mm;ii++)
	{
		scanf("%lld", &tmp);
		sum += tmp;
	}
	printf("%lld\n", ((nn - sum) < 0 ? (-1) : (nn - sum)));
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,b,c,x,y,z,cnt=0;
     //int arr[4];
    string s,ss;
    cin>>s>>ss;
    for(int i=0;i<3;i++)
    {
        if(s[i]==ss[i])
        {
            cnt++;
        }
    }
     cout<<cnt<<endl;



	return 0;
}


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

void init() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
}

void solve() {
	set<int> s; int a;
	cin >> a; s.insert(a);
	cin >> a; s.insert(a);
	cin >> a; s.insert(a);
	cout << s.size();
}

int main() {
	init();
	int t = 1; //scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}


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

int main() {
    int x; cin >> x;
    int y = x;
    while(true){
        bool ok = true;
        for(int i=2; i<y; i++){
            if(y % i == 0){
                ok = false;
                break;
            }
        }
        if(ok) break;
        y++;
    }
    cout << y << endl;
}


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

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        while(a % 2 == 0) {
            a /= 2;
            ++cnt;
        }
    }

    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3648
import java.util.*;

class Task implements Comparable<Task>{
    int a;
    int b;

    @Override
    public int compareTo(Task o){
        return this.b - o.b;
    }

    public Task(int a, int b){
        this.a = a;
        this.b = b;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        PriorityQueue<Task> q = new PriorityQueue<>();

        for(int i = 0; i < n; i++){
            q.add(new Task(sc.nextInt(), sc.nextInt()));
        }

        int t = 0;

        while(!q.isEmpty()){
            Task task = q.poll();
            if(t + task.a > task.b){
                System.out.println("No");
                return;
            }
            t += task.a;
        }

        System.out.println("Yes");

    }
}


Measured memory_bytes: 101976
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0)
#define ll long long int
#define ld long double
#define ull unsigned long long int
#define reptArIn(i,a,b,ar) for( i=a; i<b; ++i) cin>>ar[i];
#define fo(i,a,b) for(i=a; i<b; ++i)
#define foe(i,a,b) for(i=a; i<=b; ++i)
#define rep(i,n) for(i=1;i<=n;i++)
#define all(a) a.begin(), a.end()
#define pb push_back
#define ins insert
#define mk make_pair
#define f first
#define s second
#define mod 1000000007
#define vi vector<int>
#define vll	vector<ll>
#define vvi	vector<vi>
#define pii	pair<int,int> //typedef pair<int,int> pii;
#define pll	pair<ll , ll>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>  new_data_set;
//mp.reserve(4096);
//mp.max_load_factor(0.25);

int main()
{
	ll n,m,i,j;
	cin>>n>>m;
	char mat[n][m];
	ll dp[n][m];
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			cin>>mat[i][j];
		}
	}
	dp[0][0]=1;
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			if(mat[i][j]!='#')
			{
				if(j==0&&i!=0)
			    {
				  dp[i][j]=dp[i-1][j];
			    }
			    else if(i==0&&j!=0)
			    {
			      dp[i][j]=dp[i][j-1];	
			    }
			    else if(i!=0&&j!=0)
		    	dp[i][j]=((dp[i-1][j]%mod)+(dp[i][j-1]%mod))%mod;
			}
			else
			dp[i][j]=0;
		}
	}
	cout<<dp[n-1][m-1]<<endl;
	return 0;
}

Measured memory_bytes: 9088
def main():
  import sys
  b=sys.stdin.buffer
  h,w=map(int,b.readline().split())
  x=w+1
  s=[c>>3for c in b.read()]
  dp=[10000]*h*x
  a=p=s[0]
  dp[0]=b=q=5-a
  for i in range(1,w):
    t=s[i]
    dp[i]=b=b+(a^t)
    a=t
  for i in range(x,h*x,x):
    t=s[i]
    dp[i]=q=q+(p^t)
    p=t
    for j in range(1,w):
      k=i+j
      sk=s[k]
      l=k-1
      t=dp[l]+(s[l]^sk)
      l=k-x
      u=dp[l]+(s[l]^sk)
      if t>u:t=u
      dp[k]=t
  print(dp[-2]+1>>1)
main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
//    std::sort(a.begin(), a.end(), std::greater<int>() );
#define REP(i, s, n) for (int i = s; i < n; ++i)
#define rep(i, n) REP(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

using namespace std;
std::vector<std::string> split(const std::string &input, char delimiter)
{
    std::istringstream stream(input);

    std::string field;
    std::vector<std::string> result;
    while (std::getline(stream, field, delimiter))
    {
        result.push_back(field);
    }
    return result;
}

int main()
{
    string a = "YAKI";
    string b;
    cin >> b;
    rep(i, 4)
    {
        if (a[i] != b[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
s += 'R'
b = []
n = len(s)
for i in range(n-1):
    if s[i] == 'L' and s[i+1] == 'R':
        b.append(i+1)
l = 0
ans = [0]*(n-1)

for r in b:
    #[l,r]
    flag = 0
    for i in range(l,r):
        
        if s[i] == 'L' and not flag:
            #[l,i)がR,[i,r]がL
            flag = 1
            r_l = i
    evencnt = 0
    oddcnt = 0
    for i in range(l,r):
        if (abs(r_l-i))%2:oddcnt+=1
        else:evencnt+=1
    ans[r_l] = evencnt
    ans[r_l-1] = oddcnt

        

    l = r
print(*ans)

        
        
    
    
        
        
    
        

Measured memory_bytes: 49852
// 2014/12/10 Tazoe

#include <iostream>
using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;

	int DP[100][3];
	for(int i=0; i<100; i++){
		for(int j=0; j<3; j++){
			DP[i][j] = 0;
		}
	}

	for(int i=0; i<K; i++){
		int A, B;
		cin >> A >> B;

		if(B==1){
			DP[A-1][1] = DP[A-1][2] = -1;
		}
		else if(B==2){
			DP[A-1][0] = DP[A-1][2] = -1;
		}
		else{
			DP[A-1][0] = DP[A-1][1] = -1;
		}
	}

	for(int j=0; j<3; j++){
		if(DP[0][j]==-1)
			continue;

		DP[0][j] = 1;
	}

	int sum0 = 0;
	for(int j=0; j<3; j++){
		if(DP[0][j]==-1)
			continue;

		sum0 += DP[0][j];
	}

	for(int j=0; j<3; j++){
		if(DP[1][j]==-1)
			continue;

		DP[1][j] = sum0;
	}

	for(int i=2; i<N; i++){
		int sum = 0;
		for(int j=0; j<3; j++){
			if(DP[i-1][j]==-1)
				continue;

			sum += DP[i-1][j];
		}

		for(int j=0; j<3; j++){
			if(DP[i][j]==-1)
				continue;

			DP[i][j] = sum;

			if(DP[i-1][j]!=-1 && DP[i-2][j]!=-1){
				for(int k=0; k<3; k++){
					if(j==k){
						DP[i][j] += 10000;
						DP[i][j] -= DP[i-1][k];
					}
					else{
						if(DP[i-2][k]!=-1){
							DP[i][j] += DP[i-2][k];
						}
					}
				}
			}

			DP[i][j] %= 10000;
		}
	}

//	for(int i=0; i<N; i++){
//		for(int j=0; j<3; j++){
//			cout << DP[i][j] << ' ';
//		}
//		cout << endl;
//	}

	int sum1 = 0;
	for(int j=0; j<3; j++){
		if(DP[N-1][j]==-1)
			continue;

		sum1 += DP[N-1][j];
	}

	cout << sum1%10000 << endl;

	return 0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

using namespace std;
using ll = long long;

const ll MOD = 1000000007LL; // = 10^9 + 7
const double PI = 3.14159265358979;

void solve()
{
  vector<int> dish(5);
  for(int i = 0; i < 5; ++i)
  {
    cin >> dish[i];
  }
  sort(dish.begin(), dish.end(), [](auto const& l, auto const& r){
    return (l-1) % 10 > (r-1) % 10;
  });

  ll ans = 0;
  for(int i = 0; i < 4; ++i)
  {
    ans += dish[i] + (10 - (dish[i] % 10)) % 10;
  }
  ans += dish[4];
  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

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

using namespace std;

/*  テンプレここから */
typedef long long ll;

#define rep(i, n) for(int i = 0; i < n; ++i)
#define repi(i, start, end) for(int i = start; i < end; ++i)
#define all(x) (x).begin(), (x).end()
#define INF (1e9)
#define INFL (1e18)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)
#define out(x) cout << (x) << endl;
#define outyes(bool_val) cout << (bool_val ? "yes" : "no") << endl;
#define outYes(bool_val) cout << (bool_val ? "Yes" : "No") << endl;
#define outYES(bool_val) cout << (bool_val ? "YES" : "NO") << endl;
#define outPossible(bool_val) cout << (bool_val ? "Possible" : "Impossible") << endl;
#define outPOSSIBLE(bool_val) cout << (bool_val ? "POSSIBLE" : "IMPOSSIBLE") << endl;

template<typename A, size_t N, typename T>
void array_fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}
ll gcd(ll a, ll b){
    if(b == 0) return a;
    else return gcd(b, a % b);
}

int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
/*  テンプレここまで */

int n, k, min_val = INF;
vector<int> nums;

void search(int sum){
    if(sum >= n){
        min_val = min(min_val, sum);
        return;
    }

    for(int i = 0; i < nums.size(); ++ i){
        if(sum == 0 && nums[i] == 0) continue;
        search(sum * 10 + nums[i]);
    }
}

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

    cin >> n >> k;

    int check[10] = {0};
    rep(i, k){
        int d;
        cin >> d;
        check[d] = 1;
    }
    rep(i, 10){
        if(check[i] == 0) nums.emplace_back(i);
    }

    search(0);
    cout << min_val << endl;
}

Measured memory_bytes: 256
//ABC152-E Flatten より
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

vector<LLi> pri={1, 2, 3};
LLi mod=1000000007;

void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}
 
LLi modinv(LLi a) {
    LLi b = mod, u = 1, v = 0;
    while (b) {
        LLi t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}

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

void mplist(LLi x){
	int flag;

	for(int i=5;i<=x;i+=2){
		flag=0;
		for(int j=1;j<(int)pri.size();j++){
			if(i%pri[j]==0){
				flag=1;
				break;
			}
			if(x<pri[j]*pri[j]) break;
		}
		if(flag==0) pri.emplace_back(i);
	}
}

map<LLi, int> rpfac(LLi x){
	int sqx=ceil(sqrt(x));
	//cout<< "sqx=" << sqx SP << sqx*sqx << endl;//
	auto bin = lower_bound(all(pri), sqx);
	int lmt=bin-pri.begin()+1;
	map<LLi, int> tmp;
	//cout<< "lmt=" << lmt SP << pri[lmt] SP << pri[lmt]*pri[lmt] <<endl;//
	if((int)pri.size()<lmt) cout<< "rpfac: pri size is small" <<endl;

	for(int i=1;i<lmt;i++){
		while(x%pri[i]==0){
			x/=pri[i];
			tmp[pri[i]]++;
			//cout<< x <<endl;
			//tmp[0]++;//0番に何個の積でできてるかをメモれる
		}
		if(x==1) break;
	}

	//if(x!=1) cout<< "prime_fac x=" << x <<endl;
	return tmp;
}

LLi defac(map<LLi, int> mp){
	LLi tmp=1;

	/*for(int i=1;i<v.size();i++){
		if(v[i]!=0) tmp*=pow(pri[i], v[i]);
	}*/

	for (auto p : mp) {
  		LLi key = p.first;
  		int value = p.second;
		tmp*=pow(key, value);
      	tmp=tmp%mod;//mod算
	}

	return tmp;
}

int main(){

	//n個からなる整数たちをvに保持
	//mlは素因数分解に使う
	//mpに各数字の素因数分解を保持
	//lcmpが最小公倍数の素因数分解を表すmap
	LLi n, lc, ml, ans=0;
  	vector<LLi> v;
	map<LLi, int> mp, lcmp;
  
  	cin>> n;
  	v.resize(n);
  	rep(i, n) cin>> v[i];
  
	//v[i]<=1e6 より1e3までの素数列挙
  	mplist(101000);
  
	//n個の要素についてlcmを求める
  	rep(i, n){
		//素数リストpriを用いて素因数分解
  		mp=rpfac(v[i]);
		//v[i]が√v[i]を超える約数を持っていた場合の処理
  		ml=defac(mp);
      	if(v[i]!=ml) mp[v[i]/ml]++;
      
	  	//mpの各keyに対する最大の指数を求めていくことが原理的に最小公倍数を求める行為になる
		//v={2, 4, 6} のとき、
		//key=2の指数は{1, 2, 1}でmax=2
		//key=3の指数は{0, 0, 1}でmax=1
		//（補足として）key=5はmax=0
		//それぞれのmaxを合わせると2^2*3^1*5^0=12となり、これがlcmとなる
      	for (auto p : mp) {
  			auto key = p.first;
  			auto value = p.second;
          	lcmp[key]+=value;
        }
	}
  	
  	cout<< lcmp[2] << endl;
  
	return 0;
}


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

#define forn(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define PrintArray(a,n) for(int i=0;i<n;i++) cout << a[i] << " "; cout << endl;
#define CopyArray(a,temp,n) for(int i=0;i<n;i++) temp[i]=a[i];
#define InputArray(a,n) for(int i=0;i<n;i++) cin >> a[i];
#define MAX(a,b,c) max(max(a,b),c)
#define SumInRange(a,b) ((b*(b+1))/2)-(((a-1)*(a))/2)
#define Different_Random srand(time(NULL))
#define Random(a,b) (rand()%((b+1)-a))+a
#define __delete(v,n) v.erase(remove(v.begin(),v.end(),n),v.end())

#define Cases  cout << "Case " << ++Case << ": ";
#define __test int tt; int Case=0; cin >> tt; while(tt--)
#define newline cout << "\n";

#define read(x)    freopen(#x, "r", stdin)
#define write(x)   freopen(#x, "w", stdout)

#define all(x)     x.begin(), x.end()
#define dbg(args...)    {string sss(#args);sss+=',';cerr<<"-->";debugger::call(all(sss), args);cerr<<"\n";}
#define dbgA(A, n)      {cerr<<"-->"<<#A<<"=(";forn(i, n)cerr<<A[i]<<" ";cerr<<")\n";}
#define dbgA2(A, n, m)  {cerr<<"-->"<<#A<<"=\n";forn(i, n){forn(j, m){cerr<<setw(4)<<A[i][j]<<" ";}cerr<<"\n";}cerr<<"\n";}

struct debugger{
    typedef string::iterator si;
    static void call(si it, si ed) {}
    template<typename T, typename ... aT>
    static void call(si it, si ed, T a, aT... rest) {
        string b;
        for(; *it!=','; ++it) if(*it!=' ')b+=*it;
        cerr << b << " = " << a << " ";
        call(++it, ed, rest...);
    }
};

template<typename T>
T Max(T a) {return a;}

template<typename T, typename... Args>
T Max(T a, Args... args){ return a > Max(args...)? a : Max(args...);}

template<typename T>
T Min(T a) {return a;}

template<typename T, typename... Args>
T Min(T a, Args... args){ return a < Min(args...)? a : Min(args...);}


//int dx[] = {1, -1, 0, 0, -1, 1, -1, 1};
//int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
//int knight_x[] = {2, 2, -2, -2, 1, 1, -1, -1};
//int knight_y[] = {1, -1, 1, -1, 2, -2, 2, -2};

/*
cout.precision(x);
cout << fixed;
*/

typedef long long int ll;
typedef unsigned long long int ull;
const double GOLD = (1.0 + sqrt(5.0))/2.0;
const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;
const double PI = 3.141592653589793;
const double E = 2.718281828459045;

ll expo(ll a, ll n)
{
    ll result = 1;
    while(n)
    {
        if(n%2) result*=a;
        a*=a; n/=2;
    }
    return result;
}

ll mod_expo(ll x,ll y,ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1) res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

int main()
{
    #ifdef TarekHasan
        read(input.txt);
    #endif // TarekHasan
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    long long int a,b,c,d; cin >> a >> b >> c >> d;

    cout << max({b*d,c*a,a*d,c*b}) << endl;

    cerr << "time = " << clock() << " ms" << '\n';
    return 0;
}



Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main(){
    string s; cin>>s;
    vector<int> vs = vector<int>(s.length());
    for(int i=0;i<vs.size();++i){
        vs[i] = s[i]-'0';
    }
    int mini = 1000000;
    for(int i=0;i<vs.size()-2;++i){
        int now = abs(753 - vs[i]*100 - vs[i+1]*10 - vs[i+2]);
        if(now < mini) mini = now;
    }cout<<mini<<endl;
    return 0;
}

Measured memory_bytes: 256