akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T>
inline vector<T> make_v(const T &initvalue, size_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, size_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;

using pii = pair<int64_t, int64_t>;
template <class T> using MaxHeap = priority_queue<T>;
template <class T> using MinHeap = priority_queue<T, vector<T>, greater<>>;
// }}} End

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

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

    intmax_t a, b, x;
    cin >> a >> b >> x;

    intmax_t res = (b / x) - ((a - 1) / x);
    if (a == 0 && x != 1) {
        res++;
    }

    cout << res << "\n";

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
using namespace std;
#define MAX_N 1000
int x[MAX_N][MAX_N], y[MAX_N][MAX_N];
int H, W, N, X, Y, C, D, SX, SY, GX, GY;
int main() {
	while (true) {
		cin >> W >> H;
		if (H == 0 && W == 0) { break; }
		cin >> SX >> SY >> GX >> GY >> N;
		for (int i = 0; i < MAX_N; i++) {
			for (int j = 0; j < MAX_N; j++) {
				x[i][j] = 0; y[i][j] = 0;
			}
		}
		for (int i = 0; i < N; i++) {
			cin >> C >> D >> X >> Y;
			if (D == 0) {
				for (int j = Y; j < Y + 2; j++) {
					for (int k = X; k < X + 4; k++) {
						x[j][k] = C;
					}
				}
			}
			if (D == 1) {
				for (int j = Y; j < Y + 4; j++) {
					for (int k = X; k < X + 2; k++) {
						x[j][k] = C;
					}
				}
			}
		}
		queue<pair<int, int> >Q; Q.push(make_pair(SY, SX)); y[SY][SX] = 1;
		while (!Q.empty()) {
			pair<int, int>pa = Q.front(); Q.pop();
			int a1 = pa.first; int a2 = pa.second;
			if (y[a1 - 1][a2] == 0 && a1 - 1 >= 1 && x[a1][a2] == x[a1 - 1][a2]) { y[a1 - 1][a2] = 1; Q.push(make_pair(a1 - 1, a2)); }
			if (y[a1 + 1][a2] == 0 && a1 + 1 <= H && x[a1][a2] == x[a1 + 1][a2]) { y[a1 + 1][a2] = 1; Q.push(make_pair(a1 + 1, a2)); }
			if (y[a1][a2 - 1] == 0 && a2 - 1 >= 1 && x[a1][a2] == x[a1][a2 - 1]) { y[a1][a2 - 1] = 1; Q.push(make_pair(a1, a2 - 1)); }
			if (y[a1][a2 + 1] == 0 && a2 + 1 <= W && x[a1][a2] == x[a1][a2 + 1]) { y[a1][a2 + 1] = 1; Q.push(make_pair(a1, a2 + 1)); }
		}
		if (y[GY][GX] == 1) { cout << "OK" << endl; }
		if (y[GY][GX] == 0) { cout << "NG" << endl; }
	}
	return 0;
}

Measured memory_bytes: 9024
#include <iostream>
using namespace std;
using ll = long long;
#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
const ll INF = 1e18;
ll dp[101][100001];
int main() {
  int in(N); int in(W);

  int w[100], v[100];
  rep(i, N)
    cin >> w[i] >> v[i];

  rep(i, N+1) rep(j, 1e5+1) dp[i][j] = INF;
  dp[0][0] = 0;

  rep(i, N) rep(j, 1e5+1) {
    if (j - v[i] >= 0)
      dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i]);
    else
      dp[i+1][j] = dp[i][j];
  }

  int ans = 0;
  rep(j, 1e5+1)
    if (dp[N][j] <= W)
      ans = j;

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
typedef long long int ll; 
typedef long double ld; 


	
int main()
{
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	ll x;
	cin>>x;
	
	ll val = 1+4*2*x;
	
	val = sqrt(val);
	
	val-=1;
	val = val/2;
	
	if(((val*(val+1))/2) == x)
	{
		cout<<val<<endl;
	}
	else
	{
		cout<<val+1<<endl;
	}
	
}



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

int main(){
  set<int> S;
  int q, query, x, L, R;
  scanf("%d", &q);
  for(int i = 0; i < q; i++){
    scanf("%d", &query);
    if(query == 3){
      scanf("%d%d", &L, &R);
      auto it = S.lower_bound(L);
      for(auto i = it; i != S.end() && *i <= R; i++){
        printf("%d\n", *i);
      }
    }else{
      scanf("%d", &x);
      if(query == 0){
        S.insert(x);
        printf("%d\n", S.size());
      }else if(query == 1){
        auto it = S.find(x);
        if(it != S.end()){
          printf("%d\n", 1);
        }else{
          printf("%d\n", 0);
        }
      }else{
        S.erase(x);
      }
    }
  }
  return 0;
}



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

struct tree {
	string str;
	vector<tree*> to;
	tree(const string& s) : str(s) {}
	~tree() {
		for (auto ne : to) {
			delete ne;
		}
	}
};

void dfs(int depth, tree* t) {
	if (depth > 0) {
		cout << string(depth, '.');
	}
	cout << t->str << endl;
	for (auto ne : t->to) {
		dfs(depth + 1, ne);
	}
}

