akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <stack>
#include <unordered_map>
#define lld long long int
#define dbg1(vari1) cerr<<#vari1<<" = "<<(vari1)<<endl;
#define dbg2(vari1,vari2) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<endl;
#define dbg3(vari1,vari2,vari3) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<" "<<#vari3<<" = "<<(vari3)<<endl;
using namespace std;
vector <int> v;
void Sieve(int n) 
{ 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        if (prime[p] == true) 
        { 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
       		v.push_back(p);
} 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	Sieve(1000000);
	cout << *lower_bound(v.begin(),v.end(),n);
}

Measured memory_bytes: 1916
#include<stdio.h>

#define MAX 100
#define INF 2001
#define NIL -1
#define WHITE 1
#define BLACK 2

void prim(int,int);

int d[MAX],pi[MAX],color[MAX];
int G[MAX][MAX];

int main(){
  int i,j,n,sum;

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

  prim(n,0);

  sum=0;

  for(i=0;i<n;i++){
    if(pi[i]!=NIL) sum+=G[i][pi[i]];
  }

  printf("%d\n",sum);

  return 0;
}

void prim(int n,int r){
  int i,u,mincost;

  for(i=0;i<n;i++){
    d[i]=INF;
    pi[i]=NIL;
    color[i]=WHITE;
  }

  d[r]=0;

  while(1){
    mincost=INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<mincost){
	mincost=d[i];
	u=i;
      }
    }

    if(mincost==INF) break;

    color[u]=BLACK;

    for(i=0;i<n;i++){
      if(G[u][i]==-1) continue;
      if(color[i]!=BLACK && G[u][i]<d[i]){
	pi[i]=u;
	d[i]=G[u][i];
      }
    }
  }
}
	



Measured memory_bytes: 2052
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
// int n, k, heights[100000] = {40, 10, 20, 70, 80, 10, 20, 70, 80, 60};
int n, k, heights[100005];
// int n, k, heights[100000] = {10, 30, 40, 50, 20};
std::vector<int> dp(100005,-1);

int min_cost(int ind)
{
	int branch_cost[k];
	if(dp.at(ind) != -1)
		return dp.at(ind);
	if(ind == n-1)
		return 0;
	if(ind >= n)
		return INT_MAX;

	for(int i=0; i<k; i++)
	{
		// cout<<"\n"<<heights[ind]<<"\t"<<heights[ind+1]<<"\t"<<heights[ind+2]<<endl;
		if(ind+i+1 < n)
		{
			// cout<<"\n i that passes : "<<ind;
			// cout<<"\n diff: "<<abs(heights[ind] - heights[ind+i+1]);
			branch_cost[i] = abs(heights[ind] - heights[ind+i+1]) + min_cost(ind+i+1);
			// cout<<"\nbranch cost for branch "<<i<<" "<<branch_cost[i];
		}
	}

	int min = INT_MAX;
	for(int i=0; i<k; i++)
	{
		if(branch_cost[i] < min && ind+i+1 < n)
			min = branch_cost[i];
	}

	dp.at(ind) = min;
	return min;
}

int main()
{
	// cout<<"Enter no of stones:";
	cin>>n;
	// n = 10;
	// n = 5;
	// cout<<"\nEnter K:";
	cin>>k;
	// k = 4;
	// k = 3;
	// cout<<"\nEnter heights:";
	for(int i=0; i<n; i++)
		cin>>heights[i];
	// heights = {10, 30, 40, 50, 20};

	// cout<<"\nmin_cost:"<<min_cost(0);
	cout<<min_cost(0);
}

Measured memory_bytes: 52244
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});
reader.on('line', (line) => {
    lines.push(line);
});
reader.on('close', () => {
    const s = lines[0];
    const t = lines[1];

    // diff : str, str -> int
    const diff = (s, t) => {
        let cnt = 0;
        for (let i = 0; i < s.length; i++) {
            if (s[i] !== t[i]) {
                cnt++;
            }
        }
        return cnt;
    }
    console.log(diff(s, t));
});


Measured memory_bytes: 34160
BIG_NUM = 2000000000

table = [[[0]*10 for i in range (0,3)] for k in range (0,4)]

N = int(input())

for loop in range(N):
    house_id,floor,room,add = map(int,input().split())
    table[house_id-1][floor-1][room-1] += add


x = 0

for i in range(4):
    if x != 0:
        print("#"*20)
    x += 1

    for a in range(3):
        for b in range(10):
            print(" %d"%(table[i][a][b]),end = "")
        print()




Measured memory_bytes: 5624
n, d = map(int, input().split())
x = [list(map(int, input().split())) for i in range(n)]
ans = 0

def calc(arr1, arr2):
    tmp = 0
    for i, j in zip(arr1, arr2):
        tmp += abs(i - j) ** 2
    if str(tmp ** 0.5).split('.')[1] == '0':
        return 1
    return 0

for i in range(n):
    for j in range(i+1, n):
        ans += calc(x[i], x[j])

print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

using namespace std;

