akhauriyash/Code-Regression huggingface dataset:
/*
 *
 *   Author     : Amit Kumar
 *   Date    	: August 30 , 2019
 * 
 */

#include <climits>
#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 <ctime>
#include <memory.h>
#include <cassert>
#define FAST_INPUT_OUTPUT
//#define MORE_THAN_ONE_TESTCASE // COMMENT IT

#define vi vector<int>
#define vl vector<long long>
#define mii map<int , int>
#define mll map<long long , long long>
#define msi map<string , i>
#define msl map<string , long long>
#define umii unordered_map<int,int>
#define umll unordered_map<long long ,long long>
#define umsi unordered_map<string , int>
#define umsl map<string , long long> 
#define si set<int>
#define sl set<long long>
#define pii pair<int , int >
#define psi pair<string,int>
#define psl pair<string , long > 
#define pll pair<long long , long long>
#define vpii vector<pii>
#define vpll vector<pll>
#define vpsi vector<psi>
#define vpsl vector<psl>
#define pqi priority_queue<int>
#define pql priority_queue<long long>
#define ub upper_bound
#define lb lower_bound
#define bint long long int
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define iv(v) for(auto &i:v){cin>>i;}
#define ov(v) for(auto i:v){cout<<i<<" ";}cout<<endl;
#define ovn(v) for(auto i:v){cout<<i<<endl;}
#define euv(v) for(auto i:v){cerr<<i<<" ";}cerr<<endl;
#define eovn(v) for(auto i:v){cerr<<i<<endl;}
#define os(s) for(auto itr:s){cout<<itr<<" ";}cout<<endl;
#define osn(s) for(auto itr:s){cout<<itr<<endl;}
#define eos(s) for(auto itr:s){cerr<<itr<<" ";}cerr<<endl;
#define eosn(s) for(auto itr:s){cerr<<itr<<endl;}
#define rep(i,x) for(auto (i)=0 ; (i)<(x); ++(i))
#define _rep(a,b) for(auto i=(a); i<(b); ++i)
#define ef else if
#define wh while
#define el else
#define ivv(x) int x; cin>>x
#define lv(x) bint x; cin>>x
#define sv(x) string x; cin>>x
#define cv(x) char x; cin>>x
#define fv(x) float x; cin>>x
#define dv(x) double x; cin>>x
#define endl '\n'
using namespace std;






auto SOLUTION_FUNCTION( void ) ->void {
    // your solution goes here 

    sv(s);
    int ans = INT_MAX;
    for(int i=0; i<s.size()-2;++i){
        int x = 0;
        x = x + (s[i]-'0');
        x*=10;
        x = x + (s[i+1]-'0');
        x*=10;
        x = x + (s[i+2]-'0');
        ans = min (ans , abs(753-x));
    }
    cout<<ans<<endl;
    return ;
}




int main(void){
#ifdef FAST_INPUT_OUTPUT
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout<<setprecision(10);
    cout<<fixed;
    cout<<boolalpha;
#endif
#ifdef MY_LOCAL_PROJECT
    freopen("input","r",stdin);
    freopen("output","w",stdout);
#endif
    int testcase = 1;


#ifdef MORE_THAN_ONE_TESTCASE
    cin>>testcase;
#endif
    
    while(testcase--){
        SOLUTION_FUNCTION();
    }

#ifdef MY_LOCAL_PROJECT
    cout<<"Time : "<<1.0*(double)clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
 using namespace std;
 typedef long long ll;
 const int maxn=1e5+10;
 int main()
 {
 	int n;
 	cin>>n;
 	while(n){
 		if(n%10==7){
 			cout<<"Yes";
 			return 0;
		 }
		n/=10;
	 }
	 cout<<"No";
 	return 0;
 }

Measured memory_bytes: 3104
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long Read() {
    long long x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}
int main() {
    int a=Read(),b=Read();
    if (a > 0 && b > 0) {
        cout << "Positive" << endl;
    } else if (max(a, b) >= 0 && min(a, b) <= 0 || a == 0 || b == 0) {
        cout << "Zero" << endl;
    } else {
        if ((abs(min(a, b)) - abs(max(a, b))) % 2 == 0) {
            cout << "Negative" << endl;
        } else {
            cout << "Positive" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<N;i++)
using namespace std;
long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;


int main(){

int N;
cin>>N;
string s;
cin>>s;

if(N%2==1){
    cout<<"No"<<endl;
    return 0;
}
else{
    char t[N/2];
    rep(i,N/2){
    t[i]=s[i];
    }
    for(int i=0;i<N/2;i++){
        if(s[i+(N/2)]!=t[i]){
            cout<<"No"<<endl;
        return 0;
        }
    }
    cout<<"Yes";

}


 return 0;
}
/*
6
abcabc

Yes

6
abcadc

No

1
z

No
*/

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int H, W;
	while (cin >> H >> W) {
		if (H == 0 && W == 0) {
			break;
		}
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				cout << "#";
			}
			cout << endl;
		}
		cout << endl;
	}
}

