akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}

int main() {
	int a, b, c, d,N;
	cin >> N;
	d = N % 10;
	N /= 10;
	c = N % 10;
	N /= 10;
	b = N % 10;
	N /= 10;
	a = N % 10;
	N /= 10;
	if (a + b + c + d == 7) {
		cout << a << "+" << b << "+" << c << "+" << d << "=7" <<endl;
	}
	else if (a + b + c - d == 7) {
		cout << a << "+" << b << "+" << c << "-" << d << "=7" << endl;
	}
	else if (a + b - c + d == 7) {
		cout << a << "+" << b << "-" << c << "+" << d << "=7" << endl;
	}
	else if (a - b + c + d == 7) {
		cout << a << "-" << b << "+" << c << "+" << d << "=7" << endl;
	}
	else if (a + b - c - d == 7) {
		cout << a << "+" << b << "-" << c << "-" << d << "=7" << endl;
	}
	else if (a - b - c + d == 7) {
		cout << a << "-" << b << "-" << c << "+" << d << "=7" << endl;
	}
	else if (a - b + c - d == 7) {
		cout << a << "-" << b << "+" << c << "-" << d << "=7" << endl;
	}
	else if (a - b - c - d == 7) {
		cout << a << "-" << b << "-" << c << "-" << d << "=7" << endl;
	}
	
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
#include <unordered_map>
#include <vector>
#include <utility>
#include <cassert>
#include <algorithm>
#include <cstring>

using namespace std;

vector<int> dp;

int StepCases(int step) {
  if(dp[step] != -1) return dp[step];
  dp[step] = (StepCases(step - 1) + StepCases(step - 2)) % 1'000'000'007;
  return dp[step];
}

int main(int argc, char *argv[]) {
  int N, M;
  cin >> N >> M;
  dp.resize(N + 1, -1);
  dp[0] = 1;
  dp[1] = 1;
  for(int i = 0; i < M; i++){
    int tmp;
    cin >> tmp;
    dp[tmp] = 0;
  }
  cout << StepCases(N) << endl;
  return 0;
}


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

#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
#define INF (1<<29)*2
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define ffor(i, a, b, c) for(i=a;i<=b;i+=c)
#define rep(i, n) for(i=0;i<n;i++)
#define max(a, b) ((a)>(b) ? (a) : (b))
#define min(a, b) ((a)<(b) ? (a) : (b))
#define bit(n) (1LL<<(n))
#define median(a, b) (a+b)/2.0
#define ABS(a) (a >= 0 ? (a) : (-a))
#define zt(a, b) max(a,b)-min(a,b)
ll swap(ll *a,ll *b){ll tmp;tmp=*a;*a=*b;*b=tmp;}
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 sum(ll *a,ll n){ll total=0,i;if(n<=0){return 0;}else{rep(i,n) total+=a[i];return total;}}
ld avg(ll *a,ll n){if(n<=0){return 0;}else{return (ld)sum(a,n)/n;}}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define fact(n) nPr((int)n,(int)n)
#define nHr(n,r) nCr((int)(n+r+1),(int)r)
#define sankaku(x) ((1+x)*x)/2
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int stack[LIMIT2];//stack[0]=count;
int queue[LIMIT2];//queue[0]=start,queue[1]=length;
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
int upint(const void *a, const void *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }
int upchar(const void* left, const void* right) {return strcmp((char *)left,(char *)right);}
//qsort(s,n,sizeof(s[0]),upchar);
int downchar(const void* left, const void* right) {return strcmp((char *)right,(char *)left);}
//qsort(s,n,sizeof(s[0]),downchar);
int push(int n){
    if(stack[0]>=LIMIT2) return -1;
    stack[0]++;
    stack[stack[0]] = n;
    return 1;
}
int pop(){
    if(stack[0]<=0) return -1;
    stack[0]--;
    return stack[stack[0]+1];
}
int enqueue(int n){
    if(queue[0]+queue[1]>=LIMIT2) return -1;
    queue[queue[0]+queue[1]] = n;
    queue[1]++;
    return 1;
}
int dequeue(){
    int result;
    if(queue[1]<=0) return -1;
    result = queue[queue[0]];
    queue[0]++;
    queue[1]--;
    if(queue[1]==0){
        queue[0] = 2;//queue reset
    }else if(queue[1]==1){
        queue[2] = queue[queue[0]];//only oneth
        queue[0] = 2;
    }
    return result;
}

void initialize(){
    stack[0] = 0;//stack size
    queue[0] = 2;//queue start
    queue[1] = 0;//queue length
}
int main(void){
    initialize();
    ll n,m,p,i,j;
    ll a[LIMIT1]={0},b[LIMIT1]={0},c[LIMIT1]={0};
    ll result=0;
    char s[LIMIT1];
    scanf("%lld", &n);
  
    result = n / 500;
  result *= 1000;
    i = (n % 500) / 5;
  i *= 5;
  result += i;
  printf("%lld", result);
    
    
    return 0;
}



Measured memory_bytes: 128
#include <stdio.h>

int main(void)
{
    int N,M,p[100000],i,tmp;
    int AC=0,PN=0;
    int AC_flag[100000];//ACしたら1、してないなら0
    char S[100000][3];

    for(i=0; i<100000; i++){
        AC_flag[i] = 0;
    }

    scanf("%d %d",&N, &M);//N問、M回提出

    for(i=0; i<M; i++){
        scanf("%d %s",&p[i],S[i]);//pi問目でWAorAC
    }

    for(i=0; i<M; i++){
        tmp = p[i];
        if(AC_flag[tmp] == 0){//もしまだ解けていない問題ならば
            if(S[i][0] == 'A'){
                AC_flag[tmp] = 1;
                AC++;
            } else {
                PN++;
            }
        }
    }


    //解いていない問題のWA数は引き算する

    for(i=0; i<M; i++){
        tmp = p[i];
        if(S[i][0] == 'W'){//WAのみ考える
            if(AC_flag[tmp] == 0){//解いてない問題ならば引き算
                PN--;
            }
        }

    }

    printf("%d %d\n",AC, PN);

    return 0;
}

Measured memory_bytes: 1280
#define scanf_s scanf
//#define gets_s gets
#include <stdio.h>
#include <string>
#include <iostream>
#include <math.h>
using namespace std;
#define MIN -1
#define MAX 1000000
int main(void)
{
	double  min = MAX, max = MIN,x;
	while (scanf_s("%lf",&x) != EOF) {
		if (x > max) max = x;
		if (x < min) min = x;
	}
	printf("%f\n", max - min);
}

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

int main() {
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> player(N, K);
  for(int i=0; i<Q; ++i) {
    int a;
    cin >> a;
    ++player[a-1];
  }

  for (int i=0; i<N; ++i) {
    if (player[i] - Q > 0) {
      cout << "Yes\n";
    } else {
      cout << "No\n";
    }
  }
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<math.h>

int main(void){
  int n,x=1;
  double t,a;
  double h,ha,hx;
  
  scanf("%d",&n);
  scanf("%lf %lf",&t,&a);
  
  scanf("%lf",&h);
  hx=fabs(a-(t-h*0.006));
  
  for(int i=2;i<=n;i++){
    scanf("%lf",&h);
    ha=fabs(a-(t-h*0.006));
    if(hx > ha){
      x=i;
      hx=ha;
    }
  }
  printf("%d",x);
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<climits>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define mkp make_pair
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005
using namespace std;
/*
ll bin(ll i,ll j){
	ll mid=(i+j)/2;
	if(a[mid]==x)reutrn mid;
	else if(ans>x)return bin(i,mid-1);
	else return bin(mid+1,j);
}/*
ll power(ll base,ll power){
    ll res=1;
    base=base%mod;
    while(power>0){
    	if(power&1){
    		res=(res*base)%mod;
		}
		power=power>>1;
		base=(base*base)%mod;
	}
	return res;
}
*/
/*
int nCr(int x, int y){
	if(y>x)return 0;
	int num=fact[x];
	num*=invfact[y];
	num%=mod;
	num*=invfact[x-y];
	num%=mod;
	return num;
}
*/
/*bool prime[n+1];
void SieveOfEratosthenes(int n){
	rep(i,0,n+1)prime[i]=true
    for (int p=2;p*p<=n;p++)
        if (prime[p])
            for (int i=p*p;i<=n;i+=p)prime[i]=false;
}*/
/*
int gcd(int a,int b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
*/
int solve(){
	int k;
	cin>>k;
	string s;
	cin>>s;
	int n=s.length();
    if(n<=k)cout<<s<<endl;
    else{
		string ans="";
		ans=s.substr(0,k);
		ans+="...";
		cout<<ans<<endl;
	}
	return 0;
}
int main(){
    waste;
    int t;
    //cin>>t;
    t=1;
    while(t--){
       	solve();
    }
}


Measured memory_bytes: 3656
n = int(input())
a = [None for i in range(87)]
a[0] = 2
a[1] = 1

def calc(N):
    if a[N]:
        return a[N]
    elif a[N-1] and a[N-2]:
        a[N] = a[N-1] + a[N-2]
        return a[N]
    else:
        a[N] = calc(N-1) + calc(N-2)
        return a[N]

print (calc(n))


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

int main( ){
   int n;
    long long a;
    long long minValue = 1000000;
    long long maxValue = -1000000;
    long long sum = 0;
        
    cin >> n;  
    
    for (int i = 0; i < n; i++){
      cin >> a;
      if ( a < minValue ) minValue = a;
      if ( a > maxValue ) maxValue = a;
      sum += a;
    }
    
    cout << minValue << " " << maxValue << " " << sum << endl;
    
    return 0;
}

Measured memory_bytes: 1168
<?php
  $stdout= fopen( 'php://stdout', 'w' );
  foreach(range(1,9) as $ele1){
    foreach(range(1,9) as $ele2){
      /* echo "{$ele1}x{$ele2}=".$ele1*$ele2."\n"; */
      fwrite($stdout,$ele1."x".$ele2."=".$ele1*$ele2."\n");
    }
  }

Measured memory_bytes: 15132
package main

import "fmt"

func main(){
	var n,a,b int
	fmt.Scan(&n,&a,&b)
	if (b-a)%2 == 0{
//fmt.Println("even")
		fmt.Println(b-int((b+a)/2))
	} else {
//fmt.Println("odd")
		if a-1 >= n-b {
			fmt.Println((n-b)+1+(n-int(a+n-b+n+1)/2))
/*fmt.Println("b")
fmt.Println(n-b)
fmt.Println("1")
fmt.Println(n-int(a+n-b+n+1)/2)
fmt.Println(a+n-b+n+1)*/
		} else {
			fmt.Println((a-1)+1+(int(b-a)/2))
/*fmt.Println("a")
fmt.Println(a-1)
fmt.Println("1")
fmt.Println((int(b-a)/2))
fmt.Println(b-a)*/
		}
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <math.h>
#include <string>
#include <sstream>
#include <stack>
#define inf 1e9+7
#define pb push_back
#define make make_pair
 
using namespace std;
 
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define PI 3.14159265359
long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}
long long lcm(long long a,long long b){ return a/gcd(a,b)*b;}

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll n,k;

void solve(){
    rep(i,k){
        i;
        ll ans=1;
        ans*=COM(k-1,i);
        
        ans*=COM(n-k+1,i+1);
        
        
        cout << ans%MOD << endl;
    }
}

int main(){
    COMinit();
    cin >> n >>k;
    solve();
}



Measured memory_bytes: 12160
#include <stdio.h>
#include <stdlib.h>

int main(void){
    // Your code here!
    int n, t, x, y, i, xtmp=0, ytmp=0, xdist, ydist, dist;

    scanf("%d", &n);
    
    for(i=0;i<n;i++){
        scanf("%d%d%d", &t, &x, &y);
        
        xdist=(int)abs(x-xtmp);
        ydist=(int)abs(y-ytmp);
        dist=xdist+ydist;
        if(dist>t || (t-dist)%2!=0){
            printf("No");
            return 0;
        }
        
    }
    
    printf("Yes");
        
    return 0;
}

Measured memory_bytes: 128
k = int(input())

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(a[k-1])

Measured memory_bytes: 2940
#include <vector> 
#include <list> 
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

const LL mod = (LL)1e9 + 7;


int main() {
	
	int N;
	cin >> N;
	VI A(N);
	REP(i, N) { cin >> A[i]; }

	int min_ = *min_element(ALL(A));
	int max_ = *max_element(ALL(A));

	int ans = 9999999;
	for (int i = min_; i <= max_; i++) {
		int a = 0;
		REP(j, N) {
			a += (A[j] - i)*(A[j] - i);
		}
		ans = min(ans, a);
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] s = sc.next().split("");
		String[] t = sc.next().split("");
		Arrays.sort(s, Comparator.naturalOrder());
		Arrays.sort(t, Comparator.reverseOrder());
		String[] ss = new String[100];
		String[] tt = new String[100];
		for (int i = 0; i < 100; i++) {
			ss[i] = "a";
			tt[i] = "a";
		}
		for (int i = 0; i < s.length; i++) {
			ss[i] = s[i];
		}
		for (int i = 0; i < t.length; i++) {
			tt[i] = t[i];
		}
		for (int i = 0; i < 100; i++) {
			if (ss[i].compareTo(tt[i]) < 0) {
				System.out.println("Yes");
				return;
			} else if (ss[i].compareTo(tt[i]) > 0) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("No");

	}

}

Measured memory_bytes: 23636
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define MAX 10000
#define INF 1000000
#define pii pair<int,int>

vector<pii> eclist[MAX];//[[index,cost]]

void bfs(int start,int n){
    queue<int> q; // index
    vector<bool> visited(n, false);
    q.push(start);
    while (!q.empty()){
        int u = q.front();q.pop();
        visited[u] = true;
        for (pii vpair : eclist[u]) {
            int v = vpair.first;
            if(!visited[v]){
                q.push(v);
            }
        }
    }
}

void dijkstra_print_distance(int start, int n){
    priority_queue<pii> q; // cost,index
    vector<int> costs(n,INF);
    vector<bool> visited(n, false);
    costs[0] = 0;
    q.push(make_pair(0, start));
    while (!q.empty()){
        pii upair = q.top();q.pop();
        int u = upair.second,ucost = upair.first * -1;
        visited[u] = true;
        if( costs[u] < ucost) {
            continue;
        }
        for (pii vpair : eclist[u]) {
            int v = vpair.first,vcost = vpair.second;
            if(visited[v])continue;
            if (costs[v] > costs[u] + vcost){
                costs[v] = costs[u] + vcost;
                q.push(pii(costs[v] * -1, v));
            }
        }
    }
    for (int i = 0; i < n; ++i) cout << i << " " << costs[i] << endl;
}

int main(){
    //freopen("in", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int id,m,v,c;
        cin >> id >> m;
        for (int j = 0; j < m; ++j) {
            cin >> v >> c;
            eclist[id].push_back(pair<int,int>(v,c));
        }
    }

    dijkstra_print_distance(0, n);

    return 0;
}

Measured memory_bytes: 7980
#include<bits/stdc++.h>
#define int long long
using namespace std;
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; }

template<typename T> class LazySegmentTree
{
 private:
    int n;
    vector<T> node,lazy;
 public:
    LazySegmentTree(int sz,T init){
        n=1;
        while(n<sz) n*=2;
        node.assign(2*n-1,init);
        lazy.assign(2*n-1,-1);
    }
    void update(int a,int b,int x,int k,int l,int r){
        if(a<=l and r<=b) node[k]=lazy[k]=x;
        else{
            if(lazy[k]!=-1) push(k),lazy[k]=-1;
            if(check(a,b,l,(l+r)/2)) update(a,b,x,2*k+1,l,(l+r)/2);
            if(check(a,b,(l+r)/2,r)) update(a,b,x,2*k+2,(l+r)/2,r);
            node[k]=min(node[2*k+1],node[2*k+2]);
        }
    }
    T get(int a,int b,int k,int l,int r){
        if(a<=l and r<=b) return node[k];
        else{
            if(lazy[k]!=-1) push(k),lazy[k]=-1;
            T res=INT_MAX;
            if(check(a,b,l,(l+r)/2)) res=min(res,get(a,b,2*k+1,l,(l+r)/2));
            if(check(a,b,(l+r)/2,r)) res=min(res,get(a,b,2*k+2,(l+r)/2,r));
            return res;
        }
    }
    void push(int k){
        node[2*k+1]=node[2*k+2]=lazy[k];
        lazy[2*k+1]=lazy[2*k+2]=lazy[k];
    }
    bool check(int a,int b,int l,int r){
        return max(a,l)<min(b,r);
    }
    void update(int a,int b,int x){ update(a,b,x,0,0,n); }
    T get(int a,int b){ return get(a,b,0,0,n); }
};

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

    int N,Q; cin>>N>>Q;
    LazySegmentTree<int> seg(N,INT_MAX);
    while(Q--){
        int q; cin>>q;
        if(q==0){
            int s,t,x; cin>>s>>t>>x;
            seg.update(s,t+1,x);
        }else{
            int s,t; cin>>s>>t;
            cout<<seg.get(s,t+1)<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 7060
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 200005
#define eps 1e-10
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
        out(x / 10);
    }
    putchar('0' + x % 10);
}
int N;int64 D;
int64 A[MAXN];
struct seg_tr {
    struct node {
        int L,R;
        int64 cov;
        pair<int64,int> val[2];
    }tr[MAXN * 4];
    void update(int u) {
        tr[u].val[1] = mp(1e16,0);
        if(tr[u].L != tr[u].R) {
            tr[u].val[0] = min(tr[u << 1].val[0],tr[u << 1 | 1].val[0]);
            tr[u].val[1] = min(tr[u << 1].val[1],tr[u << 1 | 1].val[1]);
        }
        tr[u].val[1] = min(tr[u].val[1],mp(tr[u].cov + tr[u].val[0].fi,tr[u].val[0].se));
    }
    void build(int u,int l,int r,int on) {
        tr[u].L = l;tr[u].R = r;tr[u].cov = 1e16;
        if(l == r) {
            tr[u].val[0] = mp(A[l] + on * l * D,l);
            update(u);
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1,l,mid,on);build(u << 1 | 1,mid + 1,r,on);
        update(u);
    }
    void Change(int u,int l,int r,int64 v) {
        if(l > r) return;
        if(tr[u].L == l && tr[u].R == r) {
            tr[u].cov = min(tr[u].cov,v);
            update(u);
            return;
        }
        int mid = (tr[u].L + tr[u].R) >> 1;
        if(r <= mid) Change(u << 1,l,r,v);
        else if(l > mid) Change(u << 1 | 1,l,r,v);
        else {Change(u << 1,l,mid,v);Change(u << 1 | 1,mid + 1,r,v);}
        update(u);
    }
    void Change_pos(int u,int p) {
        if(tr[u].L == tr[u].R) {
            tr[u].val[0] = mp(1e16,tr[u].L);
            update(u);return;
        }
        int mid = (tr[u].L + tr[u].R) >> 1;
        if(p <= mid) Change_pos(u << 1,p);
        else Change_pos(u << 1 | 1,p);
        update(u);
    }
}s[2];


void Solve() {
    read(N);read(D);
    for(int i = 1 ; i <= N ; ++i) read(A[i]);
    s[0].build(1,1,N,1);
    s[1].build(1,1,N,-1);
    s[0].Change_pos(1,1);s[1].Change_pos(1,1);
    s[0].Change(1,2,N,A[1] - D);
    int cnt = N - 1;
    int64 ans = 0;
    while(cnt--) {
        pair<int64,int> t[2];
        t[0] = s[0].tr[1].val[1],t[1] = s[1].tr[1].val[1];
        if(t[0] > t[1]) swap(t[0],t[1]);
        ans += t[0].fi;
        int u = t[0].se;
        s[0].Change_pos(1,u);s[1].Change_pos(1,u);
        s[1].Change(1,1,u - 1,1LL * u * D + A[u]);
        s[0].Change(1,u + 1,N,-1LL * u * D + A[u]);
    }
    out(ans);enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

Measured memory_bytes: 76928
#include<stdio.h>
#define MAX 100
void Graph(int **);

int N;
int i,j;

int main(){
  int A[MAX][MAX];
  int *B[MAX];

  scanf("%d",&N);

  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      A[i][j] = 0;
    }
  }

  for(i = 0; i < N; i++){
      B[i] = A[i];
  }

  Graph(B);

  for(i = 0; i < N; i++){
    for(j = 0; j < N; j++){
      if(j != 0) printf(" ");
      printf("%d",A[i][j]);
    }
    printf("\n");
  }

  return 0;
}


void Graph(int **A){
  int u,k,v;

  for(i = 0; i < N; i++){
    scanf("%d%d",&u,&k);
    u--;
    for(j = 0; j< k; j++){
      scanf("%d",&v);
      v--;
      A[u][v] = 1;
    }
  }
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define endl '\n'
#define pi 3.1415926535897932384626433832
#define ll long long
using namespace std;
ll lcm(ll a, ll b){ if(!a || !b) return 0; return a * b / __gcd(a, b); }
bool isPrime(int n) {if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;}

void lok(){

}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin>>t;
    if(t%2==0||t%5==0){
        cout<<"-1"<<endl;
        return 0;
    }
    int sum=0;
    ll ps=t%10;
    ll jib=7;
    ll jay=0;
    ll i;
    string ringo;
    while(true){
        sum++;
        for(i=0;i<10;i++){
            if((ps*i)%10==jib){
                break;
            }
        }
        jay+=i*t;
        bool shih=true;
        int b=0;
        ringo=to_string(jay);
        while(true){
            if(b>=(int)ringo.size()){
                break;
            }
            if(ringo[b]!='7') {
                shih=false;
                break;
            }

            b++;
        }
        if(shih){
            cout<<sum+floor(log10(t*i))<<endl;
            return 0;
        }
        jay/=10;
        jib=((jay%10>7)?17-jay%10:7-jay%10);

    }
    return 0;
}

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

//template
#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 ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
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; }
//end