int main() {
   string s;
   cin >> s; 
   int ans=0;
   rep(i,4){
      if(s[i]=='+')
      ans++;
      else
      ans--;   
   }
   cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

double dist(int x1, int y1, int x2, int y2) {
return sqrt((double)pow(abs(x2-x1), 2)+(double)pow(abs(y2-y1), 2));
}

int main() {
    int n, d;
    cin >> n >> d;
    int ans = 0;
    rep(i, n) {
        int x, y;
        cin >> x >> y;
        if (dist(x, y, 0, 0) <= d) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
import java.util.*;
import java.util.function.Predicate;

public class Main {

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

    void run(){
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int Y = cin.nextInt();

        // 10000円札を0枚からN枚まで全探索する
        for (int A = 0; A <= N; A++){
            // 5000円札を0枚からN枚まで全探索する
            for (int B = 0; A + B <= N; B++){
                // 1000円札の枚数を計算する
                int C = N - A - B;
                int Money = 10000 * A + 5000 * B + 1000 * C;
                // 枚数はN枚なので、金額だけ見れば良い。
                if(Money == Y){
                    System.out.println(A + " " + B + " " + C);
                    return;
                }
            }
        }
        System.out.println("-1 -1 -1");
    }
}


Measured memory_bytes: 21972
#include<cstdio>
long n,k,m,j,p,i,f[333][333][333];main(){scanf("%d%d%d",&n,&k,&m);for(f[i=0][1][0]=1;i<=n;++i)for(j=1;j<=k;++j)for(p=i;~p;--p)(f[i+1][j][p]+=f[i][j][p]*(p+1))%=m,((p?f[i][j][p-1]:f[i][j+1][i])+=f[i][j][p])%=m;printf("%d",f[n][k+1][n]);}


Measured memory_bytes: 262144
inf = float("INF")

class Warshall_Floyd:

    def __init__(self, n, dist):
        self.dist = dist
        self.n = n

    def search(self):
        n = self.n
        dist = self.dist
        for i in range(n):
            dist[i][i] = 0

        for i in range(n):
            di = dist[i]
            for j in range(n):
                dj = dist[j]
                if i == j:
                    continue
                for k in range(n):
                    if dj[k] > dj[i] + di[k]:
                        dj[k] = dj[i] + di[k]

        return dist

import sys


def m():
    def main(n, m):
        dps = [[inf] * n for i in range(n)]
        dpl = [[inf] * n for i in range(n)]

        for _ in range(m):
            x, y, t, sl = sys.stdin.readline().split()
            x, y, t = map(lambda x: int(x) - 1, [x, y, t])
            t += 1
            if sl == "S":
                dps[x][y] = t
                dps[y][x] = t
            if sl == "L":
                dpl[x][y] = t
                dpl[y][x] = t

        l = Warshall_Floyd(n, dpl)
        s = Warshall_Floyd(n, dps)
        dpl = l.search()
        dps = s.search()

        r = int(input())
        v = list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
        dp1 = [inf] * n
        dp1[v[0]] = 0

        for i in range(r-1):
            b = v[i]
            c = v[i + 1]
            dp2 = [0] * n
            dplb = dpl[b]
            dpk = [dp1[k] + dplb[k] for k in range(n)]

            for j in range(n):
                # 陸路のみ
                # 船の位置は変わらず 
                dp2[j] = dp1[j] + dplb[c]

                dpljc = dpl[j][c]
                dpsj = dps[j]
                tmp = dp2[j]

                for k in range(n):
                    # 海路あり
                    # kに船があるとき
                    # v[i-1]→(陸路)→k→(海路)→j→(陸路)→v[i]
                    # この時船はjに保管される
                    tmp1 = dpk[k] + dpsj[k] + dpljc
                    if tmp > tmp1:
                        tmp = tmp1

                dp2[j] = tmp

            dp1 = dp2

        print(min(dp1))

    while 1:
        n, m = map(int, input().split())
        if n == m == 0:
            break
        main(n, m)
if __name__ == "__main__":
    m()


Measured memory_bytes: 7308
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int h[] = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            h[i] = sc.nextInt();
        }
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = Math.abs(h[2] - h[1]);
        for (int i = 3; i < n + 1; i++) {
            dp[i] = Math.min(dp[i - 2] + Math.abs(h[i] - h[i - 2]), dp[i - 1] + Math.abs(h[i] - h[i - 1]));
        }
        System.out.println(dp[n]);
    }
}

Measured memory_bytes: 48960
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  char a, b;
  cin >> a >> b;
  if (a == 'H' && b == 'H')
    cout << 'H' << endl;
  else if (a == 'H' && b == 'D')
    cout << 'D' << endl;
  else if (a == 'D' && b == 'H')
    cout << 'D' << endl;
  else if (a == 'D' && b == 'D')
    cout << 'H' << endl;
}


Measured memory_bytes: 256
import sys
#input = sys.stdin.readline
from collections import deque

H, W = map(int, input().split())

initial = 0
grid = []
for _ in range(H):
    row = input()
    initial += row.count("#")
    grid.append(row)

def bfs():
    dire = [(1,0),(0,1),(-1,0),(0,-1)]
    q = deque()
    q.append((0, 0, 1))
    explored = set()
    explored.add((0, 0))
    while q:
        y, x, count = q.popleft()
        for h, w in dire:
            yh = y + h
            xw = x + w
            if yh < 0 or yh >= H or xw < 0 or xw >= W or grid[yh][xw] == "#" or (yh, xw) in explored:
                continue
            
            if (yh, xw) == (H-1, W-1):
                return count+1

            explored.add((yh, xw))
            q.append((yh, xw, count+1))

    return -1

path_count = bfs()

if path_count == -1:
    print(-1)
else:
    print(H*W - path_count - initial)

            
            