int main()
{
	int n, k;
	string s;
	cin >> n;
	vector<tree*> pos;
	cin >> k >> s;
	pos.push_back(new tree(s));
	for (int i = 1; i < n; i++) {
		cin >> k >> s;
		auto ite = new tree(s);
		pos.push_back(ite);
		pos[k - 1]->to.push_back(ite);
	}
	dfs(0, pos.front());
	delete pos.front();
	return 0;
}

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, m; cin >> n >> m;
  vector<pair<int,int>> mvs;
  for(int i = 0; i < m; i++){
    int x, y; cin >> x >> y; y--;
    mvs.push_back({x, y});
  }
  sort(mvs.begin(), mvs.end(), [](pair<int,int> a, pair<int,int> b){
    if(a.second != b.second) return a.second < b.second;
    return a.first < b.first;
  });
  set<int> k;
  for(auto e : mvs){
  	auto it = k.lower_bound(e.first);
    if(it != k.end() && *it <= e.second);
    else k.insert(e.second);
  }
  cout << k.size() << endl;
  return 0;
}


Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int inputNum = scanner.nextInt();
			int cnt = 1;
			State state = State.NONE;
			for (int i = 1; i < n; i++) {
				int beforeNum = inputNum;
				inputNum = scanner.nextInt();
				switch (state) {
				case NONE:
					if (beforeNum < inputNum) {
						state = State.UP;
					}
					if (beforeNum > inputNum) {
						state = State.DOWN;
					}
					break;
				case UP:
					if (beforeNum > inputNum) {
						state = State.NONE;
						cnt++;
					}
					break;
				case DOWN:
					if (beforeNum < inputNum) {
						state = State.NONE;
						cnt++;
					}
					break;
				default:
					break;
				}
			}
			System.out.println(cnt);
		} catch (Exception ex) {
			ex.printStackTrace();
		}
	}

	enum State {
		NONE, UP, DOWN
	}

}


Measured memory_bytes: 48200
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
#define MOD 1000000007
ll powll(ll a,ll b){ll r=1;rep(i,b){r*=a;}return r;}
#define swap(a,b) do{ll w=(a);(a)=(b);(b)=w;}while(0)
#define swapd(a,b) do{double w=(a);(a)=(b);(b)=w}while(0)
#define in(a) scanf("%lld", &(a))
#define in2(a,b) scanf("%lld %lld",&(a),&(b))
#define in3(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define ind(a) scanf("%lf", &(a))
#define ins(a) scanf("%s", (a))
#define inc(a) scanf("%c", &(a))
#define put(a) printf("%lld\n", (a))
#define putd(a) printf("%.15f\n", (a))
//      puts(a) printf("%s\n", a) 文字はこっち
//your code here!
int main(void){
    ll alph[26]={0};
    char S[100100];
    ins(S);
    ll idx=0;
    while(S[idx]!='\0') alph[S[idx++]-'a']++;
    rep(i, 26){
        if(!alph[i]){
            putchar('a'+i);
            return 0;
        }
    }
    puts("None");
    return 0;
}


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