int main(){
   int a,b,c; scanf("%d%d%d",&a,&b,&c);
   if(a%2==1||b%2==1||c%2==1)puts("0");
   else if(a==b&&b==c)puts("-1");
   else{
      int cnt=0;
      while(1){
         if(a%2==1||b%2==1||c%2==1)break;
         int x=(a+b)/2,y=(b+c)/2,z=(c+a)/2;
         a=x; b=y; c=z; cnt++;
      }
      printf("%d\n",cnt);
   }
   return 0;
}

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

typedef long long int lli;
lli MAX = numeric_limits<lli>::max();
lli MOD = 1000000007;

/*
Finding the longest path by doing topological sort
and do DP on each node in the list: the length of the
longest path that ends at the node in the list.

g++ -std=c++11 h-grid.cpp -o k
*/
int main() {
    int i, j;
    int H, W;
    cin >> H >> W;
    string b[H];
    lli m[H][W];
    for(i = 0; i < H; i++)
        cin >> b[i];
    
    // DP from smallest top left corner
    for(i = 0; i < H; i++) {
        for(j = 0; j < W; j++) {
            if(i == 0 && j == 0) m[i][j] = 1;
            else if(b[i][j] == '#') m[i][j] = -1;
            else {
                m[i][j] = 0;
                if(i > 0 && m[i-1][j] > -1)
                    m[i][j] += m[i-1][j];
                if(j > 0 && m[i][j-1] > -1)
                    m[i][j] += m[i][j-1];
                m[i][j] %= MOD;
            }
        }
    }

    cout << m[H-1][W-1] << endl;

    return 0;
}