Measured memory_bytes: 3692
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll dp[1005][1005]={0};
int main(){
  string s,t;
  cin>>s>>t;
  for(int i=0;i<s.size();i++){
    for(int j=0;j<t.size();j++){
      int is=i+1,js=j+1;
      dp[is][js]+=dp[i][js];
      if(s[i]==t[j]){
        if(j==0) dp[is][js]++;
        else dp[is][js]+=dp[i][j];
      }
      dp[is][js]%=mod;
    }
  }
  /*for(int i=1;i<=s.length();i++){
    for(int j=1;j<=t.length();j++) cout<<dp[i][j]<<" ";
    cout<<endl;
  }*/
  cout<<dp[s.length()][t.length()]<<endl;
}



Measured memory_bytes: 11084
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int bingo[3][3];
bool bingo2[3][3];

int main() {
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> bingo[i][j];
            bingo2[i][j] == false;
        }
    }

    int N;
    cin >> N;
    vector<int> b(N);
    for (auto &&v : b) {
        cin >> v;
    }
    for (auto v : b) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (bingo[i][j] == v) {
                    bingo2[i][j] = true;
                }
            }
        }
    }

    for (int i = 0; i < 3; ++i) {
        if (bingo2[i][0] && bingo2[i][1] && bingo2[i][2]) {
            goto yes;
        }
    }
    for (int i = 0; i < 3; ++i) {
        if (bingo2[0][i] && bingo2[1][i] && bingo2[2][i]) {
            goto yes;
        }
    }

    if (bingo2[0][0] && bingo2[1][1] && bingo2[2][2]) {
        goto yes;
    }

    if (bingo2[0][2] && bingo2[1][1] && bingo2[2][0]) {
        goto yes;
    }

    cout << "No" << endl;
    return 0;
yes:
    cout << "Yes" << endl;
    return 0;
}

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

typedef pair<int,int> pi;
typedef vector<int> vi;
 
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
 
template<typename T> void max_self(T &a, T b) { a = max(a,b); return;}
template<typename T> void min_self(T &a, T b) { a = min(a,b); return;}
 
const int nax = 1e5 + 5;
const int mod = 1e9 + 7;

int solve(int a,int b,int c){
	
	a = a % c;	
	if(b == 0) return 1;
	else if((b % 2) == 0) return solve((a * a) % c,b / 2,c) % c;
	else return (a * solve((a * a) % c,b / 2,c) % c) % c;
}

int n;

signed main(){
	
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int k;
	cin >> n >> k;
		
	int arr[n];
	for(int i = 0; i < n; ++i) cin >> arr[i];
	
	bool dp[k + 1];
	memset(dp,false,sizeof(dp));
		
	for(int i = 1; i <= k; ++i){
		for(int j = 0; j < n; ++j){
			if(i >= arr[j] && dp[i - arr[j]] == false) dp[i] = true;
		}
	}
	
	if(dp[k]) cout << "First";
	else cout << "Second";
	
	return 0;
}


Measured memory_bytes: 3704
#include "bits/stdc++.h"
using namespace std;

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

#define FOR(i, s, e) for (ll(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (ll(i) = (s); (i) > (e); (i)--)
#define debug(x) cout << #x << ": " << x << endl
#define mp make_pair
#define pb push_back
const ll MOD = 1000000007;
const int INF = 1e9;
const ll LINF = 1e16;
const double PI = acos(-1.0);
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

