akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>

using namespace std;

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

    int ans[N];
    for (int i = 0; i < N; i++) {
        int temp = -1;
        for (int j = N-1-i; j >= 0; j--) {
            if (j+1 == b[j]) {
                temp = j+1;
                break;
            }
        }
        if (temp == -1) {
            cout << -1 << endl;
            return 0;
        }
        ans[i] = temp;
        for (int j = temp-1; j < N-i-1; j++) {
            b[j] = b[j+1];
        }
        b[N-i-1] = -1;
    }

    for (int i = N-1; i >= 0; i--) {
        cout << ans[i] << endl;
    }
    return 0;
}


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

#define ll long long

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define alll(it,A) for(it=A.begin();it!=A.end();it++)

#define err1(a) cout<<a<<endl
#define err2(a,b) cout<<a<<" "<<b<<endl
#define err3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl

#define mp make_pair
#define pb push_back
#define all(A)  A.begin(),A.end()
#define ft first
#define sd second

#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>

const ll N=100005;
const ll M = 1000000007;

ll dp[N];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,w;cin>>n>>w;
    memset(dp,M,sizeof(dp));
    dp[0]=0;
    rep(i,0,n){
    	ll a,b;
    	cin>>a>>b;
    	repb(j,N,b)	dp[j]=min(dp[j],dp[j-b]+a);
    }
    //rep(i,0,1000)	cout<<dp[i]<<" ";cout<<endl;
    ll ans=0;
    rep(i,0,N){
    	if(dp[i]<=w)   ans=i;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 1024
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const ll INF=1e+18;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

const ll MAX=5000;
int main(){
    ll N,M,S;
    cin>>N>>M>>S;
    vector<vector<ll>> G(N);
    vector<vector<ll>> A(N,vector<ll>(N,INF));
    vector<vector<ll>> B(N,vector<ll>(N,INF));
    vector<ll> C(N);
    vector<ll> D(N);
    REP(i,M){
        ll u,v,a,b;
        cin>>u>>v>>a>>b;
        u--;
        v--;
        G[u].push_back(v);
        G[v].push_back(u);
        A[u][v]=a;
        A[v][u]=a;
        B[u][v]=b;
        B[v][u]=b;
    }

    REP(i,N){
        cin>>C[i]>>D[i];
    }

    if(S>=MAX) S=MAX;
    vector<vector<ll>> dp(N,vector<ll>(MAX+1,INF));
    dp[0][S]=0;

    //ダイクストラ O(ElogV)
    priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> que;

    // 初期条件 (頂点 0 を初期ノードとする)
    que.push(make_pair(0,make_pair(0,S))); // 0 を橙色頂点にする

    // 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        pair<ll,pair<ll,ll>> q = que.top(); // 優先度キューから先頭頂点を取り出す
        que.pop();
        ll time=q.first;
        ll v=q.second.first;
        ll s=q.second.second;

        if(time>dp[v][s]) continue;
        ll ns=s+C[v];
        ll ntime=time+D[v];

        // 補給
        ns=s+C[v];
        if(ns<=MAX&&dp[v][ns]>ntime){
            dp[v][ns]=ntime;
            que.push(make_pair(ntime,make_pair(v,ns)));
        }
        // 移動
        for (ll nv : G[v]) {
            ns=s-A[v][nv];
            ntime=time+B[v][nv];
            if(ns>=0&&dp[nv][ns]>ntime){
                dp[nv][ns]=ntime;
                que.push(make_pair(ntime,make_pair(nv,ns)));
            }
        }

    }

    REP2(i,1,N){
        ll ans=INF;
        REP(j,MAX+1){
            ans=min(ans,dp[i][j]);
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 11500
//CODEFORCES:-
//coded by AMAN BHARTI NIT PATNA
//ALL RIGHTS RESERVED
//ECE 2K18

#include<bits/stdc++.h>
using namespace std;

//#define home
#define TASK "soln"
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define pb push_back
#define ll long long int
#define br cout<<endl;
#define fo for(int i=0;i<n;i++)
#define foo for(int i=1;i<=n;i++)
#define mod 1000000007

int dp[1000000];

int cal(int a[],int n,int k){
    if(n==0||n==1)return 0;

    if(dp[n]!=-1)return dp[n];

    int ans =INT_MAX;

    for(int i=1;i<=k;i++){
        if(n-i<1)break;
        ans = min(ans,abs(a[n]-a[n-i])+cal(a,n-i,k));
    }

    return dp[n] = ans;
}

void solve(){
    memset(dp,-1,sizeof(dp));
    int n,k;
    cin>>n>>k;
    int a[n+1];
    foo{cin>>a[i];}

    cout<<cal(a,n,k);
    br;    
}

int main(){
	#ifdef home
        assert(freopen(TASK".in","r",stdin));
        assert(freopen(TASK".out","w",stdout));
    #endif

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

    // int t;
    // cin>>t;
    // while(t-->0)
    solve();

    #ifdef home
        eprintf("Time: %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
    #endif

    return 0;
}

Measured memory_bytes: 15700
#include<stdio.h>
int A[1000];


int main(){
	int n,i,j,v;
	scanf("%d",&n);
	
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
	}
	
	
	
	for(i=0;i<n;i++){
		v = A[i];
		j=i-1;
		while(j>=0 && A[j]>v){
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = v;
		
		for(j=0;j<n-1;j++)printf("%d ",A[j]);
		printf("%d\n",A[n-1]);
	}
	
	
	
	
	return 0;
}

Measured memory_bytes: 1852
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define SZ(x)  (int)x.size()
#define SP(x)  setprecision((int)x)


using namespace std ;
typedef long long ll;
using Graph = vector<vector<int>>;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<string> vstr;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;} //最小公倍数

//-------------------------------------------------
// 
void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}


//-------------------------------------------------
// メモ
/*






*/
//-------------------------------------------------


int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n ;
  cin >> n ;
  vint cnt(100000+1,0) ;
  int ans = 0 ;
  REP(i,n){
    int a ;
    cin >> a ;
    if(a>100000){
      ans++ ;
    }
    else{
      cnt[a]++ ;
    }
  }
  FOR(i,1,100000+1){
    if(cnt[i]>=i){
      ans += cnt[i] - i ;
    }
    else{
      ans += cnt[i] ;
    }
  }
  
  cout << ans <<endl ;
  
  
  
  return 0 ;
}




Measured memory_bytes: 640
#include<stdio.h>

int main(){
	int res;
	int N,M;
	res=scanf("%d %d",&N,&M);
	int A[M];
	for(int i=0;i<M;i++){
		res=scanf("%d",&A[i]);
	}
	int days=N;
	for(int i=0;i<M;i++){
		days-=A[i];
		if(days<0){
			printf("-1\n");
			return 0;
		}
	}
	printf("%d\n",days);
	return 0;
}


Measured memory_bytes: 1708
//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
#include<cstring>
#include<sstream>
#include <iomanip>

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	printf
#define sf			  scanf
#define pb(a)         push_back(a)
#define mp			make_pair
#define fi			 first
#define se			 second
#define for0(i,n)        for(int i=0;i<n;i++)
#define for1(i,n)        for(int i=1;i<=n;i++)
#define forab(i,a,b)       for(int i=a;i<=b;i++)
#define lcm(a, b)     ((a)*((b)/gcd(a,b)))
#define sq(a)		   (a)*(a)
#define nw				"\n"
#define abs(x)		fabs(x)
#define pcase(z,x)    cout<<"Case "<<z<<": "<<x<<"\n"

int main()
{
	int k,x,a,b;
	cin>>k>>x;
	a = x-k;
	for1(i,k){
		a++;
		cout<<a<<" ";
		}
	a++;
	for1(i,k-1){
		cout<<a<<" ";
		a++;
		}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main(){
    fast;
int cnt=0,a,n,i;
cin>>n;
for(i=1;i<=n;i++){
    cin>>a;
if(a%2==1 && (a*a)%2==1 && i%2==1 )cnt++;
}
cout<<cnt<<endl;
}




Measured memory_bytes: 3572
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
typedef long long int ll;
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll dx[]={-1,-1,-1,1,1,1,0,0};
ll dy[]={-1,0,1,-1,0,1,-1,1};
string board[50];
int main(){
  int X,Y;
  cin>>X>>Y;
  rep(i,X) cin>>board[i];
  rep(i,X){
    rep(j,Y){
      int cnt=0;
      if(board[i][j]=='.'){
        rep(k,8){
          int x=i+dx[k];
          int y=j+dy[k];
          if(0<=x && x<X && 0<=y && y<Y && board[x][y]=='#') cnt++;
        }
        board[i][j]='0'+cnt;
      }
    }
  }
  rep(i,X) cout<<board[i]<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;

	if (n == m) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}

int main()
{
	cout<<(read()+read()/2)<<endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=100005;
int n,a[N],b[N];
int nd,S,T,ida[N],idb[N];
int v[2][2],ans,vis[N];
int getid(int *a,int *v){
	For(i,1,n) vis[i]=0;
	For(i,1,n) if (!vis[i]){
		int x=i; ++nd;
		for (;;){
			vis[x]=1; v[x]=nd;
			if (vis[x=a[x]]) break;
		}
	}
}
struct edge{
	int to,next,f;
}e[N*50];
int head[N*2],cur[N*2],tot=1;
void add(int x,int y,int f){
	e[++tot]=(edge){y,head[x],f};
	head[x]=tot;
	e[++tot]=(edge){x,head[y],0};
	head[y]=tot;
}
int dis[N*2],q[N*2];
bool bfs(){
    For(i,1,T) dis[i]=-1;
    int h=0,t=1; q[1]=S; dis[S]=0;
    while (h!=t){
        int x=q[++h];
        for (int i=head[x];i;i=e[i].next)
            if (e[i].f&&dis[e[i].to]==-1){
                dis[e[i].to]=dis[x]+1;
                if (e[i].to==T) return 1;
                q[++t]=e[i].to;
            }
    }
    return 0;
}
ll dfs(int x,ll flow){
    if (x==T) return flow;
    ll k,rest=flow;
    for (int &i=cur[x];i&&rest;i=e[i].next)
        if (dis[e[i].to]==dis[x]+1&&e[i].f){
            k=dfs(e[i].to,min(rest,(ll)e[i].f));
            e[i].f-=k; e[i^1].f+=k; rest-=k;
            if (!rest) break;
        }
    if (rest) dis[x]=-1;
    return flow-rest;
}
int main(){
	scanf("%d",&n);
	For(i,1,n) scanf("%d",&a[i]),++a[i];
	For(i,1,n) scanf("%d",&b[i]),++b[i];
	getid(a,ida);
	getid(b,idb);
	S=++nd; T=++nd;
	For(i,1,n){
		if (a[i]==i&&b[i]==i) ans++;
		else if (a[i]==i) add(idb[i],T,1);
		else if (b[i]==i) add(S,ida[i],1);
		else{
			add(idb[i],ida[i],1);
			if (a[i]==b[i]) add(ida[i],idb[i],1);
		}
	}
	for (;bfs();){
		For(i,1,nd) cur[i]=head[i];
		ans+=dfs(S,1<<30);
	}
	printf("%d\n",n-ans);
}

Measured memory_bytes: 11520
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
  int n, l;
  string s[110];
  cin >> n >> l;
  for(int i=0; i<n; i++){
    cin >> s[i];
  }
  sort(s, s+n);
  for(int i=0; i<n; i++){
    cout << s[i];
  }
  cout << endl;
  return 0;
}


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

#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define ALL(v) (v).begin(), (v).end()
#define INF 1e9

using namespace std;

int main(){
  int n;
  cin >> n;
  REP(i, n){
    int y, m, d, days;
    cin >> y >> m >> d;
    days = 200 * (1000-y-1) + 20 * (10 - m) + 20 - d + 1;
    int leap = 1000 / 3 - (y-1) / 3 - 1;
    days -= 10 * leap;
    if(y % 3 == 1) days -= 5;
    if(y % 3 != 0) days -= 5 - (m-1)/2;
    cout << days << endl;
  }
}

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

#ifdef LOCAL
#define debug(var) cerr << #var << " = " << var << endl;
#else
#define debug(var)
#endif

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

const int N = 1e5+23;
const long long inf = 1e15;

pair<int, int> xs[N];
pair<int, int> ys[N];
vector<pair<int, int>> g[N];

long long prim(int n) {
	long long total = 0;
	vector<pair<long long, int>> min_e(n, {inf, -1});
	min_e[0].first = 0;
	set<pair<long long, int>> q;
	q.insert({0, 0});
	vector<bool> selected(n, false);
	for (int i = 0; i < n; ++i) {
		assert(!q.empty());
		int v = q.begin()->second;
		selected[v] = true;
		total += q.begin()->first;
		q.erase(q.begin());
		for (const auto &e: g[v]) {
			if (selected[e.first] || e.second >= min_e[e.first].first) continue;
			q.erase({min_e[e.first].first, e.first});
			min_e[e.first] = {e.second, v};
			q.insert({e.second, e.first});
		}
	}
	return total;
}

void solve() {
	int n; scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &xs[i].first, &ys[i].first);
		xs[i].second = ys[i].second = i;
	}
	sort(xs, xs+n);
	sort(ys, ys+n);
	for (int i = 1; i < n; ++i) {
		g[xs[i].second].emplace_back(xs[i-1].second, xs[i].first-xs[i-1].first);
		g[xs[i-1].second].emplace_back(xs[i].second, xs[i].first-xs[i-1].first);
		
		g[ys[i].second].emplace_back(ys[i-1].second, ys[i].first-ys[i-1].first);
		g[ys[i-1].second].emplace_back(ys[i].second, ys[i].first-ys[i-1].first);
	}
	printf("%lld", prim(n));
}

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


