akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=10;
typedef pair<int,int> pii;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
char gc() {
    char ch=getchar();
    while(ch!='.'&&ch!='#') ch=getchar();
    return ch;
}
int n,m,f[N*N],dx[5]={0,1,0,0,-1},dy[5]={0,0,1,-1,0};
char a[N][N];
int getf(int x) { return x==f[x]?x:f[x]=getf(f[x]); }
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) a[i][j]=gc();
    if(a[1][1]!='#'||a[n][m]!='#') return puts("Impossible"),0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) f[(i-1)*m+j]=(i-1)*m+j;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=4;k++) {
                int x=i+dx[k],y=j+dy[k];
                if(a[x][y]=='#'&&a[i][j]=='#') f[getf((x-1)*m+y)]=getf((i-1)*m+j);
            }
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cnt+=a[i][j]=='#';
    puts(cnt==n+m-1&&getf(1)==getf(n*m)?"Possible":"Impossible");
    return 0;
}
//orzgzy
//鸡贼明年进队超稳


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)
n = int(input())
G = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
c = list(map(int,input().split()))
c.sort()
node = [0]*n
used = [False]*n

def dfs(cur,point):
    used[cur] = True
    for nx in G[cur]:
        if used[nx]: continue
        t = c.pop()
        node[nx] = t
        point += min(node[cur],node[nx])
        point = dfs(nx,point)
    return point
node[0] = c.pop()
# print(dfs(0,-1,0))
print(dfs(0,0))
print(*node)

Measured memory_bytes: 80068
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    s = S()

    if s == 'AAA' or s == 'BBB':
        print('No')
    else:
        print("Yes")


if __name__ == '__main__':
    main()


Measured memory_bytes: 38640
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define REV(s) (s).rbegin(), (s).rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define X first
#define Y second

using namespace std;

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

const int N = 110;
ll dp[N][N];
int top[N], bot[N];

ll dfs(int l, int r){ // [l, r]
	if(l == r) return 0;
	ll &res = dp[l][r];
	if(res >= 0) return res;

	res = 1ll<<32;
	for(int i = l; i <= r; ++i){
		ll tmp = dfs(l, i)+dfs(i+1, r);
		tmp += top[l]*bot[i]*top[i+1]*bot[r];
		res = min(res, tmp);
	}

	return res;
}

int main(){
	int n;
	cin >> n;
	rep(i, n) cin >> top[i] >> bot[i];

	MEMSET(dp, -1);
	cout << dfs(0, n-1) << endl;

	return 0;
}

Measured memory_bytes: 1264
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <complex>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	string s;
	ll n;
	cin >> s >> n;
	for (int i = 0; i < s.size(); i++) {
		if (i%n == 0)cout << s[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
li = []
for index in range(N-1):
	c, s, f = map(int, input().split())
	li.append((c, s, f))

for i in range(N):
	t = 0
	station = i
	while station < N-1:
		c, s, f = li[station]
		if t < s:
			t = s
			t += c
		else:
			t += (f-(t-s))%f + c
		station += 1
	print(t)

Measured memory_bytes: 3188
//↓template↓

#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

long long mod_pow(long long a, long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) { res = res * a%MOD; }
		a = a * a%MOD;
		b >>= 1;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

//↑template↑

void dijkstra(int n) {
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>que;
	fill(dij.begin(), dij.end(), INF);
	dij[n] = 0;
	que.push(pair<long long, long long>(0, n));

	while (!que.empty()) {
		pair<long long, long long>p = que.top();
		que.pop();
		long long mon = p.second;
		if (dij[mon] < p.first) continue;
		for (int i = 0; i < G[mon].size(); ++i) {
			edge e = G[mon][i];
			if (dij[e.to] > dij[mon] + e.cost) {
				dij[e.to] = dij[mon] + e.cost;
				que.push(pair<long long, long long>(dij[e.to], e.to));
			}
		}
	}
}

int main() {
	int n;
	cin >> n;
	G.resize(n + 1);
	dij.resize(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		long long a, b, c;
		cin >> a >> b >> c;
		addedge(a, b, c);
	}
	int a, b;
	cin >> a >> b;
	dijkstra(b);
	for (int i = 0; i < a; ++i) {
		int k, l;
		cin >> k >> l;
		cout << dij[k] + dij[l] << endl;
	}
}

Measured memory_bytes: 11120
import java.util.Scanner;

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

		if (N % 2 == 0) {
			System.out.println(N / 2);
		} else {
			System.out.println(N / 2 + 1);
		}

	}
}