/* -----  2017/04/29  Problem: ARC 073 B / Link: http://arc073.contest.atcoder.jp/tasks/arc073_b  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

ll N;

ll ans = 0LL;
ll dp[200][600][200];
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  ll W;
  ll w[105];
  ll v[105];
  cin >> N>>W;
  FOR(i, 0, N) {
	  cin >> w[i] >> v[i];
  }
  ll ww = w[0];
  FORR(i, N-1, -1) {
	  w[i] -= (ww);
	 // cout << w[i] << endl;
  }
  //w
  
  FOR(i, 0, N) {//new
	  FOR(j, 0, 350) {
		  FOR(k, 0, N+1) {
			  if (j - w[i] < 0 || k - 1 < 0) {
				  dp[i + 1][j][k] = dp[i][j][k];
			  }
			  else {
				  dp[i + 1][j][k] = max(dp[i][j][k], dp[i][j - w[i]][k - 1] + v[i]);
			  }
		  }
	  }
  }

  //FOR(i, 0, N) {
	 // FOR(j, 0, 405) {
		//  if (j - w[i] >= 0) {
		//	  dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
		//  }
		//  else {
		//	  dp[i + 1][j] = dp[i][j];
		//  }
	 // }
  //}
  ans = -1;

  FOR(i, 1, N + 1) {
	  FOR(j, 0, i * 3 + 1) {
		  ll k = (ww )*i + j;
		  if (W - k >= 0)
			  ans = max(ans, dp[N][j][i]);
	  }
  }
  if (ans == -1)ans = 0;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 95232
#include <iostream>

using namespace std;

int main()
{
  int w, h, x, y;
  cin >> w >> h >> x >> y;
  cout << (double)w * h / 2 << " ";
  if(w == 2*x && h == 2*y) cout << 1 << endl;
  else cout << 0 << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int n;
    string s;
    cin >> n;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        s.at(i) += n;
        if (s.at(i) > 'Z') {
            s.at(i) -= 26;
        }
    }
    cout << s << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;
typedef vector<char> vech;

int main() {
    ll N,p=1,num=0,num2=0;
    cin>>N;
    vel a(N);
    rep0(i,N){cin>>a[i];}
    rep0(i,N){p*=a[i];}
    if(p%(ll)pow(2,N-1)!=0){cout<<"No"<<endl; return 0;}
    rep0(i,N){if(a[i]%4==0){num++;} if(a[i]%2==0){num2++;}}
    if(num>=N/2){cout<<"Yes"<<endl;}
    else if(num*2+(num2-num)>=N){cout<<"Yes"<<endl;}
    else {cout<<"No"<<endl;}
}


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

#define mp make_pair

using namespace std;

typedef int32_t i32;
typedef uint32_t u32;
typedef int64_t i64;
typedef uint64_t u64;
typedef pair<int,int> pii;
typedef pair<i64,int> pli;
typedef pair<int,i64> pil;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;

const int MAX_N = 8000;
string s;
int x,y;
bool dp[MAX_N][2*MAX_N+5] = {};
vi vd, hd;

int main()
{
  cin >> s >> x >> y;
  s.push_back('T');
  int r = 0;
  int i = 0;
  while (s[i++] == 'F') r++;
  bool v = true;
  int c = 0;
  for (; i < (int)s.length(); i++) {
    if (s[i] == 'T') {
      if (v) vd.push_back(c);
      else hd.push_back(c);
      c = 0;
      v = !v;
    } else {
      c++;
    }
  }

  /*
  cout << "[hd]" << hd.size() << endl;
  for (int i : hd) cout << i << endl;
  cout << "[vd]" << vd.size() << endl;
  for (int i : vd) cout << i << endl;
  */

  dp[0&1][MAX_N+r] = true;
  for (int i = 0; i < (int)hd.size(); i++) {
    fill_n(dp[1-(i&1)], 2*MAX_N+5, false);
    for (int j = 0; j <= 2*MAX_N; j++) {
      if (dp[i&1][j]) {
        if (j-hd[i] >= 0) dp[1-(i&1)][j-hd[i]] = true;
        if (j+hd[i] <= 2*MAX_N) dp[1-(i&1)][j+hd[i]] = true;
      }
    }
  }

  if (!dp[hd.size()&1][MAX_N+x]) {
    cout << "No" << endl;
    return 0;
  }

  fill_n(dp[0], 2*MAX_N+5, false);
  dp[0][MAX_N] = true;
  for (int i = 0; i < (int)vd.size(); i++) {
    fill_n(dp[1-(i&1)], 2*MAX_N+5, false);
    for (int j = 0; j <= 2*MAX_N; j++) {
      if (dp[i&1][j]) {
        if (j-vd[i] >= 0) dp[1-(i&1)][j-vd[i]] = true;
        if (j+vd[i] <= 2*MAX_N) dp[1-(i&1)][j+vd[i]] = true;
      }
    }
  }

  if (!dp[vd.size()&1][MAX_N+y]) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i=0, ai; i<n; i++) {
        cin >> ai;
        if (i % 2 == 0 && ai % 2 == 1) ans++;
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3628
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var K int
var count int = 0
var list = make([]int, 0)

func dp(c, d int) {
	if c > 10000000000 {
		return
	}

	// fmt.Println(c)
	count++
	list = append(list, c)

	min := d - 1
	max := d + 1
	if d == 0 {
		min = 0
	}
	if d == 9 {
		max = 9
	}

	for i := min; i <= max; i++ {
		dp(c*10+i, i)
	}

}

func main() {

	nextReader = newScanner()
	K = nextInt()

	for i := 1; i < 10; i++ {
		dp(i, i)
	}

	sort.Ints(list)

	fmt.Println(list[K-1])

}

/* --------------------------------------------------------------------------
 *  std.io
 * ------------------------------------------------------------------------- */
var nextReader func() string

func newScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}
func nextString() string {
	return nextReader()
}
func nextInt64() int64 {
	v, _ := strconv.ParseInt(nextReader(), 10, 64)
	return v
}
func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}
func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}
func nextInt64s(n int) []int64 {
	r := make([]int64, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt64()
	}
	return r
}
func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(nextReader(), 64)
	return f
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func mins(t ...int) int {
	if len(t) == 0 {
		return 0
	}

	min := t[0]
	for i := 1; i < len(t); i++ {
		if min > t[i] {
			min = t[i]
		}
	}
	return min
}

func abs(a int) int {
	if a >= 0 {
		return a
	} else {
		return 0 - a
	}
}


Measured memory_bytes: 5504
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <bitset>
#include <functional>

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

using namespace std;

int main(void)
{
	long long X, Y, Z, K;
	long long A[1009], B[1009], C[1009];
	vector<long long> vec;

	cin >> X >> Y >> Z >> K;
	for (int i = 0; i < X; i++) {
		cin >> A[i];
	}
	sort(A, A + X, greater<long long>());
	for (int i = 0; i < Y; i++) {
		cin >> B[i];
	}
	sort(B, B + Y, greater<long long>());
	for (int i = 0; i < Z; i++) {
		cin >> C[i];
	}
	sort(C, C + Z, greater<long long>());

	FOR(i, 0, X) {
		FOR(j, 0, Y) {
			FOR(k, 0, Z) {
				if ((i + 1) * (j + 1) * (k + 1) > K) continue;
				vec.push_back(A[i] + B[j] + C[k]);
			}
		}
	}

	std::sort(vec.begin(), vec.end(), std::greater<long long>());

	FOR(i, 0, K) {
		cout << vec[i] << endl;
 	}

	return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define all(v) (v).begin(), (v).end()

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

  vi dp; //i番目の色で塗っている数字の最大値

  int x;
  for(int i=0; i<N; i++){
    cin>>x;
    auto itr = upper_bound(all(dp), x, [](int a, int b){
      return a > b;
    });
    if(itr!=dp.end()){
      *itr = x;
    }else{
      dp.pb(x);
    }
  }

  cout<<dp.size()<<endl;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;

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

    ll a = 0;
    int x = pow(10, 9) + 7;
    for (ll i = k; i <= n + 1; ++i){
        a += n*i - i*(i - 1) + 1;
        a %= x;
    }

    cout << a << endl;
    return 0;
}


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