int main(void) {
	string n;
	cin >> n;
	for (int i = 0; i < n.length(); i++) {
		if (n[i] == '9') {
			n[i] = '1';
		}
		else if (n[i] == '1') {
			n[i] = '9';
		}
	}
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 256
($N,$Y)=glob<>;
for$i(0..$N){
	for(0..$N-$i){
		if($i*10+$_*5+($k=$N-$i-$_)==$Y/1e3){
			exit!print"$i $_ $k"
		}
	}
}
print'-1 -1 -1'


Measured memory_bytes: 768
# AtCoder Beginner Contest 095
# C - Half and Half
# https://atcoder.jp/contests/abc095/tasks/arc096_a

a, b, c, x, y = map(int, input().split())
mincost = 10**12

for i in range(x+y):
    cost = 2*c*i + a*max(0, x-i) + b*max(0, y-i)
    if cost < mincost:
        mincost = cost

print(mincost)


Measured memory_bytes: 2940
#! /usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 6)

tt = int(input())
for _ in range(tt):
    n, a, b, c, d = map(int, input().split())
    memo = {}
    def solve(k):
        if k == 0:
            return 0
        elif k == 1:
            return d
        elif k in memo:
            return memo[k]
        else:
            res = k * d
            r = k % 2
            for x in [k - r, k - r + 2]:
                if x >= 1 and x // 2 < k:
                    res = min(res, d * abs(k - x) + a + solve(x // 2))
            r = k % 3
            for x in [k - r, k - r + 3]:
                if x >= 1 and x // 3 < k:
                    res = min(res, d * abs(k - x) + b + solve(x // 3))
            r = k % 5
            for x in [k - r, k - r + 5]:
                if x >= 1 and x // 5 < k:
                    res = min(res, d * abs(k - x) + c + solve(x // 5))
            memo[k] = res
            return memo[k]
    print(solve(n))


Measured memory_bytes: 11344
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ShekharN
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt(), a = in.nextInt(), b = in.nextInt();
            if ((Math.abs(b - a) - 1) % 2 != 0) {
                out.println("Alice");
            } else
                out.println("Borys");
        }

    }

    static class FastScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        public String nextString() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}



Measured memory_bytes: 21460
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main  {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//int n = sc.nextInt();
		//int k = sc.nextInt();
		//String[] array = new String[h+1];
		//List<String> list= new ArrayList<String>(Arrays.asList(s.split("")));
		List<Integer> list=new ArrayList<Integer>();

		for(int i=0;n>i;i++) {
			int a=sc.nextInt();
			list.add(a);
		}

		Collections.sort(list);
		int b=0;
		int a=0;
		//System.out.println(list);
		int d = n/2;
		int c = d-1;

		int half = list.get(d);
		int check = list.get(c);

		if(half==check) {
			System.out.println(0);
		}
		else {
			System.out.println(half-check);
		}
/*
		for(int i=n-2;n>i;i++) {
			int arc=0;
			int abc=0;
			a = list.get(i);
			a = a-1;
			for(int j=0;n>j;j++) {
				if(a<list.get(j)) {
					arc++;
				}
				else {
					abc++;
				}
			}
			if(arc==abc) {
				a = list.get(i);
				b = list.get(i-1);
				break;
			}
			//System.out.println(arc);
			//System.out.println(abc);
			a=0;
		}


		//System.out.println(a);
		//System.out.println(b);
		System.out.println(a-b);
		*/
		}

}



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

int main() {
  int N,K,den=1;
  cin >> N >> K;

  /*
  cout << N << endl;
  cout << K << endl;
  */
  for(int i=0; i<N; i++){
    if(den*2 <= den+K){
      den *=2;
      //cout << "ift:" << endl;
    }else{
      den += K;
      //cout << "iff:" << endl;
    }
    //cout << "den:" << den << endl;
  }
  
  cout << den << endl;
  
}


Measured memory_bytes: 256
import itertools
n = int(input())
Dict = {'M':0,'A':1,'R':2,'C':3,'H':4}

List = [[]for i in range(5)]
for i in range(n):
    tmp = input()
    if tmp[0] in Dict:
        index = Dict[tmp[0]]
        List[index].append(tmp)
List_num = [len(List[i]) for i in range(5)]
ans = 0
for v in itertools.combinations(List_num,3):
    cnt = 1
    for youso in v:
        cnt*=youso
    ans += cnt
print(ans)

Measured memory_bytes: 10100
#include <iostream>
            #include <bits/stdc++.h>
            #include <cstring>
            #include <cstdlib>
            #include <utility>
            #include <set>
            #include <vector>
            #include <algorithm>
            #include <iomanip>
            using namespace std;
            typedef long long ll;
            long double pie = 3.1415926535;
            int main() {
                
                    int k;
                    cin >> k;
                    string a;
                    cin >> a;
                    if(a.length()<=k)
                    cout << a;
                    else
                    {
                        string b(a,0,k);
                        b=b+"...";
                        cout << b;
                    }
                
                return 0;
            }

Measured memory_bytes: 3624
#include<stdio.h>
int main(){
int a, b, c, w;
scanf("%d %d %d", &a,&b,&c);
if(a>b){
w = a;
a = b;
b = w;
}if(b>c){
w = b;
b = c;
c = w;
}if(a>b){
w = a;
a = b;
b = w;
}
printf("%d %d %d\n", a,b,c);
return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

#define forn(i,n) for(int i = 0;i<int(n);i++)
#define ll long long

int main(){
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  double a;
  cin>>a;
  cout<<2*3.1415926*a;

}


Measured memory_bytes: 3804
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define Yes(f) cout<<(f?"Yes":"No")<<endl
#define yes(f) cout<<(f?"yes":"no")<<endl
#define YES(f) cout<<(f?"YES":"NO")<<endl
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v), greater<int>())

using namespace std;

const int mod=1e9+7;

void run();

void init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(12);
}

signed main(){
    init();
    run();
    return 0;
}

void run(){
    int n;
    cin>>n;
    vi v(5);
    rep(i,5)cin>>v[i];
    cout<<(int)ceil(1.0*n/ *min_element(all(v)))+4<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <string>

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

using namespace std;

int main() {
    int N, M;
    int A[300][300];
    scanf("%d %d", &N, &M);
    REP(i, N){
        REP(j, M){
            scanf(" %d", &A[i][j]);
        }
    }
    int ans = N;
    REP(step, M) {
        int cnt[300];
        fill(cnt, cnt+300, 0);
        REP(i, N) {
            REP(j, M) {
                if (A[i][j] != 0) {
                    cnt[A[i][j] - 1]++;
                    break;
                }
            }
        }
        int d = distance(cnt, max_element(cnt, cnt + M));
        REP(i, N) {
            int *iter = find(A[i], A[i + 1], d + 1);
            *iter = 0;
        }
        ans = min(ans, cnt[d]);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const ll mod=1e9+7;
const ll inf = (ll)1e17;
const ld eps = 1e-12;
const ld PI = 3.14159265358979323846;
ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k;
    cin>>n>>k;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<bool>dp(k+1);
    for(int stones=0;stones<=k;stones++){
        for(int j=0;j<n;j++){
            if(stones-a[j]>=0 && !dp[stones-a[j]]){
                dp[stones]=true;
            }
        }
    }
    cout<<(dp[k]?"First":"Second")<<endl;

    return 0;
    }


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	if(b<a)
	{
		printf("%d\n",a-1);
	}
	else
	{
		printf("%d\n",a);
	}
	return 0;
} 

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x;
    cin >> n >> m >> x;
    int sum1 = 0,sum2 = 0;
    for(int i = 0;i < m;i++)
    {
        int a;
        cin >> a;
        if(a < x)
        {
            sum1++;
        }
        else
        {
            sum2++;
        }
    }
    cout << min(sum1,sum2);
    
    return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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 (b<a) { a=b; return 1; } return 0; }



i64 n, a[101010], m;
i64 d[101010];
void solve(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		d[i+1] = d[i]+a[i];
	}
	
	bool ok = 0;
	for(int i = 2; i <= n; i++){
		if(d[i]-d[i-2] >= m){
			ok = 1;
			cout << "Possible" << endl;
			for(int j = 1; j < i-1; j++){
				cout << j << endl;
			}
			for(int j = n-1; j >= i; j--){
				cout << j << endl;
			}
			cout << i-1 << endl;
			break;
		}
	}
	if(!ok){
		cout << "Impossible" << endl;
	}
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007;
#define pi 3.14159265358979323846
#define Endl endl
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int k,n;
	cin>>k>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++){ cin>>a[i]; }
	a.pb( a[0] + k );
	vector<int> b;
	for(int i=0;i<n;i++){
		b.pb( a[i+1]-a[i] );
	}
	sort( b.begin(), b.end() );
	cout<< k - b[b.size()-1] <<endl;
	return 0;
}