Measured memory_bytes: 22484
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    long N, M;
    scan(N, M);
    auto A = new long[](N);
    auto B = new long[](N);
    auto C = new long[](M);
    auto D = new long[](M);
    foreach (i; 0 .. N)
    {
        scan(A[i], B[i]);
    }
    foreach (i; 0 .. M)
    {
        scan(C[i], D[i]);
    }
    alias T = Tuple!(long, long);
    foreach (i; 0 .. N)
    {
        auto m = T(long.max, 0);
        foreach (j; 0 .. M)
        {
            m = m.min(T(abs(A[i] - C[j]) + abs(B[i] - D[j]), j + 1));
        }
        writeln(m[1]);
    }
}


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

int main(){
    ll N;
    cin >> N;
    vector<int> A;
    int sum = 0;
    int i = 1;
    while (sum < N)
    {

        sum += i;
        A.push_back(i);
        i++;
    }
    if(sum > N){
        A.erase(remove(A.begin(),A.end(),sum - N),A.end());
        sum = N;
    }
    for (int i = 0; i < A.size();i++)
    {
        cout << A[i] << endl;
    }
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int x[320000];
int com(int a,int b)
{
	return a>b;
}
int main()
{	
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>x[i];
	sort(x,x+n,com);
	int ans=0;
	for(int i=0;i<m;i++)
	{
		ans+=x[i];
	}		
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int MAX = 100001;
        
        final int n = sc.nextInt();
        
        final int[] evenCount = new int[MAX];
        final int[] oddCount = new int[MAX];
        
        for (int i = 0; i < n / 2; i++) {
            evenCount[sc.nextInt()]++;
            oddCount[sc.nextInt()]++;
        }
        
        int even1st = evenCount[0] < evenCount[1] ? 1 : 0;
        int even2nd = evenCount[0] < evenCount[1] ? 0 : 1;
        int odd1st = oddCount[0] < oddCount[1] ? 1 : 0;
        int odd2nd = oddCount[0] < oddCount[1] ? 0 : 1;
        
        for (int i = 2; i < MAX; i++) {
            if (evenCount[even1st] < evenCount[i]) {
                even2nd = even1st;
                even1st = i;
            } else if (evenCount[even2nd] < evenCount[i]) {
                even2nd = i;
            }
            if (oddCount[odd1st] < oddCount[i]) {
                odd2nd = odd1st;
                odd1st = i;
            } else if (oddCount[odd2nd] < oddCount[i]) {
                odd2nd = i;
            }
        }
        
        int evenAdopt;
        int oddAdopt;
        
        if (even1st != odd1st) {
            evenAdopt = even1st;
            oddAdopt = odd1st;
            
        } else if (evenCount[even1st] + oddCount[odd2nd] < evenCount[even2nd] + oddCount[odd1st]) {
            evenAdopt = even2nd;
            oddAdopt = odd1st;
            
        } else {
            evenAdopt = even1st;
            oddAdopt = odd2nd;
        }
        
        System.out.println(n - evenCount[evenAdopt] - oddCount[oddAdopt]);
    }
}


Measured memory_bytes: 60568
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>


/* 
*    coder :: ATUL_PANDEY_2608
*        >>> INDIA <<<
*/
using namespace std;
using namespace __gnu_pbds;

// #define  part ..
#define pb(a) push_back(a)
#define all(a) a.begin(),a.end() 
#define mod 1000000007
//#define maxx 200006
#define ll long long 
#define quick    ios_base::sync_with_stdio(NULL),cin.tie(0);
#define listll vector< long long > 
#define listi vector< int> 
#define pii   pair<int , int> 
#define pll pair<long long , long long > 
#define minheap priority_queue<long long , vector< long long >, greater<long long > >
#define rep(i,a,b) for(int i=a;i<b;i++)
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


template < class T > using oset = tree< T , null_type, less  < T  > , rb_tree_tag , tree_order_statistics_node_update > ;


// end of #define 

// define globals ...
const int maxx = 2e5+26;

//write function from here ...


int n,k;
ll dp[111][4][2];
ll st[111];



ll dpp ( int len , int ck ,bool f){
	
	if(len == n+1)
	return ck==k;
	
	if(ck > k )
	return 0;
	
	
	if(dp[len][ck][f]!=-1)
	return dp[len][ck][f];
	
	
	ll ret =0 ;
	ll p = f? st[len-1] : 9;
	
	for( ll i =0; i <= p;i++){
		
		
		ret+= dpp(len+1, ck+ (i!=0), f && (i==p) ) ;
		
		
	} 
	
	 	
	
	
	
	return dp[len][ck][f] = ret;
}





int Main(){



string s;
cin>>s;

cin>>k;
n = s.length();


for(int i =0 ; i < k+1; i++)

memset(dp,-1,sizeof(dp));


int i=0 ;
for(auto c:s ) {
	
	st[i++]= c - '0';
}

   cout << dpp(1,0,1);


return 0;

}