Measured memory_bytes: 1152
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 1123456789012345
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;
typedef std::pair<LL, LL> P;
struct edge { LL to, cost; };

LL N, a[112345], b[112345], c[112345], Q, K, x[112345], y[112345];
LL d[112345];
std::vector<edge>G[112345];

void dijkstra(LL s)
{
	std::priority_queue<P, std::vector<P>, std::greater<P>>que;
	std::fill(d, d + N + 1, INF);
	d[s] = 0;
	que.push(P(0, s));
	while (!que.empty())
	{
		P p = que.top(); que.pop();
		LL v = p.second;
		if (d[v] < p.first) { continue; }
		rep(i, G[v].size())
		{
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

int main()
{
	in >> N;
	rep(i, N - 1)
	{
		in >> a[i] >> b[i] >> c[i];
		G[a[i]].push_back({ b[i],c[i] });
		G[b[i]].push_back({ a[i],c[i] });
	}
	in >> Q >> K;
	rep(i, Q) { in >> x[i] >> y[i]; }

	dijkstra(K);

	rep(i, Q) { out << d[x[i]] + d[y[i]] << std::endl; }
	return 0;
}

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

x, y = LI()
for i in range(x+1):
    if 2*i + 4*(x-i) == y:
        print('Yes')
        quit()
print('No')

Measured memory_bytes: 65316
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int l = 0;
        int r = 0;
        for (int i = 0; i < n; i++) {
            if(s.charAt(i) == '(') l++;
            else if(0 < l) l--;
            else r++;
        }
        for (int i = 0; i < r; i++) {
            s = "(" + s;
        }
        for (int i = 0; i < l; i++) {
            s = s + ")";
        }
        System.out.println(s);
        sc.close();

    }

}


Measured memory_bytes: 22740
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include <iomanip>
#include <cmath>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60


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

	int N; cin >> N;

	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		int num = i;
		int dig = 0;
		while (num > 0) {
			num /= 10;
			dig++;
		}

		if (dig % 2 == 1) cnt++;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int A,B,C ;
    cin>>A>>B>>C;
    if(A==B)
    {
        cout<<C;
    }
    else if(A==C)
    {
        cout<<B;
    }
    else
        cout<<A;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define ff first
#define pb push_back
#define ss second
#define maxn 500005
using namespace std;

int n, m, k;
vector<string>v;
int res[500][500], cum[500][500];

bool valid(int x, int y){
    if(x< n && x >= 0 && y < m && y >= 0){
        if(v[x][y] == '.' && !res[x][y]) return true;
        else return false;
    }
    return false;
}

int findLeft(int x, int y){
    int pt;
    pt  = y;
    while(1){
        if(!valid(x, pt - 1)) break;
        pt --;
    }
    return pt;
}

int findRight(int x, int y){
    int pt;
    pt  = y;
    while(1){
        if(!valid(x, pt + 1)) break;
        pt ++;
    }
    return pt;
}

bool canTake(int l, int r, int x){
    int sum = cum[x][r+1] - cum[x][l];
    //cout << l << " "<< r << " "<< x << endl;
    //cout << sum << endl;
    if(sum == 0) return true;
    return false;
}
void color(int l, int r, int x){
    for(int i=l;i<=r;i++){
        if(!res[x][i])res[x][i] = k;
    }
    return ;
}

int main(){
    memset(res, 0, sizeof res);
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        string s;
        cin >> s;
        v.pb(s);
    }
    for(int i=0;i<n;i++){
        int cnt = 0;
        for(int j=0;j<m;j++){
            if(v[i][j] == '#')cnt++;
            cum[i][j+1] = cnt;
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(v[i][j] == '#'){
                int l = findLeft(i, j);
                int r = findRight(i, j);
                //cout << i << " ++ "<< j << endl;
                //cout << l << " -> "<< r << endl;
                color(l, r, i);//
                for(int p=i-1;p>=0;p--){
                    if(canTake(l, r, p)){
                        color(l, r, p);
                    }
                    else{
                        break;
                    }
                }
                for(int p=i+1;p<n;p++){
                    if(canTake(l, r, p)){
                        color(l, r, p);
                    }
                    else{
                        break;
                    }
                }
                k--;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int N = 305, M = 1 << 6 | 5;
int n, C, S, l[N];
double Ans, f[M][N];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d%d",&n,&C); S=1<<(n-1);
	for(int i=0; i<n; i++) scanf("%d",&l[i]);
	int ct=0; sort(l,l+n); while(true){
		memset(f,0,sizeof(f));
		f[0][l[n-1]*n] = true;
		for(int i=1,x; i<=C*n; i++)
		if((x=i%n-1)>=0) 
		for(int j=i; j<=C*n; j++)
		for(int k=0; k<S; k++) if(k>>x&1^1)
		f[k|(1<<x)][min(C*n,max(j,i+l[x]*n))]+=f[k][j];
		Ans+=f[S-1][C*n]; ++ct;
		if(!next_permutation(l,l+n-1)) break;
	} printf("%.13lf",Ans/pow(C,n-1)/ct);
	return 0;
}

Measured memory_bytes: 512
N = int(input())
p = [0] + list(map(int,input().split()))
count = 0 #あるべきでないところにある数の個数
for i in range(1,N+1,1):
    if i != p[i]:
        count+=1

if count <= 2:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define all(a) a.begin(),a.end()
typedef long long ll;
 
int main(void){
    int n;
    cin>>n;
    vector<ll> a(n+2);
    ll sum[2] = {};
    rep1(i,n){
        cin>>a[i];
        sum[i%2] += max(a[i],0LL);
    }
 
    // 全て負
    if(all_of(all(a), [](ll x){return x<=0;})){
        int pos = max_element(a.begin()+1, a.end()-1) - a.begin();
        cout<<a[pos]<<endl<<n-1<<endl;
        for(int i=n; i>pos; i--){
            cout<<i<<endl;
        }
        rep1(i,pos-1){
            cout<<1<<endl;
        }
        return 0;
    }

    int mod = (sum[0] > sum[1]) ? 1 : 0;
    rep1(i,n)if(i%2 == mod){
        a[i] = -1;
    }
 
    cout<<max(sum[0],sum[1])<<endl;
    vector<int> res;
 
    // 最初の正まで左端を選択
    int pos = 1;
    while(a[pos] < 0){
        res.push_back(1);
        pos++;
    }

    pos += 2;    
    while (pos <= n+1) {
        if (a[pos] < 0) {
            res.push_back(3);
            if (pos == n) {
                res.push_back(2);
            }
        } else {
            res.push_back(2);
        }
        pos += 2;
    }
 
    cout<<res.size()<<endl;
    for(int x : res){
        cout<<x<<endl;
    }
    return 0;
}

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

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a==b&&a!=c) cout<<"Yes"<<endl;
  else if(a==c&&a!=b) cout<<"Yes"<<endl;
  else if(c==b&&a!=b) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
w = list(map(int, input().split()))
w_list = []
for i in range(n):
    w_list.append([w[:i],w[i:]])
del w_list[0]
l = []
for j in w_list:
    l.append(abs(sum(j[0])-sum(j[1])))
print(min(l))

Measured memory_bytes: 9180
S = input()

ans = 'AC'

if S[0] != 'A':
    ans = 'WA'
cnt = 0
for i in range(1, len(S)):
    if S[i].isupper():
        if i == 1 or i == len(S) - 1 or S[i] != 'C':
            ans = "WA"
        cnt += 1

if cnt != 1:
    ans = "WA"
    
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define itc ll t;cin>>t;while(t--)
#define otc ll t=1;while(t--)
#define ll long long int
#define ld long double
#define pb push_back
#define gcd(a,b) __gcd(a,b)
#define fi first
#define se second
#define ull unsigned long long int
#define memset(arr) memset(arr, 0, sizeof(arr));
bool sortinrev(const pair<ll, ll> &a, const pair<ll, ll> &b)
{return (a.fi > b.fi);}//sort by first in descending order
bool sortbysec(const pair<ll, ll> &a, const pair<ll, ll> &b)
{ return (a.se < b.se); }//sort by second in ascending order
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};

int main()
{
   int k;
   string s;
   cin>>k>>s;
   if(s.length()<=k)
   cout<<s<<endl;
   else
   {
       cout<<s.substr(0,k)<<"..."<<endl;
   }
    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mp make_pair
 
typedef long long ll;
typedef unsigned long long int ull;
typedef long double ld;
 
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<string, string> ss;
typedef pair<int, ss> iss;
 
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<ld> vld;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pair<int, pii>> vpiii;
 
typedef map<string, string> mss;
typedef map<string, int> msi;
typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<int, ll> mill;
typedef map<int, vpii> mivpii;

const int MAX = 1e5;

int a[MAX + 1];
int dp[MAX + 1];

void fast_io() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main() {
	fast_io();
//	freopen("input/dp_a.txt", "r", stdin);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	for(int i = 2; i <= n; i++) {
		dp[i] = INT_MAX;
	}

	for(int i = 1; i <= n; i++) {
		if(i >= 2) dp[i] = min(dp[i], dp[i - 1] + abs(a[i] - a[i - 1]));
		if(i >= 3) dp[i] = min(dp[i], dp[i - 2] + abs(a[i] - a[i - 2]));
	}
	cout << dp[n] << '\n';
	
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
	int a,b,i;
	scanf("%d %d",&a,&b);
	for(i=10;i<1263;i++){
		float c=i*0.08,d=i*0.1;
			if((int)c == a && (int)d == b){
				printf("%d",i);
				return 0;
			}
	}
	printf("-1");
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

using namespace std;

#define LL long long

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

int n, q;
LL *d;
LL ni;
LL xi, mi;
LL dSum = 0;

LL query(LL ni, LL xi, LL mi) {
	LL loopN = (ni - 1) / (LL)(n);
	dSum = 0;
	LL zCount = 0;
	for (int i = 0; i < n; ++i) {
		dSum += (d[i] % mi);
		if (d[i] % mi == (LL)(0)) {
			zCount += 1;
			dSum += mi;
		}
	}
	// cout << "dSum = " << dSum << endl;
	LL total = loopN * dSum;
	for (int i = 0; i < int((ni - 1) % (LL)(n)); ++i) {
		total += (d[i] % mi);
		if (d[i] % mi == (LL)(0)) {
			// dSum += mi;
			total += mi;
		}
	}
	// cout << "total = " << total << endl;
	LL res = ni - 1;
	xi = xi % mi;
	// how many times we cross mi, from xi to xi + total?
	res -= ((xi + total) / mi);
	return res;

}
int main() {
	cin >> n >> q;
	d = new LL[n];
	for (int i = 0; i < n; ++i) {
		cin >> d[i];
		dSum += d[i];
	}
	// prepare();
	for (int i = 0; i < q; ++i) {
		cin >> ni;
		cin >> xi >> mi;

		cout << query(ni, xi, mi) << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define tarce(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define pb push_back
#define inf 2e18
#define scan() int n; cin>>n ; int a[n+1]; for(int i = 1 ; i<=n ; i++) cin>>a[i]
#define scan2() int n,k; cin>>n>>k ; int a[n+1]; for(int i = 1 ; i<=n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define mem(a,v) memset(a,v,sizeof(a))
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void ZZ(const char* name, Arg1&& arg1){std::cerr << name << " = " << arg1 << endl;}
template <typename Arg1, typename... Args>void ZZ(const char* names, Arg1&& arg1, Args&&... args)
{
    const char* comma = strchr(names + 1, ',');
    std::cerr.write(names, comma - names) << " = " << arg1;
    ZZ(comma, args...);
}

#define N 200005

void solve(){
    int n;
    cin >> n;
    for(int i=1; i<=10; i++){
        if(1000*i >=n){
            int ans=(1000*i)-n;
            cout << ans << '\n';
            return;
        }
    }
    //cout << ans << '\n';
}




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

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

}

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

signed main() {
    int N, T;
    cin >> N >> T;
    vector<pair<int, int>> v(N);
    for (size_t i = 0; i < N; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
    int DP[10000] = {};
    for (size_t i = 0; i < N; i++) {
        int A = v[i].first;
        int B = v[i].second;
        for (int i = T - 1; i >= 0; i--) {
            DP[i + A] = max(DP[i + A], DP[i] + B);
        }
    }
    cout << *max_element(DP, DP + 10000) << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  int K, N;
  cin >> K >> N;
  int A[N];
  for(int i=0; i<N; i++) cin >> A[i];
  
  int lenght=A[N-1]-A[0];
  for(int i=1; i<N; i++){
    int x=K-(A[i]-A[i-1]);
    if(lenght > x) lenght = x; 
  }
  
  cout << lenght << endl;
}


Measured memory_bytes: 1024
import java.util.*;
import java.math.BigInteger;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    BigInteger[] A = new BigInteger[n];
    BigInteger max = new BigInteger("1000000000000000000");
    for (int i = 0; i < n; i++) {
      A[i] = sc.nextBigInteger();
    }
    Arrays.sort(A);
    BigInteger ans = BigInteger.ONE;
    for (int i = 0; i < n; i++) {
      ans = ans.multiply(A[i]);
      if (ans.compareTo(max) == 1 || ans.equals(0)) {
        break;
      }
    }
    if (ans.compareTo(max) == 1) {
      System.out.println(-1);
    } else {
      System.out.println(ans);
    }
  }
}


Measured memory_bytes: 68224
x1,y1,x2,y2 = map(int,input().split())
difx = x2 - x1
dify = y2 - y1
x3 = x2 - dify
y3 = y2 + difx
x4 = x1 - dify
y4 = y1 + difx
print(x3,y3,x4,y4)

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

using namespace std;

int main(){
    int n;
    int a[120] = {0};
    cin >> n;
    for(int b = 0; b < n; b++)cin >> a[b + 1];

    int c = 1;
    int d = 1;
    int ans = 0;
    while(c <= n + 1){
        if(a[c] == a[c - 1])d++;
        else{
            if(d != 1){
                ans += d/2;
                d = 1;
            }
        }
        c++;
    }
    cout << ans << endl;
    return 0;
}

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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cerr << (*begin) << " ";
    *begin++;
  }
  cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cerr << " " << Array[i][j];
    }
    cerr << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

string s;

signed main() {
  cin >> s;
  string a = s.substr(0, 2);
  string b = s.substr(2, 2);

  bool yymm = false;
  bool mmyy = false;

  if (a >= "00" and a <= "99" and b >= "01" and b <= "12") {
    yymm = true;
  }
  if (b >= "00" and b <= "99" and a >= "01" and a <= "12") {
    mmyy = true;
  }

  if (yymm and mmyy) {
    puts("AMBIGUOUS");
  } else if (yymm) {
    puts("YYMM");
  } else if (mmyy) {
    puts("MMYY");
  } else {
    puts("NA");
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
  #include "_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v) {
    for (auto &e : t) fill(e, v);
}
// auto v = make_vec<int>(h, w);
// fill(v, 0);  

signed main(){

  int n; cin >> n;
  auto v = make_vec<int>(2, 3);
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < 3; j++){
      cin >> v[i][j];
    } 
  }

  int N = n;
  for(int i = 0; i < 2; i++){
    vector<int> dp(N + 1);
    iota(dp.begin(), dp.end(), 0);  
    for(int j = 0; j < 3; j++){
      int lost = v[i][j], add = v[i^1][j];
      for(int k = lost; k <= N; k++){
        dp[k] = max(dp[k], dp[k - lost] + add);
      }
    }
    N = dp[N];
  }
  cout << N << endl;

  return 0;
}