Measured memory_bytes: 6628
import java.util.Scanner;

public class Main {
	Scanner sc;
	final int LEFT  = 0;
	final int DOWN  = 1;
	final int RIGHT = 2;
	final int UP    = 3;

	private Main(){
		sc = new Scanner( System.in );
	}
	private void run(){
		while( true ){
			int n = sc.nextInt();
			if( n == 0 ){ break; }
			Position[] pos = new Position[ n ];
			pos[ 0 ] = new Position( 0, 0 );
			for( int i = 1; i < n; i++ ){
				int base = sc.nextInt();
				int dir = sc.nextInt();
				switch( dir ){
				case LEFT:
					pos[ i ] = new Position( pos[ base ].x - 1, pos[ base ].y );
					break;
				case DOWN:
					pos[ i ] = new Position( pos[ base ].x, pos[ base ].y + 1 );
					break;
				case RIGHT:
					pos[ i ] = new Position( pos[ base ].x + 1, pos[ base ].y );
					break;
				case UP:
					pos[ i ] = new Position( pos[ base ].x, pos[ base ].y - 1 );
					break;
				}
			}
			int minXIndex = 0;
			int minYIndex = 0;
			int maxXIndex = 0;
			int maxYIndex = 0;
			for( int i = 1; i < n; i++ ){
				if( pos[ i ].x < pos[ minXIndex ].x ){
					minXIndex = i;
				}
				if( pos[ i ].x > pos[ maxXIndex ].x ){
					maxXIndex = i;
				}
				if( pos[ i ].y < pos[ minYIndex ].y ){
					minYIndex = i;
				}
				if( pos[ i ].y > pos[ maxYIndex ].y ){
					maxYIndex = i;
				}
			}
			System.out.println( ( pos[ maxXIndex ].x - pos[ minXIndex ].x + 1 ) + " " + ( pos[ maxYIndex ].y - pos[ minYIndex ].y + 1) );
		}

	}

	public static void main( String[] args ){
		new Main().run();
	}
}