int main(){
 quick;
int t =1; 
//cin>>t;
while(t-- )
 Main();

 return 0;


}


Measured memory_bytes: 3660
N,W = map(int,input().split())
w,v = [0]*N,[0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())
    
dp = [[10**9+1]*(sum(v)+1) for i in range(N+1)]
dp[0][0] = 0

#v[i]を使うかどうか
for i in range(N):
    #価値がjのときの最小の重さ総量
    for j in range(sum(v)+1):
        if j >= v[i]:
            dp[i+1][j] = min(dp[i][j-v[i]]+w[i],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
            
ans = 0

for i in range(sum(v)+1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)

Measured memory_bytes: 119404
N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)
 
dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1
 
for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]
 
print(dp[N][N * maxn] - 1)

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

using namespace std;

const int NS = (int)1e5 + 4;
int N;
int A[NS], B[NS];

int main(){
    scanf("%d", &N);
    for(int i = 1; i <= N + 1; ++i) scanf("%d", A + i);
    for(int i = 1; i <= N; ++i) scanf("%d", B + i);
    long long ans = 0;
    for(int i = 1; i <= N; ++i){
        int val = min(A[i], B[i]);
        ans += val, A[i] -= val, B[i] -= val;
        val = min(A[i + 1], B[i]);
        ans += val, A[i + 1] -= val, B[i] -= val;
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1152
#include<stdio.h>

int main(void){
	int n,l,i,j,f[128]={0},t,k;
	char s[128][128];
	scanf("%d%d",&n,&l);
	for(i = 1;i <= n;i++){scanf("%s",s[i]);}
	for(i = 1;i <= n;i++){
		t = 0;
		for(j = 1;j <= n;j++){
			if(f[j]){continue;}
			if(t == 0){t = j;}
			for(k = 0;k < l;k++){
				if(s[j][k] < s[t][k]){t = j;break;}
				if(s[j][k] > s[t][k]){break;}
			}
		}
		printf("%s",s[t]);
		f[t]++;
	}
	printf("\n");
	return 0;
}

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

using namespace std;

int main()
{
    int n,k,a;
    cin>>n>>k;
    vector<int>v;
    for(int i=0;i<n;i++)
    {
        cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    int diff=INT_MAX;
    for(int i=0;i<=n-k;i++)
    {
        diff=min(diff,v[i+k-1]-v[i]);
    }
cout<<diff<<endl;
return 0;
}



Measured memory_bytes: 892
def bubbleSort(A, N):
    cnt = 0
    flag = 1
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                flag = 1
                cnt += 1
    return A, cnt

N = int(input())
A = [int(_) for _ in input().split()]

A, cnt = bubbleSort(A, N)
print(" ".join([str(i) for i in A]))
print(cnt)



Measured memory_bytes: 5608
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

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

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

	int a[n];
	bool memo[n];
	REP(i, n){
		cin >> a[i];
		memo[i] = false;
	}

	int step = 1;

	int current = 0;

	while (1){
		if (a[current] == 2){
			cout << step << endl;
			return 0;
		}
		if (memo[current] == false){
			memo[current] = true;
		}
		else{
			cout << -1 << endl;
			return 0;
		}

		current = a[current] - 1;
		step++;
	}
}


Measured memory_bytes: 768
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MOD1 1000000007
#define MOD2 998244353
#define LIMIT1 200002
#define LIMIT2 500002
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(i=0;i<n;i++)
#define max(a,b) ((a)>(b) ? (a) : (b))
#define min(a,b) ((a)<(b) ? (a) : (b))
#define zt(a,b) (max((a),(b))-min((a),(b)))
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll nPr(int n,int r){ll i,result=1;rep(i,r){result*=(ll)(n-i);}return result;}
ll nCr(int n,int r){ll i,result=1;if(n<r) return 0;rep(i,min(r,n-r)){result*=(ll)(n-i);result/=(ll)(i+1);}return result;}
#define fact(n) nPr((int)(n),(int)(n))
#define nHr(n,r) nCr((int)((n)+(r)+1),(int)(r))
#define sankaku(x) (((x)*((x)+1))/2)
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,1,-1,-1};
int upint(const void *a, const void *b) { return *(int *)a < *(int *)b ? -1 : *(int *)a > *(int *)b ? 1 : 0; }
int downint(const void *a, const void *b) { return *(int *)a < *(int *)b ? 1 : *(int *)a > *(int *)b ? -1 : 0; }
int upchar(const void* left, const void* right) {return strcmp((char *)left,(char *)right);}
int downchar(const void* left, const void* right) {return strcmp((char *)right,(char *)left);}
ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
void initialize(){
    
}
int main(void){
  initialize();
  ll n,m,i,j,k,result=0;
  int a[LIMIT2]={0};
  char s[LIMIT1];
  
  scanf("%lld %lld",&n,&m);
  printf("%lld",n*m/gcd(n,m));
  return 0;
}



Measured memory_bytes: 128
#include <stdio.h>
#include <math.h>
int main(void){
  long long int N;
  scanf("%lld", &N);
  long long int a, b;
  for(long long int i = 1; i <= sqrt(N); i++){
  	if(N % i ==0){
  		a = i;
  		b = N / i;
  	}
  }
  printf("%lld",a + b -2);
  return 0;
}

Measured memory_bytes: 128
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n-1):
  if p[i] == i+1:
    p[i],p[i+1] = p[i+1],p[i]
    ans += 1