Measured memory_bytes: 198508
import io

data = int(input())
array = list(map(int,input().split()))
array.sort()
modulus = 10**9 + 7
result = (2 ** (data // 2)) % modulus
array2 = []
for i in range(data):
  array2 += [abs(data+1-2*(i+1))]
array2.sort()
if array == array2 :
  print(result)
else:
  print(0)

Measured memory_bytes: 13880
#include <bits/stdc++.h>
using namespace std;
int main () {
    string S;
    cin >> S;
    map<char, int> m;
    for (auto c: S) m[c]++;
    bool f = 1;
    if (m['N']*m['S'] == 0 && m['N']+m['S'] != 0) {
        f = 0;
    }
    if (m['W']*m['E'] == 0 && m['W']+m['E'] != 0) {
        f = 0;
    }
    if (f) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 256
a = [int(x) for x in input().split()]
if a[0] >= a[1]:
  if a[0] >= a[2] and a[2] >= a[1]:
    print("Yes")
  else:
    print("No")
else:
  if a[1] >= a[2] and a[2] >= a[0]:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            var list = new List<int>();
            for (int i = 1; i <= 40; i++)
                for (int j = 2; j <= 10; j++)
                    list.Add((int)Math.Pow(i, j));
            Console.WriteLine(list.Where(x => x <= n && x > 0).Max());
        }
    }
}

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

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i,n){
        cin >> l.at(i);
    }
    //降順でソートする
    sort(l.rbegin(), l.rend());


    int ans =0;
    rep(i,k){
        ans += l.at(i);
    }
    cout << ans << endl;
}

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