Measured memory_bytes: 9088
import java.util.*; 
import java.lang.*; 


public class Main{
    
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
                
                int x = scan.nextInt();
               
                if(x==0){
                    System.out.println(1);
                }else{
                    System.out.println(0);
                }
                
        }
}

Measured memory_bytes: 35776
s=list(input())
n=len(s)
total_b=0
cnt=0
total=0
for i in range(n):
    if s[i]=="B":
        total_b+=i
        cnt+=1
for i in range(n-cnt,n):
    total+=i
print(total-total_b)
#print(total,total_b)


Measured memory_bytes: 4840
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

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

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  int N;
  cin >> N;
  int a[N];
  for (int i = 0; i < N; i++) cin >> a[i];

  sort(a, a + N);
  int ans = 0;
  bool turn = true;
  for (int i = N - 1; i >= 0; i--) {
    if (turn) {
      ans += a[i];
    } else {
      ans -= a[i];
    }
    turn = !turn;
  }

  // 解答
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX 1000000
#define MOD 1e9
#define pb push_back
#define pairs pair<int, int>
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pairs>
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define endl '\n'
using namespace std;
/* ----------------------------------------------------------------------------------- */

#define FastInput ios_base::sync_with_stdio(false), cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define read(x) freopen(x, "r", stdin)
#define write(x) freopen(x, "w", stdout)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define REP(i, a, n) for (int i = a; i <= n; i++)
#define inputArray(a,n) rep(i, 0, n) cin >> a[i];
#define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
#define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;

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

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