if p[n-1] == n: ans += 1 # 順列最後の値を確認
print(ans)

Measured memory_bytes: 20572
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <list>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <cmath>
#define _GLIBCXX_DEBUG
using namespace std;
const long long INF = 1LL << 60;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    vector<int> P(N);
    for(int i=0;i<N;i++){
        cin >> P[i];
    }
    int cnt =1;
    int min ;
    min = P[0];
    for(int i=1;i<N;i++){
        if(min>=P[i]){
            min = P[i];
            cnt++;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3976
# -*- coding: utf-8 -*-

N=input()

#約数列挙
def make_divisors(n):
    divisors=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n/i:
                divisors.append(n/i)
    return divisors

def func(a,b):
    return a**5-b**5

L=make_divisors(N)
for yakusu in L:
    for a in range(10**3):
        b=a-yakusu
        if func(a,b)==N:
            print a,b
            quit()

Measured memory_bytes: 73184
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

// 整数スキャン（複数）
/*
int x;
scanf("%d",&x);
int y;
scanf("%d",&y);
int z;
scanf("%d",&y);

// n個の整数のスキャン
/*
ll a[n] = {};
rep(i,n){
    scanf("%lld",&a[i]);
}
*/

// 文字列スキャン
/*
string s;
cin >> s;
*/


int main() {
    int n;
    scanf("%d",&n);

    if(n<1200){
        puts("ABC");
    }else if(n<2800){
        puts("ARC");
    }else{
        puts("AGC");
    }


    return 0;
    int ans = 0;

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


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

#define vd vector<double>
 
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define vc vector<char>
#define vcc vector< vector<char> >
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a = b; return 1; } return 0; }
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
// #define mp make_pair
//#define endl '\n'
 
int main() {
	ll n;
	cin >> n;
	ll ans = 0;
    for(ll k = 1;k <= sqrt(n);k++){
		if(n % k == 0){
			ll m = n / k - 1;
			if(k < m){
				ans += m;
			}
		}
	}
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100000 + 10;
int n,a[N],b[N],c[N];
LL dp[N][3];
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	dp[1][0]=a[1],dp[1][1]=b[1],dp[1][2]=c[1];
	for(int i=2;i<=n;i++){
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
	}
	printf("%lld\n", max(max(dp[n][0],dp[n][1]),dp[n][2]));
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using V = vector<ll>;
using P = pair<ll,ll>;

int main(){
    vector<ll> co(1e5+10,0);
    ll n,k;cin >>n>>k;
    for (int i = 0; i < n; ++i) {
        ll a,b;cin >>a>>b;
        co[a]+=b;
    }
    for (ll u = 0; u <1e5+10 ; ++u) {
        if(co[u]>=k) {
            cout << u << endl;
            return 0;
        }
        k-=co[u];
    }
    return 0;
}

Measured memory_bytes: 1024
N = int(input())
A =[[0]*10 for i in range(10)]
 
for i in range(1,N+1):
  a = int(str(i)[0])
  b = int(str(i)[-1])
  A[a][b] += 1
 
cnt = 0
for _ in range(1,N+1):
  a = int(str(_)[0])
  b = int(str(_)[-1])
  cnt += A[b][a]
  
print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 5010;
typedef long long ll;

int n, A, B, p[maxn], rp[maxn];
ll f[maxn][maxn];
int sum[maxn], K[maxn][maxn], C[maxn][maxn];

int main() {
	scanf("%d%d%d", &n, &A, &B);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
		rp[p[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = n; j >= 1; j--) {
			K[i][j] = K[i][j+1];
			if (rp[j] >= i) K[i][j] = rp[j];
		}
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 1; i <= n; i++) {
			if (p[i] >= j) sum[i] = sum[i-1] + 1;
			else sum[i] = sum[i-1];
		}
		for (int i = 1; i <= n; i++) {
			int k = K[i][j];
			if (k) {
				C[i][j] = sum[k]-sum[i-1];
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = n; j >= 1; j--) {
			if (!K[i][j]) f[i][j] = 0;
			else {
				ll c = C[i][j], k = K[i][j];
				f[i][j] = min(1ll*A*(c-1)+f[k+1][p[k]+1], B+f[i][p[k]+1]);
			}
		}
	}
	printf("%lld\n", f[1][1]);
	return 0;
}

Measured memory_bytes: 392192
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
//#define T_ int
using namespace std;
//struct bit{T_ arr[1000005];int lowbit(int x){return x&(-x);}void add(int x,T_ y){for (int i=x;i<=n;i+=lowbit(i)) arr[i]+=y;}T_ query(int x){T_ s=0;for (int i=x;i>0;i-=lowbit(i)) s+=arr[i];return s;}};
//struct seg{struct treedot{int l,r;T_ sum,add;void update(T_ x){sum+=(r-l+1)*x; add+=x;}}c[800005];void pushdown(int id){if (c[id].add){c[id*2].update(c[id].add);c[id*2+1].update(c[id].add);c[id].add=0;}}void pushup(int id){c[id].sum=c[id*2].sum+c[id*2+1].sum;}void build(int id,int l,int r){if (l>r) return;c[id].l=l;c[id].r=r;c[id].sum=0;c[id].add=0;if (l==r) c[id].sum=0;else{int mid=l+(r-l)/2;build(id*2,l,mid);build(id*2+1,mid+1,r);pushup(id);}}void update(int id,int le,int ri,T_ x){if (le>c[id].r||ri<c[id].l) return;if (le<=c[id].l&&c[id].r<=ri) c[id].update(x);else{pushdown(id);update(id*2,le,ri,x);update(id*2+1,le,ri,x);pushup(id);}}T_ query(int id,int le,int ri){if (ri<c[id].l||c[id].r<le) return 0;if (le<=c[id].l&&c[id].r<=ri) return c[id].sum;T_ ans=0;pushdown(id);ans+=query(id*2,le,ri);ans+=query(id*2+1,le,ri);pushup(id);return ans;}};
//struct bit_2d{T_ a[2005][2005];int lowbit(int x){return x&(-x);}void add(int x,int y,T_ z){int i,j;for (i=x;i<=2000;i+=lowbit(i)){for (j=y;j<=2000;j+=lowbit(j)){a[i][j]+=z;}}}T_ query(int x,int y){int i,j;T_ s=0;for (i=x;i;i-=lowbit(i)){for (j=y;j;j-=lowbit(j)){s+=a[i][j];}}return s;}T_ query(int x,int y,int xx,int yy){return query(xx,yy)-query(x-1,yy)-query(xx,y-1)+query(x-1,y-1);}};
int n,m,i,j,mx,v,x,y,d[200005];
vector<int> bi[200005];
void dfs(int x,int fa)
{
	if (d[x]>mx){
		mx=d[x];v=x;
	}
	ff(bi[x],it) if (*it!=fa){
		d[*it]=d[x]+1;dfs(*it,x);
	}
}
int main()
{
	scanf("%d",&n);
	fz1(i,n-1){
		scanf("%d%d",&x,&y);
		bi[x].push_back(y);
		bi[y].push_back(x); 
	}
	mx=0;v=1;d[v]=0;dfs(1,0);
	mx=0;d[v]=0;dfs(v,0);
	if (mx%3==1) puts("Second"); else puts("First"); 
	return 0;
}

Measured memory_bytes: 21376
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    S, T = list(input()),list(input())

    len_of_S = len(S)
    counter = {}
    seen = set()
    for i in range(len_of_S):
        if S[i] in seen:
            counter[S[i]].append(i) # 常に単調増加
        else:
            counter[S[i]] = [i]
            seen.add(S[i])

    len_of_T = len(T)

    if not T[0] in seen:
        print(-1)
        exit()

    counts = counter[T[0]]
    if len(counts) == 0:
        print(-1)
        exit()

    pre = counts[0]
    rep = 1

    for i in range(1,len_of_T):
        if not T[i] in seen:
            print(-1)
            exit()

        counts = counter[T[i]]
        if len(counts) == 0:
            print(-1)
            exit()

        j = bisect.bisect_left(counts,pre)
        mx = len(counts)

        while j < mx and not counts[j] > pre:
            j += 1

        # print(pre,rep)
        if j<mx:
            pre = counts[j]
        else:
            pre = counts[0]
            rep += 1
        # print(pre,rep)

    # print(counter[T[::-1][0]],len_of_S)
    rep -= 1
    ans = rep * len_of_S  + pre + 1
    print(ans)




if __name__ == "__main__":
  main()

Measured memory_bytes: 60476
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	ll x, y;
	ll ans = 0;

	cin >> x >> y;

	ll now = x;

	while (now >= x && now <= y) {
		ans++;
		now = now * 2;
	}

	cout << ans << endl;
}

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

int main(void){
    int a = 0, b = 0;
    int ans = 0;

    scanf("%d%d", &a, &b);

    ans += a - 1;

    if(a <= b){
        ans++;
    }

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

    return 0;

} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
template<class T>
void dump(vector<T> &vec){
	for(int i=0;i<vec.size();i++){
		cout << vec[i];
		if(i+1<vec.size())cout << ' ';
		else cout << endl;
	}
	return;
}
template<class T>
void input(vector<T>& vec,int n){
	vec.resize(n);
	for(int i=0;i<n;i++){
		cin >> vec[i];
	}
}
int N;
vector<ll> a;
int main(){
	cin >> N;
	input(a,N);
	int ans = 0;
	int idx = 0;
	int s = -1;
	while(idx<N){
		ans++;
		s = idx;
		while(idx<N&&((s==idx)||((a[idx-1]-a[s])*(a[idx]-a[idx-1])>=0ll))){
			idx++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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 main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  if (a < 10 && b < 10)
    cout << a*b << endl;
  else
    cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int s, hh, mm, ss;
int main(void) {
  scanf("%d", &s);
  hh = s / 3600;
  mm = s / 60 % 60;
  ss = s % 60;
  printf("%d:%d:%d\n", hh, mm, ss);
  return 0;
}


Measured memory_bytes: 2076
# comment test comment test
# comment test comment test
# comment test comment test
# comment test comment test
# comment test comment test
n, k = gets.split.map(&:to_i)
trees = []
n.times do
  trees << gets.to_i
end
trees.sort!
ans = trees[-1] - trees[0]
n.times do |i|
  break if trees[i+k-1].nil?
  diff = trees[i+k-1] - trees[i]
  ans = [ans, diff].min
end

puts ans

Measured memory_bytes: 4016
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{BufWriter, Write};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        w: usize,
        h: usize,
        s: usize,
        d: usize,
        n: usize,
    }

    let W = w;
    let H = min(2 * W, h);
    let S = min(2 * H, s);
    let D = min(2 * S, d);

    let mut ans = n / 2 * D;
    if n % 2 == 1 {
        ans += S;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define N 1234
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
using namespace std;
int h[N][N];
int n, m;
void Constr(int U, int D, int L, int R) {
	if (U == D && L == R)	return h[U][L] = 1, void();
	int m1 = (U + D)>>1, m2 = (L + R) >> 1;
	Constr(U, m1 - 1, L, m2 - 1);
	Constr(U, m1 - 1, m2 + 1, R);
	Constr(m1 + 1, D, L, m2 - 1);
	Constr(m1 + 1, D, m2 + 1, R);
	h[m1][m2] = 1;
}
int main() {
	read(n), read(m);
	n = (1 << n) - 1, m = (1 << m) - 1;
	int mx = max(n, m);
	Constr(1, mx, 1, mx);
//	if (n <= m) {
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				printf("%d", h[i][j]);
			}
			putchar('\n');
		}
	return 0;
}


Measured memory_bytes: 8112
#include<stdio.h>
int main(void){
  int n,d;
  int x[10][10];
  float k=0.0;
  int c=0;
  int sei;
  int i,j,p=1;
  int s;
  scanf("%d %d",&n,&d);
  for(i=0;i<n;i++){
    for(j=0;j<d;j++){
      scanf("%d",&x[i][j]);
    }
  }
  for(i=0;i<n;i++){
    for(p=i+1;p<n;p++){
      for(j=0;j<d;j++){
      	k+=(x[i][j]-x[p][j])*(x[i][j]-x[p][j]);
      }
      for(sei=1;sei<=126;sei++){
      		s=sei*sei;
      		if(k==s) {
        		c++;
        		break;
      		}
      }
      k=0;
    }
    
  }
  printf("%d",c);
  return 0;
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

if sum(a) < sum(b):
    print(-1)
else:
    c = list(a[i]-b[i] for i in range(n))
    c.sort()
    if c[0] >= 0:
        print(0)
    else:
        extra = sum(c)
        cnt = 0
        for i in range(n):
            if c[i] > 0 and c[i] <= extra:
                extra -= c[i]
                cnt += 1
        print(n-cnt)

Measured memory_bytes: 84656
s=int(input())
n=s//3
m=0
def comb(a,b): #a,bは整数　aCbを出力
        m=1
        for i in range(1,a+1):
            m*=i
        n=1
        for i in range(1,b+1):
            n*=i
        k=1
        for i in range(1,a-b+1):
            k*=i
        return((m//k//n)%(10**9+7))

for i in range(n):
    p=s-2*(i+1)
    m+=comb(p-1,i)
print(m%(10**9+7))


Measured memory_bytes: 9220
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <cmath>
#include <limits>
#include <tuple>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

int main()
{
	int N;
	cin >> N;
	vector<int> a(N);
	vector<ll> b(N);
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		b[i] = a[i];
		if (i > 0)
			b[i] += b[i - 1];
	}
	ll ans = (ll)std::numeric_limits<ll>::max() / 3;
	for (int i = 1; i < N; i++) {
		ll x = b[i - 1];
		ll y = b[N - 1] - x;
		ans = min(ans, abs(x - y));
	}
	cout << ans << endl;
	return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll memo[404][404];
int A[404];
ll SA[404];

ll dpdp(int L,int R) {
	if(L+1==R) return 0;
	if(memo[L][R]>=0) return memo[L][R];
	memo[L][R]=1LL<<60;
	for(int M=L+1;M<R;M++) memo[L][R]=min(memo[L][R],dpdp(L,M)+dpdp(M,R));
	return memo[L][R]+=SA[R-1]-SA[L-1];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>A[i];
		SA[i]=SA[i-1]+A[i];
	}
	
	cout<<dpdp(1,N+1)<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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


class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String name;
		int num;

		while(true){

			try{
				name=br.readLine();
				num=Integer.parseInt(name);
				num=(num*num*num);
				System.out.println(num);
			}

			catch(Exception e){
				System.exit(0);
			}
		}
	}
}

Measured memory_bytes: 24196
def game(t, s)
  cnt = 0
  r = l = s[0]
  (1...s.size).each do |i|
    t == 1 ? r = s[i] : l = s[i]
    if r % 3 == 1 && l % 3 != 1 || r % 3 == 2 && l % 3 == 0
      r, l = l, r
      t = 1 - t
      cnt += 1
    end
    t = 1 - t
  end
  cnt
end

while s = gets.chomp
  break if s == '#'
  s = s.split('').map(&:to_i)
  p [game(0, s), game(1, s)].min
end

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

typedef long long ll;
typedef long double ld;

typedef pair<int, int> p;

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

    ll x;
    cin >> x;

    ll ans = x / 11LL * 2LL;
    x %= 11LL;

    if(x != 0) {
        if(x <= 6) ans++;
        else ans += 2LL;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Collections;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    sc.close();
    int bigger = Math.max(A, B);
    int smaller = Math.min(A, B);
    StringBuilder S = new StringBuilder();
    for (int i = 0; i < bigger; i++) {
      S.append(smaller);
    }
    System.out.println(S);
  }
}


Measured memory_bytes: 21588
s = input()

ans = 0
for i in range(1, len(s)):
  tmp_s = s[: - i]
  tmp_N = len(tmp_s)
  if tmp_N % 2 == 1:
    continue
  tmp_s_l = tmp_s[:tmp_N//2]
  tmp_s_r = tmp_s[tmp_N//2:]
  if tmp_s_l == tmp_s_r:
    ans = tmp_N
    break

print(ans)


Measured memory_bytes: 61876
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef vector<Int> vInt;
typedef pair<int,int> pint;
typedef pair<Int,Int> pInt;
typedef vector<string> vstring;
typedef vector<pint> vpint;
typedef vector<pInt> vpInt;
typedef stringstream SS;

template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define repn(i,m,n) for(int i=(m);i<(n);++i)
#define repd(i,n) for(int i=(n)-1;i>=0;--i)
#define repnd(i,m,n) for(int i=(n)-1;i>=(m);--i)
#define rep0(i,n) for(i=0;i<(n);++i)
#define repn0(i,m,n) for(i=(m);i<(n);++i)
#define repd0(i,n) for(i=(n)-1;i>=0;--i)
#define repnd0(i,m,n) for(i=(n)-1;i>=(m);--i)
#define repc(i,n) for(int i=0;i<=(n);++i)
#define repcn(i,m,n) for(int i=(m);i<=(n);++i)
#define repcd(i,n) for(int i=(n);i>=0;--i)
#define repcnd(i,m,n) for(int i=(n);i>=(m);--i)
#define repc0(i,n) for(i=0;i<=(n);++i)
#define repcn0(i,m,n) for(i=(m);i<=(n);++i)
#define repcd0(i,n) for(i=(n);i>=0;--i)
#define repcnd0(i,m,n) for(i=(n);i>=(m);--i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define IL for(;;)
#define MP make_pair
#define PB push_back
#define X second
#define Y first
#define p_queue(n) priority_queue<n,vector<n>,greater<n> >
#define PUTLINE cout<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647/3;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

string str[30];
int dis[30][30];

int main() {
	int h, w;
	IL {
		cin >> h >> w;
		if (h == 0 && w == 0) break;
		rep (i, h) cin >> str[i];
		rep (i, h) rep (j, w) dis[i][j] = INF;
		int x, y;
		rep0 (y, h) rep0 (x, w) if (str[y][x] == 'A') goto aaa;
		aaa:;
		queue<pint> que;
		que.push(MP(y, x));
		dis[y][x] = 0;
		while (!que.empty()) {
			pint now = que.front();
			que.pop();
			int cost = dis[now.Y][now.X];
			rep (i, 4) {
				if (now.X + dx[i] < 0 || w <= now.X + dx[i]) continue;
				if (now.Y + dy[i] < 0 || h <= now.Y + dy[i]) continue;
				if (str[now.Y + dy[i]][now.X + dx[i]] == '#') continue;
				if (dis[now.Y + dy[i]][now.X + dx[i]] <= cost + 1) continue;
				dis[now.Y + dy[i]][now.X + dx[i]] = cost + 1;
				que.push(MP(now.Y + dy[i], now.X + dx[i]));
			}
		}
		string move;
		cin >> move;
		rep0 (y, h) rep0 (x, w) if (str[y][x] == 'B') goto bbb;
		bbb:;
		int cost = 0;
		rep (iii, 100) rep (i, sz(move)) {
			if (move[i] == '2' && y < h - 1) ++y;
			if (move[i] == '4' && x > 0) --x;
			if (move[i] == '6' && x < w - 1) ++x;
			if (move[i] == '8' && y > 0) --y;
			++cost;
			if (cost >= dis[y][x]) {
				cout << cost << " " << y << " " << x << endl;
				goto ccc;
			}
		}
		cout << "impossible" << endl;
		ccc:;
	}
	return 0;
}

Measured memory_bytes: 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */

public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}

	static class Task {
		public void solve(int testNumber, InputReader in, PrintWriter out) {
			int N = in.nextInt();
			int[] array = new int[N];

			long x   = 0;
			long y   = 0;

			for(int i = 0; i < N; i++) {
				array[i] = in.nextInt();
				y += array[i];
			}

			long deg = Long.MAX_VALUE;
			long ans = deg;
			
			for(int i = 0; i < N - 1; i++) {
				x   += array[i];
				y   -= array[i];
				deg =  Math.abs(x - y);
				if(deg < ans) {
					ans = deg;
				}
			}	
			out.println(ans);
		}
	}

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

	}
}


Measured memory_bytes: 45580
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		int X = scan.nextInt();

		List<Integer> list = new ArrayList<>();
		list.add(0);

		for(int i = 0; i < N; i++) {
			list.add(scan.nextInt());
		}

		List<Integer> points = new ArrayList<>();

		int val = 0;
		for(int i = 0; i < N + 1; i++) {

			val += list.get(i);
			points.add(val);
		}
		
		int count  = 0;
		for(int i = 0; i < points.size(); i++) {
			if(points.get(i) <= X) {
				count++;
			}
		}
		System.out.println(count);
	}
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