class Position{
	int x, y;
	Position( int x, int y ){
		this.x = x;
		this.y = y;
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
ll INF = 1e15;

int main(){
    ll n;
    cin >> n;
    vll a(n);
    REP(i, n) cin >> a[i];
    vll dp(n + 1, INF);
    REP(i, n) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
    ll res = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 4428
using System;
using System.IO;
using System.Linq;

class Program{
    static void Main(string[] args){
        var arr = Console.ReadLine().Split();
        var N = int.Parse(arr[0]);
        var C = int.Parse(arr[2]);
        var B = Console.ReadLine().Split();
        var answer = 0;
        for (int i = 1; i <= N; i++){
            var A = Console.ReadLine().Split();
            var sum = 0;
            foreach (var (a, b) in A.Zip(B)){
                sum += int.Parse(a) * int.Parse(b);}
            if (sum + C > 0) answer++;}
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();}}

Measured memory_bytes: 27912
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

string n;
int k;
int sz;
int x[105];

int cache[105][5][2];

int dp(int idx, int cnt, int less){
    if(cnt>k) return 0;
    if(idx==sz+1){
        return (cnt==k);
    }
    int &ans=cache[idx][cnt][less];
    if(ans!=-1) return ans;
    ans=0;
    if(!less){
        for(int i=0; i<=x[idx]; i++){
            if(i!=0) ans+=dp(idx+1, cnt+1, less|(i<x[idx]));
            else ans+=dp(idx+1, cnt, less|(i<x[idx]));
            ans%=mod;
        }
    }
    else{
        for(int i=0; i<=9; i++){
            if(i!=0) ans+=dp(idx+1, cnt+1, less);
            else ans+=dp(idx+1, cnt, less);
            ans%=mod;
        }
    }
    return ans;
}

int f(string &s){
    sz=s.size();
    for(int i=0; i<sz; i++) x[i+1]=s[i]-'0';
    mst(cache,-1);
    return dp(1,0,0);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cin >> k;
    int res=f(n);
    //trace(f(n));
    //rep(i,1,sz+1) cout << x[i] << "\n";
    res%=mod;
    cout << res;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
lis = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        lis[i].append(tuple(map(int,input().split())))

from itertools import product

ans = 0
for i in product((0,1),repeat=n):
    for j,k in enumerate(i):
        if k==0:
            continue
        else:
            if all(map(lambda x:i[x[0]-1]==x[1],lis[j])):
                continue
            else:
                break
    else:
        ans = max(ans,sum(i))
print(ans)


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

#include <math.h>
#include <stdlib.h>


#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

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

//INT_MAX	2,147,483,647 = 2*1.0e9

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int N;
    cin >> N;

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

    sort(Y.begin(), Y.end());

    int medS = Y[N/2-1];
    int medL = Y[N/2];

    for(int i= 0; i < N; i++){
        if(X[i] < medL) cout << medL << endl;
        else cout << medS << endl;
    }

    return 0;
}


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

#define int             long long int
#define ld              long double
#define ff              first
#define ss              second
#define mp              make_pair
#define pb              push_back
#define endl            "\n"

#define si              set <int>
#define vi              vector <int>
#define pii             pair <int, int>
#define vpii            vector <pii>
#define mii             map <int, int>
#define que_max         priority_queue <int>
#define que_min         priority_queue <int, vi, greater<int>>

#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))


#define M               1000000007
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
	int x = 1;
	while (b)
	{
		if (b & 1) x *= a;
		a *= a;
		b >>= 1;
	}
	return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 3e5 + 7;
vector <vi > adj;
const int inf = INT_MAX;
const long long INF = LLONG_MAX;
bool vis[N];
int a[405];
int sum[405];
int dp[405][405];

int go(int s, int e)
{
	if (s >= e) return 0;
	if (e == s + 1) return a[s] + a[e];

	int &ans = dp[s][e];
	if (ans != -1) return ans;

	int res = INF;
	loop(i, s, e)
	{
		int s1 = sum[i] - sum[s - 1];
		int s2 = sum[e] - sum[i];
		//bug(s1, s2);
		res = min(go(s, i) + go(i + 1, e) + s1 + s2, res);
	}
	return ans = res;
}

void solve()
{
	int n;
	cin >> n;
	loop(i, 1, n + 1) cin >> a[i], sum[i] = sum[i - 1] + a[i];
	//Print(sum, 1, n + 1);
	loop(i, 0, 405)
	{
		loop(j, 0, 405)
		dp[i][j] = -1;
	}
	//mset(dp, -1);
	cout << go(1, n);

	return;

}

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

	cout << setprecision(9) << fixed;

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}


	return 0;
}


Measured memory_bytes: 1536
use v5.18; # strict say state
use warnings;
use List::Util qw(reduce first max min sum0);

chomp (my $n = <STDIN>);
my @s;
for my $i (0..$n-1) {
  chomp (my $in = <STDIN>);
  my @b = split //, $in;
  @b = sort {$a cmp $b} @b;
  $s[$i] = join('', @b);
}
my %h;
$h{$_}++ for @s;
my $ans = 0;
for my $value (values %h) {
  next if $value == 1;
  $ans += reduce {$a + $b} (1..$value-1);
}
say $ans;

Measured memory_bytes: 22528
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 200005;
const int INF = (LL)1e9 + 5;
const int MOD = 1000000007;

int dp[MAXN], H, W;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> H >> W;
	dp[1] = 1;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			char ch;
			cin >> ch;
			dp[j] = ch == '#' ? 0 : (dp[j] + dp[j - 1]) % MOD;
		}
	}
	
	cout << dp[W] << "\n";
}


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

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
typedef long long ll;