Measured memory_bytes: 13312
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
//			String str = br.readLine();
//			//int N = Integer.parseInt(str);
//			//StringBuilder sb = new StringBuilder();
//			String[] s = str.split(" ",0);
//			int N = Integer.parseInt(s[0]);
//			int M = Integer.parseInt(s[1]);
//			int K = Integer.parseInt(s[2]);
//			int re = 0;
//			for(int i = 0;i< N+1;i++) {
//				if(re == 1) break;
//				for(int j = 0;j<M+1;j++) {
//					if(i*M+j*N-2*(i+j-1) == K){
//						System.out.println("Yes");
//						re++;
//						break;
//					}
//					if(i==N-1 && j==M-1){
//						System.out.println("No");
//					}
//				}
//			}
			String str = br.readLine();
			if(str.length()< 4) {
				System.out.println("No");
			}else if(str.substring(0, 4).equals("YAKI")) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
//			System.out.println(sb);
//			long max  = 1000000007;
		}catch (Exception e) {
			System.exit(0);
		}
	}

}


Measured memory_bytes: 21076
#include<iostream>
#include<vector>
#include<queue>
#include<functional>

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

int N, Q, K;
vector<vector<P>> e;
ll d[100000];

void djk() {
	for (int i = 0; i < N; i++)d[i] = 1000000000000000;
	d[K] = 0;
	priority_queue<P, vector<P>, greater<P>> pq;
	pq.push(P(0, K));
	while (pq.size()) {
		auto tmp = pq.top(); pq.pop();
		if (tmp.first > d[tmp.second])continue;
		for (int i = 0; i < e[tmp.second].size(); i++) {
			auto next = e[tmp.second][i];
			if (d[next.first] > d[tmp.second] + next.second) {
				d[next.first] = d[tmp.second] + next.second;
				pq.push(P(d[next.first], next.first));
			}
		}
	}
}