// #define TEST_CASES
using ll = long long;
#define ff first
#define ss second
const int N = 1e5 + 10;

int n;
int a[21];

void solve()
{
	cin>>n;
	for (int i = 0; i < n; i++)
		cin>>a[i];
	int ans = 0;
	for (int i = 1; i < n - 1; i++)
	{
		int v[3] = {a[i - 1], a[i], a[i + 1]};
		sort(v, v + 3);
		if (a[i] == v[1]) ans++;
	}
	cout<<ans<<endl;
}

int main()
{
	int t = 1;
#ifdef TEST_CASES
	cin>>t;
#endif
	while(t--)
	{
		solve();
	}
}



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

const int MOD = 1000000007;

int rev[13][10];

ll dp[100002][13];

int main()
{
    for(int i = 0; i < 13; i++){
        int c = i;
        for(int j = 0; j < 10; j++){
            rev[i][c % 10] = c / 10;
            c += 13;
        }
    }
//    for(int i = 0; i < 10; i++) cout << rev[0][i] << endl;
    string s;
    cin >> s;
    int n = s.size();
    if(s[0] == '?'){
        for(int j = 0; j < 10; j++) dp[0][j] = 1;
    }
    else{
        dp[0][s[0] - '0'] = 1;
    }
    for(int i = 1; i < n; i++){
        if(s[i] == '?'){
            for(int j = 0; j < 13; j++){
                for(int k = 0; k < 10; k++){
                    dp[i][j] = (dp[i][j] + dp[i - 1][rev[j][k]]) % MOD;
                }
            }
        }
        else{
            for(int j = 0; j < 13; j++) dp[i][j] = dp[i - 1][rev[j][s[i] - '0']];
        }
    }
    cout << dp[n - 1][5] << endl;
}

Measured memory_bytes: 10624
import Control.Monad (replicateM, forM_)

main :: IO ()
main = do
  lines <- getNLine

  forM_ lines $ \line ->
    putStrLn . (\(a:b:c:d:_) -> yesNo $ f a b c d) . map read . words $ line

getNLine :: IO [String]
getNLine = do
  n <- readLn
  replicateM n getLine

yesNo :: Bool -> String
yesNo b = if b then "Yes" else "No"

f :: Int -> Int -> Int -> Int -> Bool
f initial buy level restock
  | buy > initial = False -- 即死
  | buy > restock = False -- ジリ貧
  | buy <= level = True -- 絶対死なない
  | otherwise =
    let
      step = gcd buy restock -- mod buy で見ると、購入・補充はこのステップで動く
    in
      buy - step + initial `mod` step <= level


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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;

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

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

	while(true) {
		int n,m,a;cin>>n>>m>>a;
		a--;
		if(n==0) break;
		vector<PP> vec;
		REP(i,m) {
			int h,p,q;cin>>h>>p>>q;
			p--,q--;
			vec.pb(PP(h,P(p,q)));
		}
		sort(ALL(vec));
		int goal[n];
		REP(i,n) goal[i]=i;
		for(auto x:vec) {
			swap(goal[x.se.fi],goal[x.se.se]);
		}
		cout<<goal[a]+1<<endl;
	}

	return 0;
}



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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    if(abs(a - c) <= d || abs(a - b) <= d && abs(b - c) <= d) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}