int main() {
	ll x;
	cin >> x;
	for (int i = 1; i < 100000; i++) {
		if (x <= i * (i + 1) / 2) {
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define INF 1000000000000000000
#define MOD 1000000007
using Graph=vector<vector<int>>;

int main(){
  int H,W,N;
  cin>>H>>W>>N;
  vector<int> a(N),b(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i)>>b.at(i);
  }

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

  map<pair<int,int>,int> m;
  for(int i=0;i<N;i++){
    int x=a.at(i);
    int y=b.at(i);
    if(x>1&&y>1&&x<H&&y<W){
      m[make_pair(x,y)]++;
    }
    for(int k=0;k<8;k++){
      int nx=x+dx[k];
      int ny=y+dy[k];
      if(nx>1&&ny>1&&nx<H&&ny<W){
        m[make_pair(nx,ny)]++;
      }
    }
  }

  cout<<((ll)H-2)*((ll)W-2)-(ll)m.size()<<endl;
  vector<int> count(10,0);
  for(auto p:m){
    count.at(p.second)++;
  }
  for(int i=1;i<10;i++){
    cout<<count.at(i)<<endl;
  }
}


Measured memory_bytes: 57344
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { reader: s.lock() };
    let n = sc.read();
    let a: Vec<usize> = sc.read_vec(n);

    let mut ans = 0;
    let mut cur = 0;
    while cur < n {
        let from = cur;
        while cur + 1 < n && a[cur + 1] == a[from] {
            cur += 1;
        }
        let count = cur - from + 1;
        ans += count / 2;
        cur += 1;
    }
    println!("{}", ans);
}

pub struct Scanner<R> {
    reader: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Pack{
  string mes,sou,des;
};

int n,m;

bool much(Pack p1, Pack p2){
  for(int i = 0; i < p1.sou.length(); i++)
    if(p1.sou[i] != p2.sou[i] && p2.sou[i] != '?') return false;

  for(int i = 0; i < p1.des.length(); i++)
    if(p1.des[i] != p2.des[i] && p2.des[i] != '?') return false;

  return true;
}

int main(){
  
  while(cin >> n >> m && n+m){
    vector<Pack> ans;
    vector<Pack> rule;
    
    for(int i = 0; i < n; i++){
      Pack p;
      cin >> p.mes >> p.sou >> p.des;
      rule.push_back(p);
    }

    reverse(rule.begin(),rule.end());

    for(int i = 0; i < m; i++){
      Pack p;
      cin >> p.sou >> p.des >> p.mes;
      for(int j = 0; j < rule.size(); j++){
	if(much(p,rule[j])){
	  if(rule[j].mes == "permit") ans.push_back(p);
	  break;
	}
      }
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++)
      cout << ans[i].sou << " " << ans[i].des << " " << ans[i].mes << endl;
  }
  return 0;
}

Measured memory_bytes: 1452
n=int(input())

a= list(map(int,input().split()))

plus = []

minas = []

for value in a:
    if value < 0:
        minas.append(abs(value))
    else:
        plus.append(value)

if len(minas)%2 == 0:
    ans = sum(plus)+sum(minas)
else:
    if len(plus) > 0:
        mini = min(min(plus),min(minas))
        ans = sum(plus)+sum(minas)-mini*2
    else:
        mini = min(minas)
        ans = sum(minas)-mini*2

print(ans)

Measured memory_bytes: 90756
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n) for (int i=1; i < (int)(n); i++)
#define rrep(i, n) for (int i=((int)(n)-1); i>=0; i--)
#define rreps(i, n) for (int i=((int)(n)-1); i>0; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using lint = long long;
using p = pair<int, int>;
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 (b<a) { a=b; return 1; } return 0; }