#define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, n){cout<<A[i][j]<<" ";}cout<<"\n";}cout<<"\n";}
#define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
#define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}

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

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }

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;
		cout << b << "=" << a << " ";
		call(++it, ed, rest...);
	}
};

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

void solve() {
	int n;
	cin >> n;
	string str;
	cin >> str;
	int count = 0;
	for (int i = 0; i < str.length() - 2; i++) {
		if(str[i] == 'A' && str[i + 1] == 'B' && str[i + 2] == 'C') {
			count++;
		}
	}
	cout << count << endl;
}

int main() {
	solve();

	// __test {
	// 	solve();
	// }
}

Measured memory_bytes: 3612
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    edge = ['#'] * (W + 2)
    field = [edge]
    q = deque()

    for i in range(H):
        line = input()
        field.append(['#'] + list(line) + ['#'])
        for j in range(W):
            if line[j] == '#':
                q.append((i + 1, j + 1, 0))
    field.append(edge)
    res = 0

    while q:
        y, x, lv = q.popleft()
        if lv > res:
            res = lv

        if field[y + 1][x] == '.':
            field[y + 1][x] = '#'
            q.append((y + 1, x, lv + 1))

        if field[y - 1][x] == '.':
            field[y - 1][x] = '#'
            q.append((y - 1, x, lv + 1))

        if field[y][x + 1] == '.':
            field[y][x + 1] = '#'
            q.append((y, x + 1, lv + 1))

        if field[y][x - 1] == '.':
            field[y][x - 1] = '#'
            q.append((y, x - 1, lv + 1))

    print(res)