Measured memory_bytes: 3500
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n,k; cin>>n>>k;
    int ans=1;
    for(int i=0; i<n; i++){
        if(ans<k) ans*=2;
        else ans+=k;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  A=list(map(int, input().strip("\n").split()))

  def swap(a, b):
    tmp=A[a]
    A[a]=A[b]
    A[b]=tmp

  def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
      if A[j] <= x:
        i += 1
        swap(i, j)
    swap(i+1, r)
    return i + 1

  p=partition(A, 0, n - 1)
  for i in range(len(A)):
    if i==p:
      print('['+str(A[i])+']', end=' ')
    elif i==len(A)-1:
      print(A[i])
    else:
      print(A[i], end=' ')



Measured memory_bytes: 16396
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
	int n;
	char c;
	string bl;
	int a=0,b=0,ab=0,o=0;
	while(cin>>n>>c>>bl)
	{
		if(bl=="A") a++;
		else if(bl=="B") b++;
		else if(bl=="O") o++;
		else ab++;
	}
	cout<<a<<endl;
	cout<<b<<endl;
	cout<<ab<<endl;
	cout<<o<<endl;
  return 0;
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define all(a)                      a.begin(), a.end()
#define pb                          push_back
#define ll							long long
#define index(a)            		order_of_key(a)
#define value(a)					find_by_order(a)
#define count_1 					__builtin_popcount
#define mod(x, m)					((((x) % (m)) + (m)) % (m))
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
int in_degree[100005],dist[100005];
vector<int> v[100005];
bool visited[100005];
void dfs(int u){
	visited[u]=true;
	
	for(auto x:v[u]){
		dist[x]=max(dist[x],1+dist[u]);
		in_degree[x]--;
		if(in_degree[x]==0){
			dfs(x);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout<<setprecision(12);
	int n,m,x,y;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		v[x].pb(y);
		in_degree[y]++;
	}
	
	for(int i=1;i<=n;i++){
		if(!visited[i]  && in_degree[i]==0){
			dfs(i);
		}
	}
	int ans=-1;
	for(int i=1;i<=n;i++)ans=max(ans,dist[i]);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 9728
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

inline int nextInt() { int d; cin >> d; return d; }

bool isPrime(int n) {
  if (n == 2) return true;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

int main() {
  while (true) {
    int p = nextInt();
    if (p == 0) {
      break;
    }
    int u, d;
    for (u = p; ; u++) {
      if (isPrime(u)) {
        break;
      }
    }
    for (d = p; ; d--) {
      if (isPrime(d)) {
        break;
      }
    }
    cout << u - d << endl;
  }

  return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long ll;
typedef vector<int >    vecint;
typedef vector<string > vecstr;
int main()
{
  int n, r;
  cin >> n >> r;
  int ans = 0;
  if(n >= 10){
    ans = r;
  }else{
    ans = r + 100*(10 - n);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>    
long long doLCM(long long* array,int size);
long long ggcd(long long a,long long b);
    
//获得最小公倍数    
long long doLCM(long long* array,int size)
{    
    long long x,y,gcd;
	long long num=array[0];
	int i;  
    //去数组的第一和第二个数，计算它们的公倍数，然后再取第三个数，  
    //和之前的公倍数计算它们的公倍数，直到只有一个数。  
    for(i=0;(i+1)<size;i++){  
        x=num;    
        y=array[i+1];  
        gcd = ggcd(x,y);    
        //LCM
    	num = x/gcd * y/gcd * gcd;  
    }  
    return num;    
}  
    
//获取最大公约数    
long long ggcd(long long a,long long b)
{  
	return b?ggcd(b,a%b):a;
}    
    
int main()
{    
	int n;
	scanf("%d",&n);
	long long array[n];
    for(int i=0;i<n;i++)
	{
		scanf("%lld",&array[i]);
	}   
    long long result = doLCM(array,n);    
    printf("%lld\n",result);    
    return 0;    
}  

Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_H=100,MAX_W=100;
int H,W,N;
int ans[MAX_H][MAX_W];
int main(){
	cin>>H>>W>>N;
	int x,y;
	x=y=0;
	bool flg=true;
	REP(i,N){
		int a;
		cin>>a;
		REP(j,a){
			ans[y][x]=i+1;
			if (flg){
				y++;
				if (y==H){
					x++;
					y=H-1;
					flg=false;
				}
			}else{
				y--;
				if (y<0){
					x++;
					y=0;
					flg=true;
				}
			}
		}
	}
	REP(h,H){
		REP(w,W){
			if (w){
				cout<<" ";
			}
			cout<<ans[h][w];
		}
		cout<<endl;
	}
	return 0;
}

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

int main() {
  string str;
  cin >> str;

  bool n = false, w = false, s = false, e = false;
  for (auto c : str) {
    if (c == 'N')
      n = true;
    if (c == 'W')
      w = true;
    if (c == 'S')
      s = true;
    if (c == 'E')
      e = true;
  }

  if (n == s && e == w)
    puts("Yes");
  else
    puts("No");
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

#define rep(i, n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int main() {
    int a,b;
    cin>>a>>b;
    int a1=a-1;
    int ans=0;
    int kuti=1;
    while(true){
        if(kuti<b){
            ans++;
            kuti+=a;
            kuti--;
        }else{
            break;
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
  
struct Point {
    double x,y;
};
  
void makeKochCurve (Point * p1, Point * p2, int n, int maxDepth) {
    if (n > maxDepth) return;
    Point s = { p1->x + (p2->x - p1->x) / 3, p1->y + (p2->y - p1->y) / 3};
    Point t = { p1->x + (p2->x - p1->x) * 2 / 3, p1->y + (p2->y - p1->y) * 2 / 3};
  
    double th = M_PI * 60 / 180;
    Point u = { (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x , (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) +s.y};
  
    makeKochCurve(p1, &s, n + 1, maxDepth);
    printf("%.8f %.8f\n", s.x, s.y);
    makeKochCurve(&s, &u, n + 1, maxDepth);
    printf("%.8f %.8f\n", u.x, u.y);
    makeKochCurve(&u, &t, n + 1, maxDepth);
    printf("%.8f %.8f\n", t.x, t.y);
    makeKochCurve(&t, p2, n + 1, maxDepth);
  
}
  
int main() {
    Point s = {0,0};
    Point e = {100,0};
  
    int n;
    scanf("%d", &n);
  
    printf("%.8f %.8f\n", s.x, s.y);
    makeKochCurve(&s, &e, 1, n);
    printf("%.8f %.8f\n", e.x, e.y);
    return 0;
}


Measured memory_bytes: 2728
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
 
void addWordCount(const vector<string>& cards, unordered_map<string, int>& wordCount);
void subWordCount(const vector<string>& cards, unordered_map<string, int>& wordCount);
  
int main() {
    int numOfBlueCard = 0;
    cin >> numOfBlueCard;
    vector<string> blueCards;
    for (int i = 0; i < numOfBlueCard; ++i) {
        string blueCard;
        cin >> blueCard;
        blueCards.push_back(blueCard);
    }
 
    int numOfRedCard = 0;
    cin >> numOfRedCard;
    vector<string> redCards;
    for (int i = 0; i < numOfRedCard; ++i) {
        string redCard;
        cin >> redCard;
        redCards.push_back(redCard);
    }
    
    unordered_map<string, int> wordCount;
    addWordCount(blueCards, wordCount);
    subWordCount(redCards, wordCount);
    
    unordered_map<string, int>::iterator maxValueWord = std::max_element(wordCount.begin(), wordCount.end(),
    [](const pair<string, int>& p1, const pair<string, int>& p2) {
        return p1.second < p2.second; });
    
    int maxValue = maxValueWord->second;
    if (maxValueWord->second < 0) {
        maxValue = 0;
    }
    cout << maxValue << endl;
}
 
void addWordCount(const vector<string>& cards, unordered_map<string, int>& wordCount) {
    for (string card : cards) {
        ++wordCount[card];
    }
}
 
void subWordCount(const vector<string>& cards, unordered_map<string, int>& wordCount) {
    for (string card : cards) {
        --wordCount[card];
    }
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
inline ll read()
{
	ll x=0,w=0;char ch=getchar();
	while(!isdigit(ch))w|=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return w?-x:x;
}
int n,a[10000],ans;
int main()
{
    n=read();reg int i,j;
    for(i=1;i<=n;++i)a[i]=read();
    for(i=1;i<=n;++i)
        for(j=i+1;j<=n;++j)
            ans+=a[i]*a[j];
    cout<<ans<<"\n";
	return 0;
}


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

int main(){
	int i, n, run, out, score;
	string str;
	cin>>n;
	for(i=0;i<n;i++){
		score=run=out=0;
		while(true){
			cin>>str;
			if(str == "HIT"){
				if(run<3) run++;
				else score++;
			}
			if(str == "OUT"){
				out++;
				if(out>=3){
					cout<<score<<endl;
					break;
				}
			}
			if(str == "HOMERUN"){
				score+=run+1;
				run=0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

ll h,w,ans=INF;

void cut1(ll now,ll W,ll end){
	for(ll i=now+1;i<end;i++){
		ll a,b,c,MAX,MIN;
		a=now*W;b=abs(now-i)*W;c=abs(end-i)*W;
		MAX=max({a,b,c});MIN=min({a,b,c});
		ans=min(ans,abs(MAX-MIN));
	}
}

void cut2(ll now,ll W,ll end){
	for(int i=1;i<W;i++){
		ll a,b,c,MAX,MIN;
		a=now*W;b=(end-now)*i;c=(end-now)*(W-i);
		MAX=max({a,b,c});MIN=min({a,b,c});
		ans=min(ans,abs(MAX-MIN));
	}
}
int main() {
	cin>>h>>w;
	for(int i=-1;i<2;i++){
		cut1(h/3+i,w,h);
		cut1(w/3+i,h,w);
	}
	for(int i=-1;i<2;i++){
		cut2(h/3+i,w,h);
		cut2(w/3+i,h,w);
	}
	cout <<ans;
}

Measured memory_bytes: 256
n = int(input())
A = [0] * n

for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            if x**2 + y**2 + z**2 + x*y + y*z + z*x <= n:
                A[x**2 + y**2 + z**2 + x*y + y*z + z*x - 1] += 1
            else:
                break

for ans in A:
    print(ans)

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

const ll N = 3e3 + 10;
ll n, ans = 1, out, ar[N];

ll gcd(ll a, ll b) {
	return (!b) ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return (a * b) / gcd(a, b);
}

int main() {
	cin >> n;
	for (ll i = 0; i < n; i++) {
		cin >> ar[i];
//		ans = lcm(ans, ar[i]);
	}
//	ans--;
	for (ll i = 0; i < n; i++)
		out += ar[i] - 1;
	cout << out;
}

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

const int maxn = 200010;
int n, a[maxn];

int main() {
    cin >> n; a[0] = -1;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] - a[i - 1] > 1) { cout << -1 << endl; exit(0); }
        if (i == 1) continue;
        if (a[i] == a[i - 1] + 1) ans++;
        else ans += a[i];
    }
    cout << ans << endl;
    return 0;
}

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

// for loop
#define rep(i,a,n) for(int i=(a);i<(n);++i)
#define repe(i,a,n) for(int i=(a);i<=(n);++i)
#define rrep(i,n,a) for(int i=(n);n>(a);--i)
#define rrepe(i,n,a) for(int i=(n);n>=(a);--i)

// abbreviati
#define PB(v) push_back(v)
#define MP make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ENDL << "\n"

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

// constant
const int INF = 1<<30;
const ll INFLL = 1LL << 60;
const ll MOD = 1000000007;
const long double PI =(acos(-1));

/***Snippet***************************************************
ifelse, isprime, torad, todeg, lcm, bfs,chmin,chmax
**************************************************************/

// adjacency list
vector<int> to[100005];

// Graph
using Graph = vector<vector<int>>;

// Grid
int H,W;
vector<vector<int>> field;

// 4方向への移動ベクトル
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,p; cin >> a >> p;
    cout << (3*a+p)/2 ENDL;
    
    return 0;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x,ll y,ll z){if(x)cout<<y<<endl;else cout<<z<<endl;}
void anss(bool x,string y,string z){if(x)cout<<y<<endl;else cout<<z<<endl;}   
ll gcd(ll x,ll y){ll r;while((r=x%y)!=0){x=y;y=r;}return y;}

vector<vector<ll>> a(100001);//辺(添え字は始点、値は終点)
vector<ll>t(100001);//訪問したかどうか
ll tbuf=0;
ll pbuf=0,qbuf=0;
ll n;
void dfs(ll k,ll d){
  t[k]=1;
  for(ll i=0;i<a[k].size();i++){
    if(t[a[k][i]]==0){
      dfs(a[k][i],d+1); 
    }
  }
  if(k==n)tbuf=d;
  if(tbuf!=0&&qbuf==0&&d==tbuf/2+1)qbuf=k;
  if(tbuf!=0&&pbuf==0&&d==tbuf/2)pbuf=k;
}

ll num=0;
void dfs2(ll k){
  t[k]=1;
  num++;
  for(ll i=0;i<a[k].size();i++){
    if(t[a[k][i]]==0){
      dfs2(a[k][i]); 
    }
  }
}

int main(){
  ll i,j,o;
  ll res=0,res1=0,res2=INF,buf=0,buf1=0,buf2=0,buf3=0,buf4=0;
  bool judge = true;
  cin>>n;
  ll p,q;
  for(i=0;i<n-1;i++){
    cin>>p>>q;
    a[p].push_back(q);
    a[q].push_back(p);
  }
  dfs(1,0);
  fill(ALL(t),0);
  t[qbuf]=1;
  dfs2(pbuf);
  // cout<<num<<endl;
  // cout<<pbuf spa qbuf spa tbuf<<endl;
  anss(num>n/2,"Fennec","Snuke");
  return 0;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int k;
 cin>>k;
 vector<string> a;
    a.push_back("1");
    a.push_back("2");
    a.push_back("3");
    a.push_back("4");
    a.push_back("5");     
	a.push_back("6");
    a.push_back("7");
    a.push_back("8");
    a.push_back("9");
    int i=0;
    while(a.size()<k)
    {
    	string x=a[i];
    	char c=x[x.length()-1];
    	string y=x;
    	string t=x;
    	if(c=='0')
    	{
    		x=x+'1';
    		t=t+'0';
    		a.push_back(t);
    		a.push_back(x);
		}
		else if(c=='9')
		{
		    t=t+'9';
			y=y+'8';
			a.push_back(y);
			a.push_back(t);
		}
		else
		{
			t=t+c;
			char p=c+1;
			char q=c-1;
			x=x+q;
			y=y+p;
			a.push_back(x);
			a.push_back(t);
			a.push_back(y);
		}
		i++;
	}
//	for(i=0;i<k;i++)
	//cout<<i<<" "<<a[i]<<endl;
	cout<<a[k-1]<<endl;
 return 0;
}


Measured memory_bytes: 6900
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int n,k;cin>>n>>k;
    vector<int> arr(n);
   for(int i = 0; i < n; i++) cin>>arr[i];
   for(int i = 0; i < n; i++) arr[i]--;
   vector<ll> s(n+1);
   for(int i = 0; i < n;  i++) s[i+1] = (s[i]+arr[i])%k;
   map<ll,ll> mp;
   ll ans = 0;
   queue<ll> q;
   for(int i = 0; i <= n; i++){
       ans+=mp[s[i]];
       mp[s[i]]++;
       q.push(s[i]);
       if(q.size() == k){
           mp[q.front()]--;
           q.pop();
       }
   }
  cout<<ans;
}


Measured memory_bytes: 16768
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0

for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            total = 500*i + 100*j + 50*k
            if total == x:
                count += 1
print(count)




Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <algorithm>
#include <iomanip>
#include <cstring>

using namespace std;
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < n; i++)
int v[26];
int main()
{
    int n, x;
    vector<int> v;
    cin >> n;
    rep(i, n)
    {
        cin >> x;
        v.pb(x);
    }
    int counter = 0;
    rep(i, n)
    {
        if (i > 0&& i < n - 1)
        {
            if ((v[i] > v[i+1] && v[i] < v[i-1]) || (v[i] < v[i+1] && v[i] > v[i-1]))
            {
                counter++;
            }
        }
    }
    cout << counter << " ";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  int r,g;
  cin >> r >> g;
  cout << 2*g-r << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

int main(){
  int n,m; cin >> n >> m;
  vvi G(n);
  vi deg(n);
  rep(i, m){
    int a,b; cin >> a >> b;
    a--; b--;
    G[a].pb(b); G[b].pb(a);
    deg[a]++; deg[b]++;
  }

  queue<int> q;
  rep(v, n) if(deg[v] == 1) q.push(v);
  vector<bool> pushed(n,false);

  while (!q.empty()) {
    int v = q.front(); q.pop();
    pushed[v] = true;
    for(auto nv : G[v]){
      deg[nv]--;
      if(deg[nv] == 1) q.push(nv);
    }
  }

  int cnt = 0;
  rep(v, n) if(pushed[v]) cnt++;
  if(cnt==n) cnt--;
  std::cout << cnt << '\n';
}


Measured memory_bytes: 256