int main() {
  int s, w; cin >> s >> w;
  if (s <= w)
    printf("unsafe\n");
  else
    printf("safe\n");

  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <string>

using namespace std;

bool mmable(char a, char b){
    if(a == '0'){
        if(b != '0'){
            return true;
        }else return false;
    }else if(a == '1'){
        if(b == '0'  || b == '1'  || b == '2'){
            return true;
        }else false;
    }else return false;
}

int main(){

    string s;
    cin >> s;
    bool a,b;
    string ans = "";

    a = mmable(s[0],s[1]);
    b = mmable(s[2],s[3]);

    if(a){
        if(b){
            ans += "AMBIGUOUS";
        }else ans += "MMYY";
    }else{
        if(b){
            ans += "YYMM";
        }else ans += "NA";
    }

    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll GCD(ll a, ll b){ return a ? GCD(b % a, a) : b; }
int main(){
    ll n;
    cin>>n;
    n--;
    stack<int> s;
    while(n>=0){
        s.push(n%26);
        n/=26;
        n--;
    }
    while(!s.empty()){
        cout<<(char)(s.top()+'a');
        s.pop();
    }
    cout<<endl;
}

Measured memory_bytes: 3544
n = int(input())
a = input().split()
a = [int(m) for m in a]
asum = []
t = 0
for i in range(n):
    t += a[i]
    asum.append(t)
x1 = 0
x2 = 0
x3 = 0
x4 = 0
s1 = 1
s2 = 3
ansli = []
for i in range(n - 3):
    ansli.append([])
ac = 2
bc = 2
for i in range(2, n - 1):
    for j in range(s1, i):
        if j == 1:
            s1l = asum[0]
            s1r = asum[i - 1] - asum[0]
            cr = abs(s1l - s1r)
            ac = 2
        else:
            if ac == 1:
                s1r += a[i - 1]
                cr = abs(s1l - s1r)

            s1l2 = asum[j - 1]
            s1r2 = asum[i - 1] - asum[j - 1]
            cr2 = abs(s1l2 - s1r2)
            if cr2 <= cr:
                s1l = s1l2
                s1r = s1r2
                cr = cr2
                s1 = j
                ac = 2
            else:
                break
    ansli[i - 2].append(s1l)
    ansli[i - 2].append(s1r)
    ac = 1
    for k in range(s2, n):
        if k == 3:
            s2l = asum[i] - asum[i - 1]
            s2r = asum[n - 1] - asum[i]
            crw = abs(s2l - s2r)
            bc = 2
        else:
            if bc == 1:
                s2l -= a[i - 1]
                crw = abs(s2l - s2r)

            s2l2 = asum[k - 1] - asum[i - 1]
            s2r2 = asum[n - 1] - asum[k - 1]
            cr2w = abs(s2l2 - s2r2)
            if cr2w <= crw:
                s2l = s2l2
                s2r = s2r2
                crw = cr2w
                s2 = k
                bc = 2
            else:
                break
    ansli[i - 2].append(s2l)
    ansli[i - 2].append(s2r)
    bc = 1
ransli = []
for i in range(n - 3):
    p = max(ansli[i])
    q = min(ansli[i])
    ransli.append(p - q)

print(min(ransli))

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

int main() {
	string S; cin >> S;
	for (long long i = 0; i < 4; i++) {
		cout << S.at(i);
	}
	cout << ' ';
	for (long long i = 4; i < 12; i++) {
		cout << S.at(i);
	}
	cout << endl;
}

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

#define ll long long
#define mod 1000000007

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

    ll a;
    cin >> a;
    ll b = a*a;
    cout << a + b + (b*a) << "\n";
    
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
struct objects{
    int weight,value;
};
ll solve(){
   int n,w;
   cin>>n>>w;
   objects object[n];
   int totalvalue=0;
   for(int i=0;i<n;i++){
       cin>>object[i].weight>>object[i].value;
       totalvalue+=object[i].value;
   }
   ll dp[n+1][totalvalue+1];
    //dp[i][j] denotes the least weight to get a value of
   // j from the first i objects
   dp[0][0]=0;//It takes 0 weight here
   int ans=0;
   for(int i=1;i<=totalvalue;i++){
       dp[0][i]=1e18;
      // Just set it arbitrarily large
       //because it's not possible 
   }
   for(int i=0;i<n;i++){
       for(int j=0;j<=totalvalue;j++){
           if(j>=object[i].value){
                dp[i+1][j]=min(dp[i][j],dp[i][j-object[i].value]+object[i].weight);
                //Either don't choose this object(dp[i][j]) or choose this object
                //The value without it would be j-object[i].value
                //the minimum weight would be the minimum weight needed to
                //get a value of j- object[i].value and add the weight of this object.
           }
           else{
               //If I choose this object the value will go over j
               dp[i+1][j]=dp[i][j];
           }
           if(dp[i+1][j]<=w){//Is it possible to get value of j in less than w weight
               ans=max(ans,j);//Find maximum such j
           }
       }
   }
   return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout<<solve();
}

Measured memory_bytes: 82412
N,K = map(int,input().split())
p = list(map(int,input().split()))
math = [0]*N
ans = 0
check = 0
for i,j in enumerate(p):
    math[i] += (j*(j+1)/2)/j
    if(i+1<=K):
        check += math[i]
    else:
        check += math[i]
        check -= math[i-K]
    ans = max(ans,check)
print(ans)

Measured memory_bytes: 32144
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <regex>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
using ll = long long;
using VL=vector<ll>;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
const long long INF =  999999999;

int dx[2]={1,0},dy[2]={0,1};
int d[500][500];

int main(){
  typedef pair<int,int> P;
  int H,W;
  cin>>H>>W;
  vector<string> S(H+1);
  REP(i,H){
    cin>>S[i];
    S[i]+='#';
  }
  S[H]=string(W+1,'#');
  map<P,int> pos;

  REP(i,H+1){
    REP(j,W+1)pos[P(i,j)]=j+i*(W+1);
  }

  REP(i,450)REP(j,450)d[i][j]=INF;
  REP(i,450)d[i][i]=0;

  REP(x,H){
    REP(y,W){
      REP(k,2){
        int nx=x+dx[k],ny=y+dy[k];
        if(S[nx][ny]=='.' && S[x][y]=='.'){
          d[pos[P(x,y)]][pos[P(nx,ny)]]=1;
          d[pos[P(nx,ny)]][pos[P(x,y)]]=1;
        }
      }
    }
  }

  int N=H*(W+1);
  REP(k,N){
    REP(i,N){
      REP(j,N){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }
  int ans=0;
  REP(i,N){
    REP(j,N){
      if(d[i][j]!=INF && i!=j)ans=max(ans,d[i][j]);
    }
  }

  cout<<ans<<endl;
}


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

signed main() {
  int n, k;
  cin >> n >> k;
  vector<int> p(n), c(n);
  for (int &i : p) {
    cin >> i;
    i--;
  }
  for (int &i : c) cin >> i;
  ll ans = -1001001001;
  for (int i = 0; i < n; i++) {
    int now = i;
    vector<ll> vs;
    ll res = 0;
    while (1) {
      now = p[now];
      res += c[now];
      vs.push_back(res);
      if (now == i) break;
    }
    int sz = vs.size();
    for (int j = 0; j < sz; j++) {
      if (j + 1 > k) break;
      if (res <= 0) ans = max(ans, vs[j]);
      else ans = max(ans, vs[j] + ((k - j - 1) / sz) * res);
    }
  }
  cout << ans << endl;
  return 0;
}

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.end()

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//cout << fixed << setprecision(6);
	int n; cin >> n;
	vi a(n);
	rep(i, n) cin >> a[i];

	ll ans = 0;
	rep(i, n) ans += a[i];
	ans -= n;

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
# 2019/01/05
# AtCoder Grand Contest 30

# Input
a, b, c = map(int,input().split())

# Init
ans = 0
wc = 0

if a >= c:
    ans = c
else:
    ans = a
    wc = c - a

if wc > 0:
    if b >= wc:
        ans += wc
    else:
        ans += b + 1

ans += b

# Output
print(ans)


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

 using namespace std;
 typedef long long ll;
 #define rep(i, n) for(int i = 0; i < (int)(n); i++)

 int main() {
   int N, ans = 0;
   cin >> N;
   map<int, int> A;

   rep(i, N) {
     int tmp;
     cin >> tmp;
     A[tmp]++;
     A[tmp] %= 2;
   }

   for(auto p: A) {
     ans += p.second;
   }

   cout << ans << endl;
 }


Measured memory_bytes: 4864
#include<stdio.h>
int main(){
  int i,j;
  int c[3][3];
  for(i=0;i<3;i++)
    for(j=0;j<3;j++)
      scanf("%d",&c[i][j]);
  int a[3],b[3];
  a[0]=(c[0][0]-c[1][0]+c[1][1]-c[0][1])/2;
  b[0]=c[0][0]-a[0];
  a[1]=a[0]+c[1][0]-c[0][0];
  b[1]=c[1][1]-a[1];
  a[2]=a[0]+c[2][1]-c[0][1];
  b[2]=c[2][2]-a[2];
  for(i=0;i<3;i++)
    for(j=0;j<3;j++)
      if(a[i]+b[j]!=c[i][j]){
        puts("No");
        return 0;
      }
  puts("Yes");
  return 0;
}


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

int main() {
  long long a;
  string s;
  cin>>a>>s;
  long long count=0;
  for(int i=0;i<1000;i++){
    int c[3]={i/100,(i/10)%10,i%10};
    int cou=0;
    rep(j,a){
      if(s.at(j)==('0'+c[cou])) cou++;
      if(cou==3) break;
    }
    if(cou==3) count++;
  }
  cout<<count<<endl;

}


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

#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#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))

const ll MOD = 1000000007;

ll pow(ll x, ll y, ll z) {
    ll ret;
    if (y == 0) {
        return 1;
    } else if (y == 1) {
        return x % z;
    } else if (y % 2) {
        ret = pow(x, y/2, z);
        ret = ret * ret % z * x % z;
        return ret;
    } else {
        ret = pow(x, y/2, z);
        ret = ret * ret % z;
        return ret;
    }
}

int main(){
    ll N;
    ll i, j, k;

    cin >> N;
    
    vll Ts(N, 0); 
    vll As(N, 0);

    rep(i, N){
        cin >> Ts[i];
    }
    rep(i, N){
        cin >> As[i];
    }

    if (N == 1) {
        cout << (As[0] == Ts[0]) << endl;
        return 0;
    }


    ll m = max(Ts[0], As[0]);
    rep(i, N){
        if (m != max(Ts[i], As[i])) {
            cout << 0 << "\n";
            return 0;
        }
    }


    vll hs(N, 0);
    hs[0] = Ts[0];
    hs[N-1] = As[N-1];
    rep(i, N-1){
        if (Ts[i+1] > Ts[i]) {
            hs[i+1] = Ts[i+1];
        }
    }
    
    for (i = N-2; i >= 0; i--) {
        if (As[i] > As[i+1]) {
            if(hs[i] == 0){
                hs[i] = As[i];
            }
            else if (hs[i] != As[i]){
                cout << 0 << '\n';
                return 0;
            }
        }
    }

    ll cummax = hs[0];
    rep(i, N-1){
        cummax = max(cummax, hs[i+1]);
        if (Ts[i+1] != cummax) {
            cout << 0 << '\n';
            return 0;
        }
    }
    
    cummax = hs[N-1];
    for (i = N-2; i >= 0; i--) {
        cummax = max(cummax, hs[i]);
        if (cummax != As[i]) {
            cout << 0 << '\n';
            return 0;
        }
    }

    ll prev = 0;
    ll ans = 1;
    i = 0;
    while (i < N) {
        while (i < N && hs[i] != 0) {
            i++;
        }
        prev = i - 1;
        while (i < N && hs[i] == 0) {
            i++;
        }
        if (i == N){
            break;
        }

        // cout << hs[i] << ',' << hs[prev] << endl;
        ans *= pow(min(hs[i], hs[prev]), i - prev - 1, MOD);
        // cout << ans << ' ';
        ans %= MOD;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5632