if __name__ == '__main__':
    main()


Measured memory_bytes: 138220
#include <stdio.h>
#include <string.h>
#define TRUE 0
#define FALSE 1
#define SIZE 5
#define LEN 6
#define MAX 5000

int Min( int a, int b){
  if( a < b ) return a;
  else        return b;
}

void String_Sort( int size , int len, char data[size][len]){
  /* Using Comb Sort Algorithm */
  int i;
  int h = size;
  int Is_Swapped = FALSE;
  char tmp[LEN];
  
  while( h > 1 || Is_Swapped == TRUE ){
    if( h > 1 ) h = (h * 10) / 13;
    
    for( Is_Swapped = FALSE, i=0; i + h < size; i++){
      if( strcmp(data[i], data[i+h]) > 0 ){
        /* Swap data[i] and data[i+h] */
        strcpy( tmp , data[i] );
        strcpy( data[i] , data[i+h] );
        strcpy( data[i+h] , tmp );
        
        Is_Swapped = TRUE;
      }
    }
  }
}

void Dedupe( int size, int len, char data[size][len] ){
  int i,n,w;
  for( i=0, n=size, w=0; i < n; i++){
    if( strcmp( data[i], data[i+1] ) != TRUE ){
      strcpy( data[w], data[i]);
      w++;
    }
  }
  
  size = w;
}