signed main(void)
{
	int n;
	cin >> n;
	ll a = 0;
	REP(i, n) {
		int p, n;
		char c;
		cin >> p >> c >> n;
		if(c == '(') a += n;
		else a -= n;
		if(a == 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
 
using namespace std;
 
 
 
int main()
{
    double a,b;
    int least, step;
    cin>>a>>b;
    step=floor(log(b)/log(a));
    least = (pow(a,step)-1)/(a-1);
    //cout<<step<<" "<<least<<endl;
    for(int i=0; i<=10; i++)
    {
        if(i*(a-1)>=b-pow(a,step))
        {
            cout<<least+i;
            return 0;
        }
    }
 
}

Measured memory_bytes: 640
import sys
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
antena = [a,b,c,d,e]
state = 1
for i in range(len(antena)):
    for j in range(i+1,len(antena)):
        if antena[j]-antena[i]<=k:
            state = 1
        else:
            state = 0
            break
    if state == 0:
        print(":(")
        sys.exit()
print("Yay!")



Measured memory_bytes: 3064
N = int(input())
A = [int(x) for x in input().split()]

from collections import defaultdict as dd
Dict = dd(lambda:0)
for a in A:
    Dict[a] += 1

if N & 1: Dict[0] += 1
f = (lambda:(lambda x:0 if x&1 else 2) if N&1 else (lambda x:2 if x&1 else 0))()
Possible = {i:f(i) for i in range(N)}
for key,value in Dict.items():
    if value != Possible[key]:
        print(0)
        exit()
else:
    print(2**(N//2)%1000000007)
                



Measured memory_bytes: 28492