int main() {
	cin >> N;
	e.resize(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		e[a].push_back(P(b, c));
		e[b].push_back(P(a, c));
	}
	cin >> Q >> K;
	K--;
	djk();
	for (int i = 0; i < Q; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		cout << d[a] + d[b] << endl;
	}
	return 0;
}

Measured memory_bytes: 9856
package main

import (
	"fmt"
)

func main() {
	var x, y int
	fmt.Scan(&x, &y)
	a := 0

	for i := 0; i < x; i++ {
		ni := 2 * i
		yo := 4 * (x - i)
		nii := 4 * i
		yoo := 2 * (x - i)
		if ni+yo == y || nii+yoo == y {
			a = 1
		}

	}
	if a == 1 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1752
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;

const int MAXN=400;

LL n,m,ans,cntW,cntB;
bool visited[MAXN][MAXN];
string s[MAXN];

bool avail(int i,int j,char c){
	if(i<0||i>=n||j<0||j>=m) return false;
	if(s[i][j]==c) return false;
	return true;
}

void dfs(int i,int j){
	if(i<0||i>=n||j<0||j>=m) return;
	if(visited[i][j]) return;
	visited[i][j]=true;
	if(s[i][j]=='.') cntW++;
	else cntB++;
	if(avail(i,j-1,s[i][j])) dfs(i,j-1);
	if(avail(i,j+1,s[i][j])) dfs(i,j+1);
	if(avail(i+1,j,s[i][j])) dfs(i+1,j);
	if(avail(i-1,j,s[i][j])) dfs(i-1,j);
}

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>s[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			visited[i][j]=false;
	ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(!visited[i][j]){
				cntB=0;
				cntW=0;
				dfs(i,j);
				ans+=cntB*cntW;
			}
	cout<<ans<<"\n";
} 

Measured memory_bytes: 13092
# include<bits/stdc++.h>
using namespace std;
# define l long long 
# define db double 
# define rep(i,a,b) for(l i=a;i<b;i++)
# define revrep(i,a,b) for(l i=a;i>=b;i--)
# define vi vector<l>
# define pb push_back
# define mp make_pair
# define ss second
# define ff first
# define pii pair<l,l>
# define trvi(v,it) for(vi::iterator it=v.begin();it!=v.end();++it)
# define read(a) freopen(a,"r",stdin)
# define write(a) freopen(a,"w",stdout)
# define io ios::sync_with_stdio(false)
const l MOD=1e9+7;
const l N=3e5+5;
const l INF=1e14;
int main(){
	io;
	l n;
	cin>>n;
	l a[N],b[N];
	rep(i,0,n) cin>>a[i]>>b[i];
	l ans=0;
	revrep(i,n-1,0){
		a[i]+=ans;
		if(a[i]%b[i]) ans+=b[i]-a[i]%b[i];
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 1792
import itertools

N = int(input())
xylist = [list(map(int,input().split())) for i in range(N)]

jyunlist = [i for i in range(N)]
p_list = list(itertools.permutations(jyunlist))
a = 0
sum = 0
for keiro in p_list:
    for i in range(N-1):
        a = ((xylist[keiro[i+1]][0]-xylist[keiro[i]][0])**2+(xylist[keiro[i+1]][1]-xylist[keiro[i]][1])**2)**(1/2)
        sum += a
ans = sum/len(p_list)

print(ans)

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b; cin>>a>>b;
    cout<<(a+b)%24<<endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ff first 
#define ss second
#define mod 1000000007
#define lim 100005
#define nfs_mw ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int rsz[lim] = {};

int main()
{
	// nfs_mw;
	int i,u,n; string s;
	cin>>s;
	n = s.size();

	if((s[0] == '0') || (s[n-1] == '1')){
		cout<<(-1)<<"\n";
		return 0;
	}

	for(i=0; i<n/2; i++) if(s[i] != s[n-i-2]) {
		cout<<(-1)<<"\n";
		return 0;
	}

	rsz[u = 1] = n - 1;

	for(i=(n/2); i; i--)
		if(s[i-1] == '1'){
			rsz[u] -= i;
			cout<<u<<" "<<(u+1)<<"\n";
			rsz[++u] = i-1;
		}

	for(i=u; i; i--)
		while(rsz[i]--)
			cout<<i<<" "<<(++u)<<"\n";		
}

Measured memory_bytes: 1664
n,m=map(int,input().split())
a=[]
for i in range(n):
    a.append([0,0])
b=[]
c=0
d=0
for i in range(m):
    b.append(list(input().split()))
    b[i][0]=int(b[i][0])
a=sorted(a,key=lambda x:x[0])
for i in range(m):
    if b[i][1]=='WA':
        if a[b[i][0]-1][0]==0:
            a[b[i][0]-1][1]+=1
    else:
        if a[b[i][0]-1][0]==0:
            a[b[i][0]-1][0]=1
for i in range(n):
    c+=a[i][0]
    if a[i][0]==1:
        d+=a[i][1]
print(c,d)

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

int main()
{
	int i, n, maxm=0;
	cin >> n;
	int ans[n+1], h[n+1];
	ans[0]=h[0]=0;
	for(i=1; i<=n; i+=1)
		cin >> h[i];
	ans[n]=0;
	for(i=n-1; i>=1; i-=1)
	{
		if(h[i]>=h[i+1])
			ans[i]=ans[i+1]+1;
		else
			ans[i]=0;
	}
	for(i=1; i<=n; i+=1)
		maxm=max(maxm, ans[i]);
	cout << maxm << endl;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include<limits>
#include<iomanip>
#include<cassert>

using namespace std;

typedef long long ll;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n-1;i >= 0;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second

const long double pi = 3.141592653589793;
const int mod = 1e9 + 7;

vector<ll> inv{0, 1}; // ith index will store (1/i)%mod
vector<ll> finv{1, 1}; // ith index will store (1/i!)%mod
vector<ll> fact{1, 1}; // ith index will store (i!)%mod

void populate(int n) {
    for(int i = 2;i < n;i++) {
        fact.pb((i*fact[i-1])%mod);
        inv.pb(mod-((inv[mod%i]*(mod/i))%mod));
        finv.pb((finv[i-1]*inv[i])%mod);
    }
}

ll P(int n, int r) {
  return fact[n]*finv[n-r]%mod;
}

ll C(int n, int r) {
  return P(n, r)*finv[r]%mod;
}

int main() {

 // freopen("input.in","r",stdin);
 // freopen("output.out","w",stdout);

 ios_base::sync_with_stdio(false);
 cin.tie(NULL);

 int n, m;cin >> n >> m;
 populate(m+1);

 ll ans = 0;
 rep(k, n+1) {
   if(k & 1) {
     (ans -= C(n,k)*P(m,k)%mod*P(m-k,n-k)%mod*P(m-k,n-k)%mod)%=mod;
     if(ans < 0) ans += mod;
   } else {
     (ans += C(n,k)*P(m,k)%mod*P(m-k,n-k)%mod*P(m-k,n-k)%mod)%=mod;
   }
 }
 cout << ans << endl;

 return 0;
}


Measured memory_bytes: 15156
#include<bits/stdc++.h>
#define vpair(d) vector<pair<d, d> >

using namespace std;


int main()
{
	int a, b;
	cin >> a >> b;
	
	int c;
	bool flag = false;
	for( c = 1; c <= 3; c ++){
		if((a*b*c)%2 != 0){
			flag = true;
			break;
		}
	}
	if(flag)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

#include <cstdio>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

/*================================================
	Dijkstra
================================================*/
#define COST_TYPE int
#define NMAX (1000001)
#define INF (100000000)
vector<pair<COST_TYPE, int> > G[NMAX];
COST_TYPE cost[NMAX];
bool done[NMAX] = { false };

void dijkstra(int root)
{
	priority_queue<pair<COST_TYPE, int>, vector<pair<COST_TYPE, int> >, greater<pair<COST_TYPE, int> > > PQ;
	pair<COST_TYPE, int> current;	/* first: cost, second: index */
	COST_TYPE next_cost;
	int current_index, next_index;

	rep(i, NMAX) {
		done[i] = false;
		cost[i] = INF;
	}

	cost[root] = 0;
	PQ.push(make_pair(0, root));

	while (!PQ.empty()) {
		current = PQ.top();
		PQ.pop();

		current_index = current.second;

		if (done[current_index]) continue;
		done[current_index] = true;

		rep(i, G[current_index].size()) {
			next_index = G[current_index][i].second;
			next_cost = G[current_index][i].first;

			if ((!done[next_index])
				&& (cost[next_index] > cost[current_index] + (COST_TYPE)next_cost)) {
				cost[next_index] = cost[current_index] + (COST_TYPE)next_cost;
				PQ.push(make_pair(cost[next_index], next_index));
			}
		}
	}
}

int main()
{
	int n, s, t, w;
	int root = 0, root_cost = 0, ans = 0;

	cin >> n;
	rep(i, n - 1) {
		(void)scanf("%d %d %d", &s, &t, &w);
		G[s].push_back(make_pair(w, t));
		G[t].push_back(make_pair(w, s));
	}
	
	dijkstra(0);

	rep(i, n) {
		if (cost[i] > root_cost) {
			root_cost = cost[i];
			root = i;
		}
	}

	dijkstra(root);

	rep(i, n) {
		if (cost[i] > ans) ans = cost[i];
	}

	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 35588
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<algorithm>
#define M_PI 3.14159265358979323846
#define ll long long
using namespace std;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
ll lcm(int a, int b) {
	return (ll)a * b / gcd(a, b);
}
int main() {
	int k;
	string s;
	cin >> k;
	cin >> s;
	if (k >= s.size()) cout << s << endl;
	else cout << s.substr(0, k) + "..." << endl;
	return 0;
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ld long double

using namespace std;

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

    ll rC = 0; 

    vector<char> A;

    char temp;
    for(int i = 0; i < n; i++){
    	cin >> temp;

    	if(temp == 'R') rC++;
    	//if(temp == 'W') wC++;

    	A.pb(temp);
    }

    ll count  = 0;
    for(int i = 0; i < rC; i++){
    	if(A[i] == 'W') count++;
    }

    cout << count << endl;


   

    return 0;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
int N, Q;
struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;
 
public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);
 
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }
 
    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
 
    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
 
    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        if(b <= l || r <= a) return 0;
        eval(k, l, r);
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};
int main() {
    cin >> N >> Q;
    LazySegmentTree seg( vector<ll>(N, 0) );
    for(int i=0; i<Q; i++) {
        int query; cin >> query;
        if(query == 0) {
            int s, t, x; cin >> s >> t >> x;
            seg.add(s-1, t, x);
        }
        else {
            int s, t; cin >> s >> t;
            cout << seg.getsum(s-1, t) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 7580
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

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

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
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;
}
//

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

  int a, b, ans[4] = {0};
  cin >> a >> b;
  for (int i = 1; i <= 3; i++) {
    if (i == a) continue;
    if (i == b) continue;
    cout << i << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define inf (ll)1e9
#define mod (ll)(1e9+7)
#define d(x) cerr<<#x<<"="<<x<<endl;
#define p(x) cout<<(x)<<endl
#define ps(x) cout<<(x);
#define pk(x) cout<<(x)<<" ";
#define pfix(d,x) cout << fixed << setprecision(d) << x << endl;
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define minel(v) *min_element(all(v))
#define minind(v) distance((v).begin(), min_element(all(v)))
#define maxel(v) *max_element(all(v))
#define maxind(v) distance((v).begin(), max_element(all(v)))
#define p2d(v,n,m) rep(i,n){rep(j,m){pk(v[i][j]);}p("");}
#define fi first
#define se second
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll a[100001],b[100001],c[100001],d,n,m,x,y,z,h,w,k,mi=inf,ma=-inf,ans,s,t,l,r,res,tmp,itr,p,q;
bool flag;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dx8[8]={1,1,0,-1,-1,-1,0,1},dy8[8]={0,1,1,1,0,-1,-1,-1};
char cha;
string st;
typedef map<ll, ll> imap;
typedef pair<ll, ll> P;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<pair<ll,ll> > VP;
P pa;


int main(){
    cin>>n>>k;
    vector<double> ve(n);
    rep(i,n)cin>>ve[i];
    double ans=0,sum=0,maxsum=0,newsum;
    rep(i,k){
        sum+=(ve[i]+1)/2;
    }
    rep(i,k,n){
        newsum=sum-(ve[i-k]+1.0)/2.0+(ve[i]+1.0)/2.0;
        if(maxsum<newsum){
            maxsum=newsum;
            l=i-k+1;
        }
        sum=newsum;
    }
    rep(i,l,l+k){
        ans+=(double)(ve[i]+1)/2;
    }
    pfix(12,ans);
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100001
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

pair<int,int> a[1001];
pair<int,int> ans;
int b[1001], c[1001];
bool comp(pair<int,int> x, pair<int,int> y){
	return x.fi > y.fi;
}

int main(){
	int n, m, t;
	ans.se = 0;
	scanf("%d%d", &n, &m);
	rrep(i,n){
		scanf("%d", &t);
		a[i].fi = t;
		a[i].se = i;
	}
	rrep(i,m)scanf("%d", &b[i]);
	sort(a+1, a+n+1);
	//rrep(i,n)printf("%d %d\n", a[i].fi, a[i].se);
	for(int i = 1;i <= m;i++){
		t = INF;
		rrep(j,n)if(a[j].fi <= b[i])t = min(t, a[j].se);
		c[t]++;
		if(c[t] > ans.se){
			ans.fi = t;
			ans.se = c[t];
		}
		//printf("%d ", t);
	}
	printf("%d\n", ans.fi);
	return 0;
}

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<vector<int>> ki(n);
    int a, b;
    for(int i = 0; i < n-1; ++i) {
        cin >> a >> b;
        a--, b--;
        ki[a].push_back(b);
        ki[b].push_back(a);
    }
    int p, x, cnt[n+1] = {0};
    for(int i = 0; i < q; ++i) {
        cin >> p >> x;
        cnt[p-1] += x;
    }

    vector<int> dist(n, -1);
    queue<int> que;
    dist[0] = 0;
    que.push(0);

    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(int nv : ki[v]) {
            if(dist[nv] != -1) continue;

            dist[nv] = dist[v] + 1;
            cnt[nv] += cnt[v];
            que.push(nv);
        }
    }

    for(int i = 0; i < n; ++i) {
        cout << cnt[i] << ' ';
    }
    
    cout << '\n';

    return 0;
}


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

int main()
{
   ll a,b,c,t;
   cin>>a>>b>>c;
   cin>>t;
   ll r=0;
   while(r<t){
   	if(b>a&&c>b){
   		break;
	   }
   	if(b<=a){
   		b=b*2;r++;
	   }
	else if(c<=b){
		c=c*2;r++;
	}   
   }
   if(b>a&&c>b){
   	cout<<"Yes";
   }
   else{
   	cout<<"No";
   }
    return 0;
}

Measured memory_bytes: 3592
import java.util.*;

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

		while(true){
			double p = Math.sqrt(sc.nextDouble());
			int n = sc.nextInt();
			if(p == 0 && n == 0) break;

			double max = 1 / (double)n;
			double min = (double)n;
			int max_p = 1;
			int max_q = n;
			int min_p = n;
			int min_q = 1;

			for(int i=1;i<=n;i++){
				int j1 = (int)Math.floor(i * p);
				int j2 = (int)Math.ceil(i * p);

				if(j1 <= n && (double)j1/i > max){
					max = (double)j1/i;
					max_p = j1;
					max_q = i;
				}
				if(j2 <= n && (double)j2/i < min){
					min = (double)j2/i;
					min_p = j2;
					min_q = i;
				}
			}

			System.out.printf("%d/%d %d/%d\n",min_p,min_q,max_p,max_q);
		}
	}
}

Measured memory_bytes: 13000
// 2011/09/23 Tazoe

#include <iostream>
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	int S[100000];
	S[0] = 0;
	for(int i=1; i<n; i++)
		cin >> S[i];

	int sum = 0;
	int I = 0;
	for(int i=0; i<m; i++){
		int a;
		cin >> a;

		if(a>0){
			for(int j=0; j<a; j++){
				I++;
				sum += S[I];
			}
		}
		else{
			a = -a;
			for(int j=0; j<a; j++){
				sum += S[I];
				I--;
			}
		}

		sum %= 100000;
	}

	cout << sum << endl;

	return 0;
}

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

using namespace std;

unsigned int v[1001];
unsigned int w[1001];
unsigned int dp1[10001];
unsigned int dp2[10001];

int main()
{
	unsigned int n, W;

	unsigned int* pDp1;
	unsigned int* pDp2;
	cin >> n >> W;
	for (unsigned int i = 0; i < n; ++i) {
		cin >> v[i] >> w[i];
	}

	for (unsigned int i = 0; i < n; ++i) {
		if (i % 2 == 0) {
			pDp1 = dp1;
			pDp2 = dp2;
		} else {
			pDp1 = dp2;
			pDp2 = dp1;
		}
		for (unsigned int j = 0; j <= W; ++j) {
			if (j >= w[i]) {
				pDp2[j] = max(pDp1[j - w[i]] + v[i], pDp1[j]);
			} else {
				pDp2[j] = pDp1[j];
			}
		}
	}

	cout << pDp2[W] << endl;
	return 0;
}



Measured memory_bytes: 3204
n,k=map(int,input().split())
l=list(map(int,input().split()))
sl=sorted(l)
ten=0
jiten=0
for i in range(n):
    for j in range(n):
        if l[i]>l[j]and i<j:ten+=1
        if l[i]<l[j]:jiten+=1
print((ten*k+jiten*(k*(k-1))//2)%1000000007)


Measured memory_bytes: 3188
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class ACirclePond {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      double r; cin >> r;
      cout << setprecision(10) << fixed;
      cout << r*PI*2 << endl;
    }
};

signed main() {
  ACirclePond solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3760
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace CSharp
{
    static class Program
    {
        static void Main(string[] args)
        {
            int n, k;
            ReadInt(out n, out k);
            int ans = n - k + 1;
            Console.WriteLine(ans);
        }

        #region Helpers

        static int[] ReadIntArray() => Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
        static long[] ReadLongArray() => Console.ReadLine().Split().Select(s => long.Parse(s)).ToArray();

        static int[] ReadLineIntArray(int count) => Enumerable.Repeat(0, count).Select(_ => int.Parse(Console.ReadLine())).ToArray();
        static long[] ReadLineLongArray(int count) => Enumerable.Repeat(0, count).Select(_ => long.Parse(Console.ReadLine())).ToArray();

        static string ReadString() => Console.ReadLine();
        static int ReadInt() => int.Parse(Console.ReadLine());
        static long ReadLong() => long.Parse(Console.ReadLine());

        static void ReadInt(out int first)
        {
            var array = ReadIntArray();
            first = array[0];
        }

        static void ReadInt(out int first, out int second)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
        }

        static void ReadInt(out int first, out int second, out int third)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadInt(out int first, out int second, out int third, out int fourth)
        {
            var array = ReadIntArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        static void ReadLong(out long first)
        {
            var array = ReadLongArray();
            first = array[0];
        }

        static void ReadLong(out long first, out long second)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
        }

        static void ReadLong(out long first, out long second, out long third)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
        }

        static void ReadLong(out long first, out long second, out long third, out long fourth)
        {
            var array = ReadLongArray();
            first = array[0];
            second = array[1];
            third = array[2];
            fourth = array[3];
        }

        #endregion
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h> // {{{
// clang-format off
#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define TEN(n) ((ll)(1e##n))
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
#define USE1(T) template <typename T> inline
#define USE2(T, U) template <typename T, typename U> inline
#define mygc(c) (c) = getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

template <typename T> using duo = std::pair<T, T>;
template <typename T> using vec = std::vector<T>;
using ll = long long;
using pii = duo<int>;
USE2(T,U)bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE2(T,U)bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE1(T=int)T in(){T x;std::cin>>x;return x;}
USE1(T=int)vec<T>in(int n){vec<T>v;v.reserve(n);rep(i,n)v.pb(in<T>());return v;}
USE1(T)vec<std::pair<T,int>>zipi(const vec<T>&x,int s=0){int N=x.size();vec<std::pair<T,int>>v;v.reserve(N);rep(i,N)v.pb(x[i],s+i);return v;}
USE1(T)vec<T>ndvec(T v,int n){return vec<T>(n,v);}
USE2(T,...Ts)auto ndvec(T v,int n,Ts...ns)->vec<decltype(ndvec(v,ns...))>{return ndvec(ndvec(v,ns...),n);}
USE1(T)void pr(T x){std::cout<<x<<'\n';}
USE2(T,...Ts)void pr(T x,Ts...xs){std::cout<<x<<' ';pr(xs...);}
USE1(T=int)T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
USE1(T=int)void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
// clang-format on
// }}}
struct IoSetup { // {{{
  IoSetup() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.precision(10);
    std::cerr.precision(10);
  }
} iosetup; //}}}
using namespace std;
const int inf = 1001001001;
const ll infl = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  int N = in();
  pr(N * (N + 1) / 2);
  return 0;
}


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

int main() {
  
  string C1, C2;
  cin >> C1 >> C2;
  
  if (C1.at(0) == C2.at(2) && C1.at(1) == C2.at(1) && C1.at(2) == C2.at(0)) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
  
return 0;
}

Measured memory_bytes: 3640
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>


long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;
string s;
int k;



int main(){

cin>>s;
cin>>k;
int len=s.size();
map<string,int>ans;
string v;
for(int i=0;i<len;i++){
    v.clear();
    for(int l=0;(i+l<len) && (l<k) ;l++){
        v.push_back(s[i+l]);
        ans.insert(make_pair(v,2));
    }
}
auto iter=ans.begin();
int p=1;
while(p<=k){
    if(p==k){
        cout<<iter->first<<endl;
    }
    iter++;
    p++;
}
 return 0;
}

Measured memory_bytes: 1920
#include<iostream>
#include<vector>
#include<string>
#include<math.h> 
#include<algorithm> 
#include<stdio.h> 
#include<sstream>
#include<fstream>  
using namespace std; 
typedef long long ll; 
typedef long double ld; 

int ceil(int a, int m){
    // division of a and m
    if(a % m == 0){
        return a/m; 
    }
    else{
        return a/m + 1; 
    }
}

vector<int> sort(vector<int> arr){
    sort(arr.begin(), arr.end()); 
    return arr; 
}





int main(){

char nl = '\n'; 
char bl = ' ';
/*
For array arr use the following preamble to sort
int diff = sizeof(arr)/sizeof(arr[0]); 
sort(arr, arr + diff); 

*/
int n,d; 
cin >> n >> d;
vector<pair<int,int> > coord; 
 for(int i = 0; i<n; i++){
 	int a,b;
 	cin >> a >> b; 
 	coord.push_back(make_pair(a,b)); 
 }
 int cnt = 0; 
 for(int i = 0; i<coord.size(); i++){
 	if(pow(coord[i].first,2) + pow(coord[i].second, 2) <= pow(d,2)){
 		cnt++; 
 	}
 }
 cout << cnt; 
}

Measured memory_bytes: 5360
#include <bits/stdc++.h>
#define re return
#define ll long long
#define ld long double
#define f first
#define s second
#define pi acos(-1)
#define oo (int)1e9
#define OO (ll)1e18
#define EPS 1e-7
#define FX(n) fixed<<setprecision(n)
#define mm(o,k) memset(o,k,sizeof o)
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int maxn=505;
bool pal(int x){
    int temp=x;
    stack<int>st;
    while(temp)
        st.push(temp%10),temp/=10;
    while(x){
        if(x%10!=st.top())re 0;
        x/=10;st.pop();
    }
    re 1;
}
int main()
{
    IO;
    int a,b,ans=0;
    cin >> a >> b;
    while(a<=b){
        ans+=pal(a);
        ++a;
    }
    cout<<ans<<endl;
    re 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i;
    cin>>n;
    vector<int>a(n),dp(n);
    for(i=0;i<n;i++)cin>>a[i];
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
    for(i=2;i<n;i++)
    {
        dp[i]=min((dp[i-1]+abs(a[i-1]-a[i])),(dp[i-2]+abs(a[i]-a[i-2])));
    }
    cout<<dp[n-1]<<endl;
    return 0;
}


Measured memory_bytes: 1024
n, m = map(int, input().split())


def make_divisors(num):
    divisors = []
    for i in range(1, m+1):
        if i * i > m:
            break
        if m % i == 0:
            divisors.append(i)
            divisors.append(m // i)
    return divisors

div = make_divisors(num=m)
div.sort()
ans = 1
for x in div:
    if x*n <= m:
        ans = x
print(ans)


Measured memory_bytes: 3060
// Problem : E - Crested Ibis vs Monster
// Contest : AtCoder Beginner Contest 153
// URL : https://atcoder.jp/contests/abc153/tasks/abc153_e
// Memory Limit : 1024.000000 MB 
// Time Limit : 2000.000000 milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor)

// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
using namespace std;
 
#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

ll DP[20004];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int H, N; cin >> H >> N;
	memset(DP, 15, sizeof DP);
	DP[0] = 0;
	while(N--) {
		int dam, cos; cin >> dam >> cos;
		iter(i, dam, 20000) DP[i] = min(DP[i], DP[i-dam]+cos);
	}
	ll mi = DP[20000];
	iter(v, H, 20000) mi = min(mi, DP[v]);
	cout << mi << endl;
}



Measured memory_bytes: 512