int main(void){
  int i,n,w,sslen,K;
  char s[MAX];
  char ss[MAX*5][LEN];
  
  scanf("%s",s);
  scanf("%d",&K);
  
  /* Make SubString List */
  for( sslen=0 ,n=1; n<=Min(strlen(s),5); n++){
    for( i=0; i <= strlen(s) - n; sslen++, i++){
      for( w=0; w < n; w++){
        ss[sslen][w] = s[i+w];
        ss[sslen][w+1] = '\0';
      }
    }
  }
  
  String_Sort( sslen, LEN, ss);
  /*
  for( i=0, n=sslen, w=0; i < n; i++){
    if( strcmp( ss[i], ss[i+1] ) == TRUE ) sslen--;
    else{
      strcpy( ss[w], ss[i]);
      w++;
    }
  }*/
  
  Dedupe( sslen, LEN, ss );
  
  printf("%s",ss[K-1]);  
  
  return 0;
}

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

using namespace std;

typedef long long llint;

int main() {
  llint x;
  cin >> x;
  llint v = 100;
  llint ans = 0;
  while (v < x) {
    v += v * 0.01;
    ans++;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(void) {
	int x, y, temp;

	scanf("%d %d", &x, &y);

	if (y > x) {
		temp = x;
		x = y;
		y = temp;
	}

	while (1) {
		if (x % y == 0 ) {
			break;
		}
		else {
			temp = x % y;
			x = y;
			y = temp;
		}
	}

	printf("%d\n", y);
	return 0;
}


Measured memory_bytes: 2108
#include <iostream>
#include <vector>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

ll a[1000][1000];
vector<ll> x;
vector<ll> y;
vector<ll> x2;
vector<ll> y2;

int main() {
	ll h, w; cin >> h >> w;

	rep(i, 0, h)rep(j, 0, w) {
		ll v;
		cin >> v;
		a[i][j] = v % 2;
	}

	ll cnt = 0;
	rep(i, 0, h) {
		rep(j, 0, w - 1) {
			if (a[i][j] % 2) {
				a[i][j]--;
				a[i][j + 1]++;

				y.push_back(i + 1);
				x.push_back(j + 1);
				y2.push_back(i + 1);
				x2.push_back(j + 2);
				cnt++;
			}
		}
	}

	rep(i, 0, h - 1) {
		if (a[i][w - 1] % 2) {
			a[i][w - 1]--;
			a[i + 1][w - 1]++;

			y.push_back(i + 1);
			x.push_back(w);
			y2.push_back(i + 2);
			x2.push_back(w);
			//y[cnt] = i + 1;
			//x[cnt] = w;
			//y2[cnt] = i + 2;
			//x2[cnt] = w;
			cnt++;
		}
	}
	cout << cnt << endl;
	rep(i, 0, cnt) {
		cout << y[i] << " " << x[i] << " " << y2[i] << " " << x2[i] << endl;
	}

	return 0;
}

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

int main (){
   vector<int> v;
   for(int i=0;i<3;i++){
      int a;
      cin>>a;
      v.push_back(a);
   }
   sort(v.begin(),v.end());
   if(v[0]+v[1]==v[2]){
      cout<<"Yes"<<endl;
   }else{
      cout<<"No"<<endl;
   }
   
}

Measured memory_bytes: 256
s = input()
q = int(input())
rev = 0
fir = ''
end = ''
for i in range(q):
    qvery = input()
    if len(qvery) == 1: #t == 1
        rev += 1
    else:
        qq, f, c = qvery.split(' ')
        f = int(f)
        if rev % 2 == 0:
            if f == 1:
                fir += c
            else:
                end += c
        else:
            if f == 2:
                fir += c
            else:
                end += c
fir = fir[::-1]
s = fir + s + end
if rev % 2 == 1:
    s = s[::-1]
print(s)

Measured memory_bytes: 4384
n,w=map(int,input().split())


wv=[list(map(int, input().split())) for i in range(n)]
dp=[[0]*(w+1) for _ in range(n)]


for i in range(n):
    for j in range(w+1):
        if i==0:
            if j>=wv[i][0]:
                dp[i][j]=wv[i][1]
        else:
            if j< wv[i][0]:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-wv[i][0]]+wv[i][1])