int main()
{
	int n, m;
	cin >> n >> m;
	int h[100001];
	vector<int> michi[100001];
	for (int i = 1; i <= n; ++i)
	{
		cin >> h[i];
	}
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		michi[a].push_back(b);
		michi[b].push_back(a);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		int flag = 1;
		for (int j = 0; j < michi[i].size(); ++j)
		{
			if (h[i] <= h[michi[i][j]])
			{
				flag = 0;
				break;
			}
		}
		ans += flag;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9152
#include <stdio.h>

int main(void) {
	int W, H, x, y, r;

	scanf("%d", &W);
	scanf("%d", &H);
	scanf("%d", &x);
	scanf("%d", &y);
	scanf("%d", &r);

	if (x-r >= 0 && x+r <= W && y-r >= 0 && y+r <= H){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1000000007;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX*/                      ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
/*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int main(){
    ll n,m;
    cin >> n >> m;
    ll ans = min(m/2,n);
    n-=ans;
    m = m-ans*2;
    ans+=m/4;
    cout << ans << endl;

}



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

int main()
{
    int N;
    int A;
    cin >> N;
    cin >> A;

    string ans = "No";

    for (int i = 0; i <= A; i++) {
        int remain = N - i;
        if (remain % 500 == 0) {
            ans = "Yes";
            break;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
#include <algorithm>

using namespace std;

int main() {

	int n[5];

	for (int i = 0; i < 5; i++) {
		scanf("%d", &n[i]);
	}

	printf("%d\n", n[0] - max((int)ceil((double)n[1] / n[3]), (int)ceil((double)n[2] / n[4])));

	return 0;
}

Measured memory_bytes: 2756
#include <bits/stdc++.h>
#define ll long long
#define fastIO cout << fixed << setprecision(15), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

const double PI = acos(-1);

int main() {
	fastIO;
#ifdef LOCAL
	freopen("input.in", "rt", stdin);
#endif
	int a, b, h, m;
	cin >> a >> b >> h >> m;
	double f = 360.0 / (1.0*12*60);
	double ff = 360/60;
	double angA = (m + h*60) * f;
	double angB = 1.0*m * ff;
	double ang = 0;
	if(angA > angB)
		ang = angA - angB;
	else
		ang = angB - angA;
	while(ang > 360)
		ang -= 360;
	cout << sqrt(a*a + b*b - 2*a*b*cos(ang * PI / 180.0));
	return 0;
}


Measured memory_bytes: 4180
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys


def std_in():
    return sys.stdin.readline().strip()


def get_ints():
    return map(int, sys.stdin.readline().strip().split())


def main():
    n = int(std_in())

    flag = 0
    for ni in range(n):
        d1, d2 = get_ints()
        if d1 == d2:
            flag += 1
        else:
            flag = 0
        if flag >= 3:
            print("Yes")
            break
    else:
        print("No")


if __name__ == "__main__":
    main()


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

int graph[101][101], d[101], n, color[101], queue[10000], head, tail;

void enqueue(int key) {
    queue[tail++] = key;
}

int dequeue() {
    return queue[head++];
}

void bfs() {
    int i, u;
    for (i = 2; i <= n; i++) {
        color[i] = 1;
        d[i] = -1;
    }
    color[1] = 0;
    head = 0;
    tail = 0;
    enqueue(1);
    while (head <= tail) {
        u = dequeue();
        for (i = 1; i <= n; i++) {
            if (graph[u][i] == 1) {
                if (color[i] == 1) {
                    color[i] = 0;
                    d[i] = d[u] + 1;
                    enqueue(i);
                }
            }
        }
        color[u] = -1;
    }
}

int main(void){
    int dd, i, a, j, n2;
    
    scanf("%d", &n);
    
    for (i = 1; i <= 100; i++) {
        for (j = 1; j <= 100; j++) {
            graph[i][j] = 0;
        }
    }
    
    for (i = 0; i < n; i++) {
        scanf("%d %d", &dd, &n2);
        for (j = 0; j < n2; j++) {
            scanf("%d", &a);
            graph[dd][a] = 1;
        }
    }
    
    bfs();
    
    for (i = 1; i <= n; i++) {
        printf("%d %d\n", i, d[i]);
    }
    
    return 0;
}




Measured memory_bytes: 2128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n,x;
    while(cin >> n >> x && (n != 0 || x != 0))
    {
        int ans = 0;
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                for(int k = 1;k <= n;k++)
                {
                    if(i == j || j == k || i == k)
                    {
                        continue;
                    }
                    if(i + j + k == x)
                    {
                        ans++;
                    }
                }
            }
        }
        cout << ans / 6 << "\n";
    }

    return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <map>

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

string gtp = "spr";

int main(){
    ll N,K;
    cin >> N >> K;
    
    ll point[3];
    REP(i,3)cin >> point[i];

    string t;
    cin >> t;

    ll res = 0;
    REP(i,N)
    {
      if(i >= K && t[i] == t[i - K])
      {
        t[i] = '*';
        continue;
      }

      REP(j,3)
      {
        if(t[i] == gtp[j])
        {
          res += point[j];
        }
      }
    }

    cout << res << endl;

    return 0;    
}



Measured memory_bytes: 512
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#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 <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<vector<vector<int>>> v3int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef vector<vector<vector<ll>>> v3ll;
typedef list<int> liint;
typedef pair<int, int> pint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<ll, int>> vpll_int;
typedef vector<pair<int, ll>> vpint_ll;
typedef set<pair<int, int>> spint;
typedef set<pair<ll, int>> spll;
typedef unordered_map<int, unordered_set<int>> Graph;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vll A(N);
    rep(i, N) cin >> A[i];
    vll S(N + 1);
    rep(i, N) {
        S[i + 1] = A[i] + S[i];
    }

    ll ans = 0;
    ll p = 1000000007;
    rep(i, N) {
        ans = ans + (((A[i] % p) * ((S[N] - S[i + 1]) % p)) % p);
        ans %= p;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6336
a, b, c = gets.chomp.split(" ").map { |n| n.to_i}

ab = a + b
bc = b + c
ac = a + c

if ab < bc && ab < ac
	p ab
elsif bc < ab && bc < ac
	p bc
elsif ac < bc && ac < ab
	p ac
elsif ab == bc && bc == ac && ac == bc
	p ac 
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#include<algorithm>	
using namespace std;
#define ll long long 
vector<vector<int>> l(100001);
//int used[100001][100001];
int col[100001];
const int MAX = 510000;
const int MOD = 1000000007;

int main() {
  int a;
  cin >> a;
  int res = a + a*a + a*a*a ;
  cout << res;
                         
}




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

using namespace std;

template<typename input_Integer>
vector<input_Integer> is_Prime(input_Integer N){


    vector<input_Integer> Prime;
    vector<bool> check(N+1,true);
    check[0]=false;
    check[1]=false;


    for(input_Integer i = 2; i * i <= N; ++i){
        if(check[i]){
            for(input_Integer k = i * 2; k < N; k += i){
                check[k] = false;
            }
        }
    }


    for(input_Integer i=2;i<N;++i){
        if(check[i]){
            Prime.emplace_back(i);
        }
    }

    return Prime;
}


int main(){
    int Q;
    cin>>Q;
    vector<int> Prime;
    Prime=is_Prime(100000);
    vector<bool> check(100001);

    for(int x :Prime){
        check[x]=true;
    }

    for(int i=100000;i>=0;--i){
        if(check[i]){
            check[i]=check[(i+1)/2];
        }
    }
    
    vector<int> niteru;

    for(int i=0;i<100000;++i){
        if(check[i]){
            niteru.emplace_back(i);
        }
    }

    int l,r;
    for(int i=0;i<Q;++i){
        cin>>l>>r;
        int ans=upper_bound(niteru.begin(),niteru.end(),r)-lower_bound(niteru.begin(),niteru.end(),l);

    cout<<ans<<endl;

    }

}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define loop2(i, s, n, a) for (int i = int(s); i < int(n); i += a)
#define loop(i, s, n) loop2(i, s, n, 1)
#define rep(i, n) loop(i, 0, n)

#define pb push_back
#define all(in) in.begin(),in.end()

using ll = long long;
using ull = unsigned long long;
using namespace std;

const int MOD = 1e9+7;
const int MAX = 100100;

long long fac[MAX], finv[MAX], inv[MAX];
// 前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数の計算
long long COM(int n, int k){
    if (n < 0 || k < 0 || n < k) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    ll n, k; cin >> n >> k;
    vector<int> a(n); rep(i,n) cin >> a[i];

    sort(all(a));
    COMinit();

    ll ans = 0;
    rep(i,n){
        ans += (-a[i]+a[n-1-i])*COM(n-1-i,k-1);
        ans %= MOD;
      	if(ans < 0) ans += MOD;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5908
N = int(input())
T= [0]*N
for i in range(N):
    T[i] = int(input())
T.sort(reverse=True)
def gcd(n,m):
    while m > 0:
        n , m = m , n%m
    return n
def lcm(n,m):
     x = n*m//gcd(n,m)
     return x
for i in range(N-1):
    T[i+1] = lcm(T[i],T[i+1])
print(T[N-1])

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmpStr = br.readLine().split(" ");
		
		int n = Integer.parseInt(tmpStr[0]);
		int p = Integer.parseInt(tmpStr[1]);
		
		int[] numOfBiscuits = new int[n];
		
		tmpStr = br.readLine().split(" ");
		//int[] count = new int[101];
		int odd = 0,even = 0;
		

		for(int i = 0; i < n; i++){
			numOfBiscuits[i] = Integer.parseInt(tmpStr[i]);
			if(numOfBiscuits[i]%2 == 0) even++;
			else odd++;
		}
		long result = (long)Math.pow(2, even);
	/*	if(even == 0){
			result = 0;
		}*/
		long oddResult = 0;
		if(p == 0){
			for(int i = 0; i <= odd ; i+=2){
				oddResult += combination6(odd, i);
			}
		}
		
		else if(p == 1){
			for(int i = 1; i <= odd ;i+=2){
				oddResult += combination6(odd, i);
			}
		}
		
		result *= oddResult;
		System.out.println(result);
	}
	
	static long combination6 (int n, int p){
		long result = 1;

		if(p > n-p){
			p = n-p;
		}

		for(int i = 1; i <= p ; i++){
			result *= (n - i + 1);
			result /= i;
		}

		return result;
	}

}


Measured memory_bytes: 21204
using System;
using System.Linq;

class DP {
    static void Main(string[] args) {
        var st = Console.ReadLine().Split().Select(long.Parse).ToArray();
        long N = st[0];
        long W = st[1];
        var w = new long[N];
        var v = new long[N];
        for (int i = 0; i < N; i++) {
            var x = Console.ReadLine().Split().Select(long.Parse).ToArray();
            w[i] = x[0];
            v[i] = x[1];
        }

        //考えうる価値の最大値
        long max_value = N * 1000 + 100;

        //少し大きめに配列を確保
        var dp = new long[N + 2, max_value + 10];

        long max_weight = 1000000000L * N + 100L;

        //値は全て大きな値で初期化する
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= max_value; j++) {
                dp[i, j] = max_weight;
            }
        }
        for (int i = 0; i < N; i++) {
            dp[i, 0] = 0;
        }
        for (int j = 1; j < max_value; j++) {
            if (j <= v[0]) {
                dp[0, j] = w[0];
            } else {
                dp[0, j] = max_weight;
            }
        }

        for (int i = 0; i < N - 1; i++) {
            for (int j = 0; j <= max_value; j++) {
                long kari = dp[i, j];
                if (j - v[i + 1] >= 0) {
                    kari = Math.Min(kari, dp[i, j - v[i + 1]] + w[i + 1]);
                }
                dp[i + 1, j] = kari;
            }
        }

        long ans = 0;

        for (int j = 0; j <= max_value; j++) {
            if (dp[N - 1, j] <= W) {
                ans = j;
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 90848
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
template <typename T>
struct range_chmin{
	int N;
	vector<T> ST;
	range_chmin(vector<T> A){
		int n = A.size();
		N = 1;
		while (N < n){
			N *= 2;
		}
		ST = vector<T>(N * 2 - 1, INF);
		for (int i = 0; i < n; i++){
			ST[N - 1 + i] = A[i];
		}
	}
	T operator [](int k){
		k += N - 1;
		T ans = ST[k];
		while (k > 0){
			k = (k - 1) / 2;
			ans = min(ans, ST[k]);
		}
		return ans;
	}
	void chmin(int L, int R, T x, int i, int l, int r){
		if (R <= l || r <= L){
			return;
		} else if (L <= l && r <= R){
			ST[i] = min(ST[i], x);
			return;
		} else {
			int m = (l + r) / 2;
			chmin(L, R, x, i * 2 + 1, l, m);
			chmin(L, R, x, i * 2 + 2, m, r);
			return;
		}
	}
	void chmin(int L, int R, T x){
		chmin(L, R, x, 0, 0, N);
	}
};
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> A(N - 2, N - 2);
  range_chmin<int> H(A), V(A);
  long long ans = (long long) (N - 2) * (N - 2);
  for (int i = 0; i < Q; i++){
    int d, x;
    cin >> d >> x;
    if (d == 1){
      int cnt = V[x - 2];
      ans -= cnt;
      H.chmin(0, cnt, x - 2);
    }
    if (d == 2){
      int cnt = H[x - 2];
      ans -= cnt;
      V.chmin(0, cnt, x - 2);
    }
  }
  cout << ans << endl;
}

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

const int INF = 1<<20;

int main(){
    int n,i,j,a,b;
    for(;cin >> n,n;){
        int m[100][100],rec[100],t[100][100],mv,ind;
        for(i=0;i<n;i++){
            rec[i] = 0;
            for(j=0;j<n;j++){
                m[i][j] = t[i][j] = 0;
            }
        }
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                cin >> m[i][j];
            }
        }
        for(i=0;i<n;i++){
            mv = INF, ind = 0;
            for(j=0;j<n;j++){
                if( m[i][j] < mv ) ind = 0;
                if( m[i][j] <= mv ){
                    mv = m[i][j];
                    rec[ind++] = j;
                }
            }
            for(j=0;j<ind;j++){
                t[i][ rec[j] ]++;
            }
        }
        for(i=0;i<n;i++){
            mv = -INF, ind = 0;
            for(j=0;j<n;j++){
                if( m[j][i] > mv ) ind = 0;
                if( m[j][i] >= mv ){
                    mv = m[j][i];
                    rec[ind++] = j;
                }
            }
            for(j=0;j<ind;j++){
                t[ rec[j] ][i]++;
            }
        }
        bool flg = false;
        for(i=0;i<n&&!flg;i++){
            for(j=0;j<n&&!flg;j++){
                if(t[i][j]/2){
                    cout << m[i][j] << endl;
                    flg = true;
                }
            }
        }
        if( !flg ) cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <queue>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int INF = 10000000;


int main(){
    int n;
    cin >> n;
    int x = n % 10;
    if(x == 3) cout << "bon" << endl;
    else if(x == 0 || x == 1 || x == 6 || x == 8) cout << "pon" << endl;
    else cout << "hon" << endl;
}


Measured memory_bytes: 3588
from sys import stdin
import math

EPS = 1e-10

class Vector:
    def __init__(self, x=None, y=None):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    # can't  apply "number * Vector" but "Vector * number"
    def __mul__(self, k):
        return Vector(self.x * k, self.y * k)

    def __truediv__(self, k):
        return Vector(self.x / k, self.y / k)

    def __gt__(self, other):
        return self.x > other.x and self.y > other.yb

    def __lt__(self, other):
        return self.x < other.x and self.y < other.yb

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    # usually cross operation return Vector but it returns scalor
    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def rotate(self, theta):
        return Vector(self.x * math.cos(theta)
                               - self.y * math.sin(theta),
                               self.x * math.sin(theta)
                               + self.y * math.cos(theta))

class Point(Vector):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

class Segment:
    def __init__(self, p1=Point(0, 0), p2=Point(1, 1)):
        self.p1 = p1
        self.p2 = p2

class Line(Segment):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > EPS:
        return 1
    elif a.cross(b) < -EPS:
        return -1
    elif a.dot(b) < -EPS:
        return 2
    elif a.norm() < b.norm():
        return -2
    else:
        return 0

def contains(P, p):
    n = len(P)
    count = 0
    for i in range(n):
        a = P[i]
        b = P[ (i + 1) % n ]
        if a.y > b.y:
            a, b = b, a
        if ccw(p, a, b) == 2 or p == a or p == b:
            return 1
        if ccw(p, a, b) == 1 and b.y > p.y and a.y <= p.y:
            count = count + 1
    if count % 2 == 0:
        return 0
    else:
        return 2

def read_polygon(n):
    P = []
    for _ in range(n):
        line = stdin.readline().strip().split()
        p = Vector(int(line[0]), int(line[1]))
        P.append(p)
    return P

def read_and_print_results(k, P):
    for _ in range(k):
        line = stdin.readline().strip().split()
        p = Vector(int(line[0]), int(line[1]))
        result = contains(P, p)
        print(result)

def __main():
    n = int(input())
    P = read_polygon(n)
    k = int(input())
    read_and_print_results(k, P)

if __name__ == '__main__':
    __main()


Measured memory_bytes: 5848