print(dp[n-1][w])


Measured memory_bytes: 119788
<?php
list($n, $m) = ints();
$A = ints();
$m = intdiv($m, 2);
$min = 10**10;
foreach($A as $a){
  if($min < $a){
    $d = $a - $min;
    if(!isset($map[$d]))$map[$d] = 0;
    $map[$d]++;
  }
  chmin($min, $a);
}
$max = max(array_keys($map));
$maxCount = $map[$max];
echo $maxCount,"\n";

function str(){
  return trim(fgets(STDIN));
}
function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}
function chmax(&$a,$b){if($a<$b){$a=$b;return 1;}return 0;}
function chmin(&$a,$b){if($a>$b){$a=$b;return 1;}return 0;}

function o(...$val){
    if(count($val)==1)$val = array_shift($val);
    $trace = debug_backtrace();
    echo $trace[0]['line'].")";
    if(is_array($val)){
        if(count($val) == 0){
            echo "empty array";
        }elseif(!is_array(current($val))){
            echo "array: ";
            echo implode(" ", addIndex($val))."\n";
        }else{
            echo "array:array\n";
            if(isCleanArray($val)){
                foreach($val as $row)echo implode(" ", addIndex($row))."\n";
            }else{
                foreach($val as $i => $row)echo "[".$i."] ".implode(" ", addIndex($row))."\n";
            }
        }
    }else{
        echo $val."\n";
    }
}
function addIndex($val){
    if(!isCleanArray($val)){
        $val = array_map(function($k, $v){return $k.":".$v;}, array_keys($val), $val);
    }
    return $val;
}
function isCleanArray($array){
    $clean = true;
    $i = 0;
    foreach($array as $k => $v){
        if($k != $i++)$clean = false;
    }
    return $clean;
}
/**
 * 座圧対象の配列を渡すと以下の値を返す
 * ・圧縮された配列
 * ・復元用のMap
 * ・圧縮用のMap
 **/
function atsu($array){
    $a = array_flip($array);
    $fuku = array_flip($a);
    sort($fuku);
    $atsu = array_flip($fuku);
    foreach($array as $i => $val)$array[$i] = $atsu[$val];
    return [$array, $fuku, $atsu];
}
//配列の最大公約数
function gcdAll($array){
    $gcd = $array[0];
    for($i = 1; $i < count($array); $i++){
        $gcd = gcd($gcd, $array[$i]);
    }
    return $gcd;
}

//最大公約数
function gcd($m, $n){
    if(!$n)return $m;
    return gcd($n, $m % $n);
}

//配列の最小公倍数
function lcmAll($array){
    $lcm = $array[0];
    for($i = 1; $i < count($array); $i++){
        $lcm = lcm($lcm, $array[$i]);
    }
    return $lcm;
}

//最小公倍数
function lcm($a, $b) {
    return $a / gcd($a, $b) * $b;
}
//ビットカウント-1の数を数える
function popcount($x){
    $con = 0;
    while ($x) {
        $x &= $x-1;
        ++$con;
    }
    return $con;
}


Measured memory_bytes: 20980
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
  ll h,w;cin>>h>>w;
  vector<vector<int > >c(h+2,vector<int>(w+2));
  REP(i,1,h+1){
    REP(j,1,w+1){
      char d;cin>>d;
      if(d=='.')c[i][j]=2;
      else c[i][j]=1;
    }
  }
  bool t=true;
  REP(i,1,h+1){
    REP(j,1,w+1){
      bool f=true;
      if(c[i][j]==1){
        f=false;
        rep(k,4){
          if(c[i+dx[k]][j+dy[k]]%2){
            f=true;
            break;
          }
        }
      }
      if(!f){
        t=f;
        break;
      }
    }
  }
  cout<<(t?"Yes":"No")<<endl;
}

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

#include <iostream>
#include <algorithm>

using namespace std;

class AAddSubMul {
public:
	void solve(std::istream& cin, std::ostream& cout) {
	    int A, B;

	    cin >> A;
	    cin >> B;

        int ans = max(A + B, A - B);
        ans = max(ans, A * B);

        cout << ans;
	}
};


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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,w;
  cin>>n>>w;
  int wt[n+1],v[n+1];
  for(int i=1;i<=n;++i){
    cin >> wt[i] >> v[i];
  }
  long long int dp[n+1][(int)1e5+1];
  for(int i=0;i<=n;++i){
    for(int j=0;j<=(int)1e5;++j){
      dp[i][j]=(1LL << 60);
    }
  }
  for(int i=0;i<=n;++i){
    dp[i][0]=0;
  }
  for(int i=1;i<=n;++i){
    for(int j=1;j<=(int)1e5;++j){
      if(j-v[i]>=0){
        dp[i][j]=min(dp[i-1][j-v[i]] + wt[i],dp[i-1][j]);
      } else{
        dp[i][j]=dp[i-1][j];
      }
    }
  }
  int ans=0;

    for(int j=0;j<=(int)1e5;++j){
      if(dp[n][j]<=w){
        ans=j;
      }
    }

  cout << ans;
}


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

int ws(int n)
{
	return n == 0 ? 0 : 1 + ws(n / 10);
}

int main()
{
	int N, res = 0;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		if (ws(i) % 2 == 1) res++;
	printf("%d\n", res);
}


Measured memory_bytes: 256
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - Round Up the Mean
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int a, b;
  cin >> a >> b;
  printf("%d\n", (a + b + 1) / 2);
  return 0;
}


Measured memory_bytes: 256
P = 1000000007

n = int(input())
dp = [0] * (n+1)

for i in range(3,n+1):dp[i] = 1
for i in range(3,n+1):
	for j  in range(3, i-2):
		dp[i]+=dp[j]
		dp[i]%=P
		
print(dp[n])


Measured memory_bytes: 9004
#include <iostream>
#include <string>
#include <iterator>
#include <vector>
#include <unordered_map>
#include <algorithm>

struct pair_hash {
	template <class T1, class T2>
	std::size_t operator() (const std::pair<T1, T2> &pair) const {
		return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
	}
};

int main()
{
  int a,b,c,d,e,k;
  std::cin >> a >> b >> c >> d >> e >> k;
  int res = 0;
  if ((e-a) > k) res = 1;

  if (res==1) std::cout << ":(";
  else std::cout << "Yay!";

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define MAX 100000
void inarray(int a[], int n){
    for(int i = 0; i < n; i++) cin >> a[i];
}

int main(){
    ll a,b,c; cin >> a >> b >> c;
    ll C = c-a-b;
    if(C < 0){
        cout << "No" << endl; return 0;
    }
    if(4*a*b < C*C) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
// #define STOPIT
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;

void debug_impl() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
    #define debug(...)\
    do {\
        cerr << boolalpha << "[" << #__VA_ARGS__ << "]:";\
        debug_impl(__VA_ARGS__);\
        cerr << std::noboolalpha;\
    } while (false)
#else
    #define debug(...) {}
#endif

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr>
istream& operator>> (istream& is, Container& v)
  { for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, enable_if_t<!is_same< Container, string >::value, nullptr_t> = nullptr >
ostream& operator<< (ostream& os, Container const& v) {
  os << "{";
  for (auto it = v.begin(); it != v.end(); it++)
    {os << (it != v.begin() ? "," : "") << *it;}
  return os << "}";
}
int main()
{
    int S, W;
    cin >> S >> W;
    if (S>W)
        cout << "safe" << endl;
    else
        cout << "unsafe" << endl;
    return 0;
}


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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(a) max((a),-(a))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repe(i,n) rep(i,(n)+1)
#define per(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define pere(i,n) rep(i,(n)+1)
#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define RET return 0
#define MOD 1000000007
#define INF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n,w;
  cin >> n >> w;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin >> a[i];
  sort(all(a),greater<int>());
  vector<int> ruiseki(n+1,0);
  for(int i=n-1;i>=0;i--){
    ruiseki[i]=a[i]+ruiseki[i+1];
  }
  if(ruiseki[0]<=w){
    cout << 1 << endl;
    return 0;
  }
  LL ans=0;
  vector<LL> dp(w+1,0);
  dp[0]=1;
  if(ruiseki[1]<w&&w-ruiseki[1]<a[0]) ans++;
  for(int i=0;i<n-1;i++){
    for(int j=w;j>=0;j--){
      if(j>=a[i]) dp[j]=(dp[j]+dp[j-a[i]])%MOD;
    }
    // for(int j=0;j<=w;j++) cout << dp[j] << " ";
    // cout << endl;
    // cout << max(w-ruiseki[i+2]-a[i+1]+1,0) << endl;
    for(int j=max(w-ruiseki[i+2]-a[i+1]+1,0);j<=w-ruiseki[i+2];j++){
      ans=(ans+dp[j])%MOD;
    }
  }
  cout << ans << endl;
  return 0;
}



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


int main() {

  unsigned long long N;
  cin >> N;

  unsigned long long ans = 0;

  for(int i=1; i<=N; i++){
    int fizz = i%3;
    int buzz = i%5;
    if(fizz !=0 && buzz !=0){
      ans += i;
    }
  }

  cout << ans << endl;

  return 0;

}


Measured memory_bytes: 3608
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){

    string S;
    cin >> S;

    string nS;
    for (int i = 0; i < S.length(); i++){
        nS = nS + S[S.length() - 1 - i];
    }
    
    long long count = 0, ans = 0;
    for (int i = 0; i < S.length(); i++){
        if (nS[i] == 'C' && nS[i + 1] == 'B'){
            i++;
            count++;
        }else if(nS[i] == 'A'){
            ans = ans + count;
        }else{
            count = 0;
        }
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1500
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		long a = in.nextLong();
		long b = in.nextLong();
		long c = in.nextLong();
		long d = in.nextLong();
		System.out.println(solve(a, b, c, d));
		in.close();
	}

	private static long solve(long a, long b, long c, long d) {
		long r = 0;
		r += (b / c);
		r -= ((a - 1) / c);
		r += (b / d);
		r -= ((a - 1) / d);
		long x = gcm(c, d);
		x = c * d / x;
		r -= (b / x);
		r += ((a - 1) / x);
		return b - a + 1 - r;
	}

	private static long gcm(long c, long d) {
		if (c < d) {
			long x = c;
			c = d;
			d = x;
		}
		if (c % d == 0)
			return d;
		return gcm(d, c % d);
	}
}


Measured memory_bytes: 21716