akhauriyash/Code-Regression huggingface dataset:
from itertools import permutations
from copy import deepcopy
board = [["."] * 8 for _ in range(8)]
N = int(input())

def check(r, c, board):
    # 4つのループで8方向のblockを移動不可にする
    for i in range(8):
        if board[i][c] == "Q": return False
        if board[r][i] == "Q": return False
    for i in range(-8,8):
        if 0 <= i + c < 8 and 0 <= i + r < 8:
            if board[i+r][i+c] == "Q": return False
        if 0 <= c+(-i) < 8 and 0 <= i + r < 8:
            if board[i+r][-i+c] == "Q": return False
    return True

rc = [list(map(int, input().split())) for _ in range(N)]

def main():
    for p in permutations(range(8)):
        tmp = deepcopy(board)
        for i, v in enumerate(p):
            tmp[i][v] = "Q"
        if not all(tmp[rc[i][0]][rc[i][1]] == "Q" for i in range(N)): continue
        judge = True
        for i, v in enumerate(p):
            tmp[i][v] = "."
            if check(i, v, tmp):
                pass
            else:
                judge = False
                break
            tmp[i][v] = "Q"
        if judge: return tmp
       
tmp = main()
for t in tmp:
    print(''.join("Q" if i == "Q" else "." for i in t))




Measured memory_bytes: 6328
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
using namespace std;
int main()
{
    int n, x;
    long long a[maxn] = {0};
    cin >> n >> x;
    long long  count = 0;
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    for (int i = 0; i < n; i++)
    {
        if (a[i] > x)
        {
            count += (a[i] - x);
            a[i] = x;
        }
        if (a[i] + a[i+1] > x)
        {
            count += (a[i+1] + a[i] - x);
            a[i+1] = a[i+1] - (a[i+1] + a[i] - x);
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
long long int maxi(int a,long long int b)
{
if(a>b)
return a;
return b;
}
int main()
{
long long int a,b,c;
cin>>a>>b>>c;
if(c>=a)
cout<<0<<" "<<maxi(0,b-(c-a));
else
cout<<(long long)(a-c)<<" "<<b;
return 0;
}


Measured memory_bytes: 256
//Atcoder AGC_A
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL t,A,B,C,D;
map<LL,LL> memo;

LL solve(LL N) {
    if(N==0) return 0;
    if(N==1) return D;
    if(memo.count(N)) return memo[N];
    LL l2=(N/2)*2;
    LL r2=((N+1)/2)*2;
    LL l3=(N/3)*3;
    LL r3=((N+2)/3)*3;
    LL l5=(N/5)*5;
    LL r5=((N+4)/5)*5;

    LL res=1e18;
    if(N<res/D) res=N*D;
    res=min(res,llabs(l2-N)*D+A+solve(l2/2));
    res=min(res,llabs(r2-N)*D+A+solve(r2/2));

    res=min(res,llabs(l3-N)*D+B+solve(l3/3));
    res=min(res,llabs(r3-N)*D+B+solve(r3/3));

    res=min(res,llabs(l5-N)*D+C+solve(l5/5));
    res=min(res,llabs(r5-N)*D+C+solve(r5/5));

    memo[N]=res;

    return res;
}

int main() {
    int T;
    cin>>T;
    
    for(t=0;t<T;t++){
        memo.clear();
        LL N;
        cin>>N;
        cin>>A>>B>>C>>D;
        cout<<solve(N)<<endl;
    }
}

Measured memory_bytes: 4448
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;


int n;
long long a[100002];
long long dp[100002][2];
long long rec(int pos, int stat){
	if (pos == 0){return 0ll;}
	dp[pos][stat] = max(rec(pos-1, 0) + (2*stat-1)*(-1)*a[pos-1], rec(pos-1, 1) - (2*stat-1) * (-1) * a[pos-1]);
	return dp[pos][stat];
}
int main(){
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		scanf("%lld",&a[i]);
	}
	dp[1][0] = a[0];
	dp[1][1] = -a[0];
	for(int j=2;j<=n;j++){
		dp[j][0] = max(dp[j-1][0] + a[j-1], dp[j-1][1] - a[j-1]);
		dp[j][1] = max(dp[j-1][0] - a[j-1], dp[j-1][1] + a[j-1]);
	}
	printf("%lld\n", dp[n][0]);	
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
    long long n;
    cin >> n;
    
    vector<long long> a(n);

    for(long long i = 0; i < n; i++) cin >> a[i];


    vector<long long> ans(n);

    for(long long i = 0; i < n; i++){
        ans[a[i]-1] = i+1; 
    }

    for(long long i = 0; i < n; i++) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for (int i = (n); i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main()
{
    double n;
    cin >> n;
    OP(ceil(n / 2));
    return 0;
}

Measured memory_bytes: 256
solve :: Int -> Int -> Int -> Bool
solve n m k = elem k $ do
    a <- [0..n]
    f a <$> [0..m]
  where
    f a b = m * a + n * b - a * b * 2

main :: IO ()
main = do
    [n,m,k] <- map read . words <$> getLine :: IO [Int]
    putStrLn $ if solve n m k then "Yes" else "No"

Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>a(n),b(n),c(n);
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
    int dpa[n],dpb[n],dpc[n];
    dpa[0]= a[0];
    dpb[0] = b[0];
    dpc[0] = c[0];
    for(int i=1;i<n;i++)
    {
        dpa[i] = max(dpb[i-1]+a[i],dpc[i-1]+a[i]);
        dpb[i] = max(dpa[i-1]+b[i],dpc[i-1]+b[i]);
        dpc[i] = max(dpa[i-1]+c[i],dpb[i-1]+c[i]);
        //cout<<dp[2]<<endl;

    }
    //cout<<dp[2]<<endl;
    int ans = max(dpa[n-1],max(dpb[n-1],dpc[n-1]));
    cout<<ans<<endl;
}


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

const int INF = 1000000001;

int main(){
   int N;
   std::cin >> N;
   int A[N];
   for(int i=0; i<N; ++i){
      std::cin >> A[i];
   }

   int dp[N+1];
   std::fill(dp, dp+N+1, INF);
   std::reverse(A, A+N);
   for(int i=0; i<N; ++i){
      *std::upper_bound(dp, dp+N, A[i]) = A[i];
   }
   std::cout << std::lower_bound(dp, dp+N, INF) - dp << std::endl;

   return 0;
}


Measured memory_bytes: 1024
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans = 0;
		for(int i = 1; i <= n; i=i+2){
			int tmp = 0;
			for(int j = 1; j <= i; j++){
				if(i%j==0)tmp++;
				if(tmp==9)break;
			}
			if(tmp == 8)ans++;
		}
		System.out.print(ans);
	}
}


Measured memory_bytes: 23764
#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll MOD = 1000000000 + 7;


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

  ll ans = 1;
  for (ll i = 1; i <= n; ++i) {
    ans *= i;
    ans %=  MOD;
  }

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

Measured memory_bytes: 3600
def next(n):
	if n%2:
		return 3*n+1
	return n/2
cnt = {}
s = int(input())
cnt[s] = 1
i = 1
while True:
	w = next(s)
	i += 1
	if w in cnt:
		print(i)
		break
	cnt[w] = 1
	s = w

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

signed main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    string s; cin >> s;
    int n=(int)s.size();
    ll dp[n+1][2];
    dp[0][0]=0; dp[0][1]=1;
    for(int i=1;i<=n;i++){
        int x=s[i-1]-'0';
        dp[i][0]=min(dp[i-1][0]+x,dp[i-1][1]+10-x);
        dp[i][1]=min(dp[i-1][0]+x+1,dp[i-1][1]+10-x-1);
    }
    cout << dp[n][0] << endl;
}


Measured memory_bytes: 19808
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define bit(k) (1LL<<(k))
typedef long long ll;

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);

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

/*------------------------------------/
for library*/

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    map<int, int> map;
    int n;
    cin>>n;
    vector<ll> A(n);
    rep(i,n){
        cin>>A[i];
        map[A[i]]++;
    }
    for(auto p:map){
        if(p.second >=2){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    
}

Measured memory_bytes: 11264
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=25;
int n;
LL a[MAXN],b[MAXN],v[MAXN],ln;
LL ans;
LL dfs(int l,int r,int sl,int sr)
{
	if(l>r)return 0;
	if(l==r)return a[l]*(sl+sr);
	LL ret=(1LL<<63-1);
	for(int i=l;i<=r;i++)
	{
		LL s1=dfs(l,i-1,sl,sr+sl);
		LL s2=dfs(i+1,r,sl+sr,sr);
		ret=min(ret,s1+s2+a[i]*(sl+sr));
	}
	return ret;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	pr2(dfs(2,n-1,1,1)+a[1]+a[n]);
	return 0;
}


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

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

  int N, M, X, Y;
  cin >> N >> M >> X >> Y;

  vector<int> X_N, Y_M;

  while(N--) {
		int x;
		cin >> x;
		X_N.push_back(x);
	}

  while(M--){
    int y;
    cin >> y;
    Y_M.push_back(y);
  }

  vector<int>::iterator iter = max_element(X_N.begin(), X_N.end());
  size_t X_INDEX = distance(X_N.begin(), iter);
  int X_MAX = X_N[X_INDEX];

  iter = min_element(Y_M.begin(), Y_M.end());
  size_t Y_INDEX = distance(Y_M.begin(), iter);
  int Y_MIN = Y_M[Y_INDEX];

  if ( X_MAX < Y_MIN && ( X < Y_MIN && Y_MIN <= Y ) ) { 
    printf("No War");
  } else {
    printf("War");
  }
}

Measured memory_bytes: 256
fun main() {
    val pw = java.io.PrintWriter(System.out)
    Problem.solve(java.util.Scanner(System.`in`), pw)
    pw.flush()
}

data class ModInt(var value: Long) {
    init {
        value %= MOD
    }

    operator fun plus(b: Long): ModInt =
        ModInt((this.value + b) % MOD)

    operator fun plus(b: ModInt): ModInt =
        ModInt((this.value + b.value) % MOD)

    operator fun plusAssign(b: Long) {
        this.value += b
        this.value %= MOD
    }

    operator fun plusAssign(b: ModInt) {
        this.value += b.value
        this.value %= MOD
    }

    operator fun minus(b: Long): ModInt =
        ModInt((this.value + MOD - b) % MOD)

    operator fun minus(b: ModInt): ModInt =
        ModInt((this.value + (MOD - b.value)) % MOD)

    operator fun minusAssign(b: Long) {
        this.value += MOD - b
        this.value %= MOD
    }

    operator fun minusAssign(b: ModInt) {
        this.value += MOD - b.value
        this.value %= MOD
    }

    operator fun times(b: Long): ModInt =
        ModInt((this.value * b) % MOD)

    operator fun times(b: ModInt): ModInt =
        ModInt((this.value * b.value) % MOD)

    operator fun timesAssign(b: Long) {
        this.value *= b
        this.value %= MOD
    }

    operator fun timesAssign(b: ModInt) {
        this.value *= b.value
        this.value %= MOD
    }

    fun pow(p: Long): ModInt = when {
        p == 0L -> ModInt(1)
        p % 2 == 1L -> this * this.pow(p - 1)
        else -> {
            val half = this.pow(p / 2)
            half * half
        }
    }

    companion object {
        const val MOD = 1000000007L
    }
}

object Problem {
    fun solve(sc: java.util.Scanner, pw: java.io.PrintWriter) {
        val N = sc.next().toInt()
        val K = sc.next().toInt()

        val num = LongArray(K + 1)
        val ans = ModInt(0L)
        for (x in K downTo 1) {
            val n = ModInt(K.toLong() / x).pow(N.toLong())
            var x2 = x
            while (true) {
                x2 += x
                if (x2 > K) break
                n -= num[x2]
            }
            num[x] = n.value
            n *= x.toLong()
            ans += n
        }

        pw.println(ans.value)
    }
}


Measured memory_bytes: 55816
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 998244353
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif

const int INF = 0x7fffffff;
const int N=1e5+5;
/*
char *TT,*mo,but[(1<<15)+2];
#define getchar() ((TT==mo&&(mo=(TT=but)+fread(but,1,1<<15,stdin),TT==mo))?-1:*TT++)//*/
inline int read(){
    int x=0,rev=0,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return rev?-x:x;
}/*
struct Edge{
	int nxt,v;
//	int w;
//	int id;
}e[N<<1];
void add(int u,int v){
	e[++tot].v=v,e[tot].nxt=head[u],head[u]=tot;
	e[++tot].v=u,e[tot].nxt=head[v],head[v]=tot;
}*/
int n,a[N],ans;
int main(){
#ifdef Devil_Gary
    freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
#endif
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<=n;i++) for(int j=1;j<i;j++) for(int k=1;k<j;k++){
		if(a[i]==a[j]||a[j]==a[k]||a[k]==a[i]) continue;
		int s=a[i]+a[j]+a[k];
		int mx=max(a[i],max(a[j],a[k]));
		if((s-mx)>mx) ++ans;
		
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
    int a,p;
    scanf("%d%d", &a, &p);
    int pie = ((a*3)+p)/2;
    if(pie<1) printf("0\n");
    else{
        cout << pie << endl;
    }
    return 0;
}


Measured memory_bytes: 256
int main(){
int a,b,area,perimeter;
scanf("%d%d", &a, &b);
if("a>=1" && "a<=100" && "b>=1" && "b<=100"){
area=a*b;
perimeter=2*a+2*b;
printf("%d %d\n", area, perimeter);}
return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef pair<int,int> P;

int n;
vector<int> v[10];
vector<int>::iterator it;

void solve(){
	rep(i,10) v[i].clear();
	rep(i,n){
		int h[3];
		rep(j,3) cin >> h[j];
		sort(h,h+3);
		do{
			rep(j,60){
				int hh, mm, ss;
				hh = (h[0]+j)%60; 
				mm = (h[1]+j)%60;
				ss = (h[2]+j)%60;
				if(hh%5 != mm/12) continue;
				v[i].push_back((hh/5)*60*60+mm*60+ss);
			}
		} while(next_permutation(h,h+3));
	}
	rep(i,n) sort(v[i].begin(),v[i].end());
	int cnt = INF;
	P ans;
	rep(i,12*60*60){
		int tmp = 0;
		rep(j,n){
			it = lower_bound(v[j].begin(),v[j].end(),i);
			if(it == v[j].end()){
				tmp = INF;
				break;
			}
			tmp = max(tmp,*(it));
		}
		if(tmp-i < cnt){
			cnt = tmp-i;
			ans = P(i,tmp);
		}
	}
	int hh = ans.first/3600, mm = (ans.first%3600)/60, ss = ans.first%60;
	if(hh < 10) cout << "0" << hh << ":";
	else cout << hh << ":";
	if(mm < 10) cout << "0" << mm << ":";
	else cout << mm << ":";
	if(ss < 10) cout << "0" << ss << " ";
	else cout << ss << " ";
	hh = ans.second/3600; mm = (ans.second%3600)/60; ss = ans.second%60;
	if(hh < 10) cout << "0" << hh << ":";
	else cout << hh << ":";
	if(mm < 10) cout << "0" << mm << ":";
	else cout << mm << ":";
	if(ss < 10) cout << "0" << ss << endl;
	else cout << ss << endl;
}

int main(){
	while(cin >> n){
		if(n == 0) break;
		solve();
	}
}

Measured memory_bytes: 1224
import java.net.SecureCacheResponse;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        boolean ans = !(a > 8 || b > 8);

        System.out.println(ans ? "Yay!" : ":(");
    }
}


Measured memory_bytes: 21844
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        int l = scanner.nextInt() + scanner.nextInt();
        int r = scanner.nextInt() + scanner.nextInt();
        System.out.println(l == r ? "Balanced" : l > r ? "Left" : "Right");
    }
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define SFOR(i,a,b) for(int i=a;i<b;i++)
#define elif(a) else if(a)
#define INF INT_MAX
#define F first
#define S second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  char a;
  cin>>a;
  switch(a){
    case 'A':
      cout<<"T"<<endl;
      break;
    case 'T':
      cout<<"A"<<endl;
      break;
    case 'C':
      cout<<"G"<<endl;
      break;
    case 'G':
      cout<<"C"<<endl;
      break;
  }

  return 0;
}



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

using namespace std;
#define ll long long

int main (void) {
    ll n, a, b;
    ll ret = 0;

    scanf("%lld%lld%lld", &n, &a, &b);
    /*
    int j=0;
    if(a!=0){
        for(int i=a;i<n;i+=a){
            j++;
            i+=b;
            if(n < i){
                cout << a*j << endl;
            }
        }
    }else{
        cout << 0 << endl;
    }
    if(a!=0) cout << a*j+n-(a*j+b*j) << endl;
    */
   if(a!=0){
       if(n%(a+b)){
           if(n%(a+b) > a){
               cout << a*(n/(a+b))+a << endl;
           }else{
               cout << a*(n/(a+b))+n%(a+b) << endl;
           }
       }else{
           cout << a*(n/(a+b)) << endl;
       }
   }else{
       cout << 0 << endl;
   }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long int
#define endl '\n'
using namespace std;

void solve(){
   int n, m, sum = 0; cin >> n >> m;

   for(int i = 0 ; i < m ;++i){
       int x; cin >> x;
       sum += x;
   }

   if(sum > n) cout << -1 << endl;
   else cout << n - sum << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3616
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using namespace std;

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  string s;
  int k;
  cin>>s>>k;
  for(auto& c:s){
    if(c=='a') continue;
    int count='z'-c+1;
    if(count<=k){
      k-=count;
      c='a';
    }
  }
  s[s.size()-1]+=k%26;
  if(s[s.size()-1]>'z'){
    s[s.size()-1]-='z'-'a';
  }
  cout<<s<<endl;

  return 0;
}


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

from collections import deque

q = deque()

def calc(d, c):
    if c&1:
        q.append(d)
    if c == 1:
        return 0
    d *= 2
    c>>=1
    if d >= 10:
        return c * 2 + calc(1+d%10, c)
    return c + calc(d, c)
    

def main():
    M = int(input())
    ans = 0
    for i in range(M):
        d, c = map(int, input().split())
        ans += calc(d, c)
    
    num = q.popleft()
    while len(q) > 0:
        t = q.popleft()
        num += t
        if num >= 10:
            num = 1 + num%10
            ans += 1
        ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 126852
#include<stdio.h>
#include<stdlib.h>
#define N 100

int n,u=0;
int d[N],k[N];
int v[N][N],c[N][N];


void SSSP(int n,int x)
{
  int i;

  d[n]=x;

  for(i=0;i<k[n];i++){
    if(d[v[n][i]]>x+c[n][i]){
      SSSP(v[n][i],x+c[n][i]);
    }
  }
  return;
}


int main(){

  int i,j,u;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&u);
    scanf("%d",&k[u]);

    for(j=0;j<k[u];j++){
      scanf("%d %d",&v[u][j],&c[u][j]);
    }
  }
  for(i=0;i<n;i++){
    d[i]=1000000;
  }
 
SSSP(0,0);
 
 for(i=0;i<n;i++){
   printf("%d %d\n",i,d[i]);
 }
 return 0;
}

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

using namespace std;

int main() {
	vector<string> output;
	string input, cardStr;
	int h, m;

	cin >> cardStr;
	cin >> m;

	while(1) {
		cin >> input;
		if('-' == input.front()) {
			output.push_back(cardStr);
			break;
		}

		if('a' <= input.front() && input.front() <= 'z'){
			output.push_back(cardStr);
			cardStr = input;
			cin >> m;
		}
		else{
			h = stoi(input);
			string temp = cardStr.substr(0, h);
			cardStr.erase(0, h);
			cardStr.append(temp);
		}
	}

	for(const auto& e : output) {
		cout << e << endl;
	}

	return 0;
}


Measured memory_bytes: 3136
N, M = map(int, input().split())

a = [None] * M
b = [None] * M

for i in range(M):
    a[i], b[i] = map(int, input().split())

p = [[] for i in range(N + 1)]

for i in range(M):
    p[b[i]].append(M + i)

for i in range(M):
    p[a[i]].append(i)

ok = [False] * M
nx = []
ans = 0

for i in range(1, N + 1):
    for j in p[i]:
        if j < M:
            nx.append(j)
        else:
            if ok[j - M]:
                continue

            while nx:
                ok[nx[-1]] = True
                nx.pop()

            ans += 1

print(ans)

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

typedef long long ll;

int n;
ll a[100005];
__int128_t ans;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    ans=1;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]==0){
            cout<<0<<endl;
            return 0;
        }
    }
    ll p=1e18;
    for(int i=0;i<n;i++){
        ans*=a[i];
        if(ans>p){
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<(ll)ans<<endl;

    return 0;
}


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

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

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

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

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

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

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

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

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



const LL mod = 1000000007;

LL gcd(LL a, LL b) { if (a%b == 0) { return b; } else return gcd(b, a%b); }
LL lcm(LL a, LL b) { return a / gcd(a, b)*b; }

#define Yes_ cout<<"Yes"<<endl; return 0;
#define No_ cout<<"No"<<endl; return 0;


#define YES_ cout<<"YES"<<endl; return 0;
#define NO_ cout<<"NO"<<endl; return 0;

#define POSSIBLE cout<<"POSSIBLE"<<endl; return 0;
#define IMPOSSIBLE cout<<"IMPOSSIBLE"<<endl; return 0;



LL conbi2(LL n, LL r) {
	if (r>n || r<0LL)return 0LL;
	LL i;
	LL s = 1LL;
	for (i = 1LL; i <= r; i++)s = s * (n + 1LL - i) / i;
	return s;
}

int main() {

	int N;
	cin >> N;
	vector<LL> A(N),B,C;
	REP(i, N) { cin >> A[i]; }
	B = A;
	sort(ALL(A));
	LL c = (N) / 2;


	REP(i, N) {

		if (B[i] < A[c]) {
			cout << A[c] << endl;

		}
		else {
			cout << A[c-1] << endl;

		}

	}
	/*int N;
	cin >> N;
	vector<LL> a(N);

	REP(i, N) { cin >> a[i]; }

	sort(ALL(a), greater<LL>());
	LL max_ = -1; 
	PII ans;
	REP(i, N) {
		for (int j = i + 1; j < N; j++) {
			LL comb = a[i]-max(a[i]-a[j],a[j]);
			if (comb > max_) {
				ans.first = a[i];
				ans.second = a[j];
				max_ = comb;
			}
		}
	}

	cout << ans.first << " " << ans.second << endl;*/
}

Measured memory_bytes: 5376
#include <stdio.h>
#include <string>
using namespace std;

const char dat[10][2] = {
    "w", "", "k", "s", "t", "n", "h", "m", "y", "r"
};
const char au[] = "aiueo";

char s[1024];

int main() {
    const string of = "TLURD";
    scanf("%s", s);
    for (int i = 0; s[i]; i+=2) {
        const int ix = of.find(s[i+1]);
        if (s[i] == '0' && ix == 2) printf("nn");
        else printf("%s%c", dat[s[i]-'0'], au[ix]);
    }
    printf("\n");
    return 0;
}

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

struct start { start() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(10);
}; }start;

typedef long long ll;


int main(){
    int a,b;
    rep(i,0,3000){
        cin >> a >> b;
        if(a+b == 0) break;
        else cout << min(a,b) << " " << max(a,b) << endl;
    }
    return 0;
}


Measured memory_bytes: 3100
import scala.io.StdIn

object Main extends App {
  val Array(a, b, c, d) = StdIn.readLine().split(' ').map(_.toInt)

  val ac = scala.math.abs(a - c)
  val ab = scala.math.abs(a - b)
  val bc = scala.math.abs(b - c)

  println(if (ac <= d || (ab <= d && bc <= d)) "Yes" else "No")

}


Measured memory_bytes: 27332
#include <iostream>
#include <string>
using namespace std;
int main(void){
    string o,e;
    cin>>o>>e;
    for(int i=0;i<e.length();i++){
        cout<<o[i]<<e[i];
    }
    if(o.length()==e.length()){
        cout<<endl;
    }else{
        cout<<o[o.length()-1]<<endl;
    }
    
}


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

#define sz(x) (int)(x.size())
#define FOR(x,y,z) for(int x = y; x <= z; x++)
#define int long long

const int N = 1e5 + 2, inf = 1e18, mod = 1e9 + 7;

string s;
int n, dp[13][N];

int power(int a, int b, int p){
	int ret = 1;
	a %= p;
	while(b > 0){
		if(b % 2 == 1)
			ret = ret * a % p;
		b /= 2;
		a = a * a % p;
	}
	return ret;
}

int go(int id, int rem){
	if(id >= n)
		return rem == 5;

	int &ans = dp[rem][id];
	if(~ans)
		return ans;
	ans = 0;

	if(s[id] != '?'){
		int dig = s[id] - '0';
		int next_rem = rem + dig * power(10, id, 13);
		ans = (ans + go(id + 1, next_rem % 13)) % mod;
	}else{
		for(int i = 0; i < 10; i++){
			int next_rem = rem + i * power(10, id, 13);
			ans = (ans + go(id + 1, next_rem % 13)) % mod;
		}
	}
	return ans;
}

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

	memset(dp, -1, sizeof(dp));
	cin >> s;
	n = sz(s);
	reverse(s.begin(), s.end());
	cout << go(0, 0);
}


Measured memory_bytes: 21740
#include<iostream>
#include<cstdio>
#include <cstring>
#include<map>
#include<string>
#include<stack>
#include <sstream>
#include<vector>
using namespace std;

int ryoukin(int n){
	int ans;
	if(n<=10) ans=1150;
	else if(n<=20) ans=1150+ ((n-10)*125);
	else if(n<=30) ans= 1150 + 1250 + ((n-20)*140);
	else ans = 1150 + 1250 + 1400 + ((n-30)*160);
	return ans;
}


int main(){
	int n;
	while(cin>>n)
	{
		if(n==-1) break;
		cout<< 4280-ryoukin(n) <<endl;
	}
	return 0;
}

Measured memory_bytes: 1160
import sys
input=sys.stdin.readline
from itertools import combinations

X,Y=(int(x) for x in input().rstrip('\n').split())
if (X+Y) % 3 != 0:
  print(0)
else:
  t = (X+Y)//3
  if X<t or Y<t:
    print(0)
  else:
    s = abs(X-Y)
    if s==t:
      print(1)
    else:
      a = (t-s) // 2      
      res = t
      for i in range(1,a):
        res = res*(t-i)
        ad = pow(i+1,1000000005,1000000007)%1000000007
        res = res*ad
        res = res%1000000007
      print(res%1000000007)

Measured memory_bytes: 9248
#include <iostream>
using namespace std;
int gcd(int a, int b) {
    if (a%b == 0) {
        return b;
    } else {
        return gcd(b, a%b);
    }
}
int main() {
    int n;
    cin >> n;
    int result;
    cin >>result;
    for (int i=0; i<n-1; i++) {
        int a;
        cin >> a;
        result = gcd(result, a);
    }
    cout << result << endl;
}

Measured memory_bytes: 3608
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R


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

	cin >> N >> M;
	vector<long long int>v(N);
	for (auto &i : v)cin >> i;
	long long int ans = 0;
	for (int i = 0; i < N; i++)ans += abs(v[i] - i);
	vector<long long int>add(N);
	vector<long long int>minus(N);
	for (int i = 0; i < N; i++) {
		add[i] = min((long long int)i, v[i]) * 2;
		minus[i] = max((long long int)i, v[i]) * 2;
	}
	sort(add.begin(), add.end(), greater<long long int>());
	sort(minus.begin(), minus.end());
	long long int by = 0;
	for (int i = 0; i < M; i++) {
		if (add[i] - minus[i] < 0)continue;
		by += add[i];
		by -= minus[i];
	}
	cout << ans + by << endl;
	return 0;
}



Measured memory_bytes: 5196
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int ret=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return w*ret;
}
inline long long read_l()
{
	long long ret=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return w*ret;
}
int n;
long long k;
long long a[200010];
long long s[200010];
map<long long,int> mp;
long long ans=0;
int main()
{
	n=read(),k=read_l();
	for(int i=1;i<=n;i++) a[i]=read_l();
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i],s[i]%=k;
	mp[0]++;
	for(int i=1;i<=n;i++)
	{
		if(i-k>=0) mp[((s[i-k]-i+k)%k+k)%k]--;
		ans+=(long long)mp[((s[i]-i)%k+k)%k],mp[((s[i]-i)%k+k)%k]++;
	}
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

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

  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  int cnt = 0;
  while (true) {
    if (*max_element(h.begin(), h.end()) == 0) {
      break;
    }
    int idx = 0;
    while (idx < n) {
      if (h[idx] == 0) {
        idx++;
      } else {
        cnt++;
        while (idx < n && h[idx] != 0) {
          h[idx]--;
          idx++;
        }
      }
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<cstdio>

using namespace std;

int e;

int check(int ne){
	if(ne==0)return 0;
	int lb=0,ub=10001;
	while(ub-lb>1){
		int mid=(lb+ub)/2;
		if(mid*mid<=ne)lb=mid;
		else ub=mid;
	}
	return (ne-lb*lb+lb);
}

int main(void){
	while(1){
		scanf("%d",&e);
		if(e==0)break;
		int lb=0,ub=101;
		while(ub-lb>1){
			int mid=(lb+ub)/2;
			if(mid*mid*mid<=e)lb=mid;
			else ub=mid;
		}
		//printf("%d\n",lb);
		int res=1000000;
		for(int i=0;i<=lb;i++){
			res=min(res,i+check(e-i*i*i));
		}
		printf("%d\n",res);
	}
	return 0;
}

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

int main(){
    int a, b;
    cin >> a >> b;
    int minus = 1;
    for(int i=a;i<=b;i++){
        if(i==0){
            cout << "Zero" << endl;
            return 0;
        }
        if(i<0)
            minus = minus*(-1);
    }
    if(minus == 1)
        cout  << "Positive" << endl;
    else
        cout  << "Negative" << endl;
    return 0;
}

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

int main(){
    int w,a,b;
    cin>>w>>a>>b;
    int ans=1000000;
    if(b>=a+w){
        ans=b-a-w;
    }
    else if(a>=b+w){
        ans=a-b-w;
    }
    else ans=0;
    cout<<ans<<endl;
}



Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll ans = 0;
    REP(i,n){
        ll t = (1+n-i)*(n-i)/2;
        ans += t;
        //cout << ans << endl;
    }
    
    REP(i,n-1){
        ll u,v;
        cin >> u >> v;
        if(u>v) swap(u,v);
        ll t = u * (n-v+1);
        ans -= t;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3648
<?php 
  $k = trim(fgets(STDIN));
  fscanf(STDIN,"%d %d",$a,$b);
  for($i=$a; $i<=$b; $i++){
    if($i%$k == 0){
      echo "OK\n";
      exit;
    }
  }
  echo "NG\n";

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

namespace ConsoleApp1
{
    class Program
    {
        static long Read() => long.Parse(Console.ReadLine());

        static void Main(string[] args)
        {
            long n = Read();
            long[] A = new long[5];
            for (int i = 0; i < A.Length; i++)
            {
                A[i] = Read();
            }

            long ans = ((n - 1) / A.Min() + 1) + 4;
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13268
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>
#include <numeric>
typedef long long ll;
using namespace std;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
//#define int long long
#define all(vec) vec.begin(), vec.end()

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

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

	int A,B;
	cin>>A>>B;
	if(B%A==0){
		cout << A + B << endl;
	}else{
		cout << B - A << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(n) for(int I = 0; (I) < (n); ++(I) )
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define el cout << endl
#define dump(x) cout << " " << #x << "=" << x
#define vdump(v) for(size_t T=0; T<v.size(); ++T){cout << " " << #v << "[" << T << "]=" << v[T];} cout << endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    int n;
    cin >> n;
    vector<int> adj(n);
    repeat(i, n) {
        cin >> adj[i];
        --adj[i];
    }
    
    int pos = 0;
    repeat(i, n) {
        pos = adj[pos];
        if (pos == 1) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}   

Measured memory_bytes: 640
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
#mo=998244353
#input=sys.stdin.readline

n=I()
p6=[6**i for i in range(0,7)][::-1]
p9=[9**i for i in range(0,7)][::-1]
ans=n

for i in range(n+1):
    m=0
    n6=i
    n9=n-i
    for j in p6:
        m+=n6//j
        n6%=j
    for j in p9:
        m+=n9//j
        n9%=j
    ans=min(ans,m)
print(ans)

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

using namespace std;

#define REP(i, n) for(int i = 0; i < (n); i++)
#define SORT(v, n) sort(v, v+n);
#define SSORT(v, n) sort(v, v+n, greater<int>())

int main(){
	int n,i;
	cin >> n >> i;
	cout << n-i+1 << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <math.h>
#include <set>
  
#define REP(i,n)for (int i=0;i<(n);i++)
#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define ll long long
using namespace std;
typedef pair<int,int> P;
int N, W[300], dp[300][300];
  
int rec(int l,int r){
	if(l>=r)return 0;
	if(dp[l][r]!=-1)return(dp[l][r]);
  	int ret = 0;
  	if(abs(W[l]-W[r])<=1&&rec(l+1,r-1)==r-l-1)ret=r-l+1;
  	for(int m=l;m<r;m++)ret=max(ret,rec(l,m)+rec(m+1,r));
  	return (dp[l][r]=ret);
}
  
int main(){
  	while(1){
		cin>>N;
		if(N==0)break;
    	for(int i=0;i<N;i++)cin>>W[i];
    	memset(dp,-1,sizeof(dp));
		cout<<rec(0,N-1)<<endl;
  	}
}


Measured memory_bytes: 3424
#include <bits/stdc++.h>
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef long long int64;
template<class T,class U>bool chmax(T &a, const U &b) { if (a<b) { a=b; return true; } return false; }
template<class T,class U>bool chmin(T &a, const U &b) { if (b<a) { a=b; return true; } return false; }
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cii(n);
    auto ans = "APPROVED";
    rep(i, n){
        cii(a);
        if (a % 2 == 0 && !(a % 3 == 0 || a % 5 == 0))
            ans = "DENIED";
    }
    co(ans);
    return 0;
}

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

int main() {
    int n, m, state[20][20], p[20];

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> state[i][0];
        for (int j = 0; j < state[i][0]; j++) {
            cin >> state[i][j + 1];
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> p[i];
    }

    int mask = 0, ans = 0;
    while (mask < (1 << n)) {
        bool isall = true;

        for (int i = 1; i <= m; i++) {
            int cnt_on = 0;

            for (int j = 1; j <= state[i][0]; j++) {
                if (mask & (1 << (state[i][j] - 1))) {
                    cnt_on++;
                }
            }

            if (cnt_on % 2 != p[i]) {
                isall = false;
            }
        }

        if (isall) {
            ans++;
        }

        mask++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
/*
  AtCoder Beginner Contest 101
  B - Digit Sums
*/

#include<iostream>
using namespace std;

unsigned int N, S;

int main() {
  scanf("%u", &N);

  S = 0;
  uint buf = N;
  while(buf != 0) {
    S += buf % 10;
    buf /= 10;
  }

  if (N % S == 0) printf("Yes\n");
  else printf("No\n");
  return 0;
}

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

int prime(int p){
  for (int i=2; i<p; i++){
    if (p % i == 0){
      return 1;
    }
  }
  return 0;
}

int main() {
  int X;
  cin >> X;
  while (prime(X)){
    X++;
  }
  cout << X << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string S;
    cin >> S;
    int ans = 0;
    for(int i = 0; i < S.size(); i++){
        if(S.at(i) == 'o'){
            ans++;
        }
    }
    cout << 700 + 100 * ans << endl;
    return 0;
}

Measured memory_bytes: 3588
import java.util.*;
public class Main {
	double EPS = 1.0e-04;
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while(n-- > 0){
			double [] compDis = new double[3];
			for(int i = 0; i < 3; i++){
				compDis[i] = sc.nextDouble();
			}
			int m = sc.nextInt();
			double [][] inputDis = new double[m][3];
			for(int i = 0; i < m; i++){
				for(int j = 0; j < 3; j++){
					inputDis[i][j] = sc.nextDouble();
				}
			}
			
			calc(compDis, inputDis);
			
		}
	}
	
	private void calc(double [] compDis, double [][] inputDis){
		int m = inputDis.length;
		for(int i = 0 ; i < m; i++){
			for(int j = 0; j < m; j++){
				for(int k = 0; k < m; k++){
					if(i == j || i == k || j == k) continue;
					double a = getDis(inputDis[k], inputDis[j]);
					double b = getDis(inputDis[i], inputDis[k]);
					double c = getDis(inputDis[j], inputDis[i]);
					double rate = compDis[0] / a;
					double value1 = rate * b;
					double value2 = rate * c;
					if(isSimilar(compDis[1],value1) && isSimilar(compDis[2], value2)){
						System.out.println((i+1) + " "+ (j+1) + " " + (k+1));
						return;
					}
				}
			}
		}
	}
	
	

	private boolean isSimilar(double comp, double value1) {
		if(value1 - EPS <= comp && comp <= value1 + EPS){
			return true;
		}
		return false;
	}

	private double getDis(double [] a, double [] b) {
		double x = a[0] - b[0];
		double y = a[1] - b[1];
		double z = a[2] - b[2];
		double res = x * x + y * y + z * z;
		return Math.sqrt(res);
	}

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

Measured memory_bytes: 13000
#include "iostream"
#include <stdlib.h>

int compare(const void *x, const void *y) {
	return *(int*)x - *(int*)y;
}

int main()
{
	int n;
	int i;
	long int *A;
	long int sum = 0;

	std::cin >> n;
	A = (long int*)malloc(n * sizeof(long int));
	for (i = 0;i < n;i++) {
		std::cin >> A[i];
	}

	qsort(A, n, sizeof(long int), compare);

	if (n % 2 == 0) {
	for (i = 0;i < n / 2 - 1;i++) {
		sum -= 2 * A[i];
	}
	sum -= A[i];
	sum += A[i + 1];

	for (i = n / 2 + 1;i < n;i++) {
		sum += 2 * A[i];
	}
	}
	else {
		long int sum_1 = 0;
		long int sum_2 = 0;
		for (i = 0;i < n / 2 - 1;i++) {
			sum_1 -= 2 * A[i];
		}
		sum_1 -= A[i];
		sum_1 -= A[i + 1];

		for (i = n / 2 + 1;i < n;i++) {
			sum_1 += 2 * A[i];
		}
		for (i = 0;i < n / 2 ;i++) {
			sum_2 -= 2 * A[i];
		}
		sum_2 += A[i];
		sum_2 += A[i + 1];

		for (i = n / 2 + 2;i < n;i++) {
			sum_2 += 2 * A[i];
		}
		if (sum_1 < sum_2)sum = sum_2;
		else sum = sum_1;
	
	}

	std::cout << sum;

	return 0;
}



Measured memory_bytes: 1788
#include<cstdio>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N=200010;
const int mod=998244353;
int n,k,l[N],r[N],tr[N];
int Add(int a,int b){
	return a+b>=mod?a+b-mod:a+b;
}
void update(int x,int v){
	while(x<=n){
		tr[x]=Add(tr[x],v);
		x+=lowbit(x);
	}
	return;
}
int query(int x){
	int ret=0;
	while(x){
		ret=Add(ret,tr[x]);
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d",l+i,r+i);
	update(1,1);
	update(2,-1);
	for(int i=1;i<n;i++){
		int x=query(i);
		for(int j=1;j<=k;j++){
			if(i+l[j]<=n)
				update(i+l[j],x);
			if(i+r[j]+1<=n)
				update(i+r[j]+1,mod-x);
		}
	}
	printf("%d\n",query(n));
}

Measured memory_bytes: 4012
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;


int main(void){
    int n,l,sum=0;
    cin>>n>>l;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        a[i]=l+i-1;
        sum+=a[i];
    }
    int mi=10000,ans=0;
    for(int i=1;i<=n;i++){
        if(mi>=abs(sum-(sum-a[i]))){
            mi=abs(sum-(sum-a[i]));
            ans=sum-a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

ll power_mod(ll n, ll m)
{
    ll base = n;
    ll res = 1;
    while (m > 0)
    {
        if (m & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        m >>= 1;
    }
    return res;
}

ll fact[MAX_HW*10];
void init_fact()
{
    fact[0] = fact[1] = 1;
    rep(i, 2, MAX_HW*10)
        fact[i] = (fact[i - 1] * i) % MOD;
}

ll inv_mod(ll n)
{
    return power_mod(n, MOD - 2);
}

ll comb(int n, int m)
{
    if (n == 0 or m == 0) return 1;
    if (n == m) return 1;
    ll res = 1;
    res = (res * fact[n]) % MOD;
    res = (res * inv_mod(fact[m])) % MOD;
    res = (res * inv_mod(fact[n - m])) % MOD;
    return res;
}

int main()
{
    init_fact();
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    ll ans = 0;

    rep(i, b + 1, w + 1)
    {
        ans = (ans + (comb(h-a+i-2, i-1) * comb(a+w-(i-1)-2, a-1)) % MOD) % MOD;
        // cout << h-a+i-2<< ' ' << i-1 << ' ' << comb(h-a+i-2, i-1) << endl;
        // cout << a+w-(i-1)-2<< ' ' << a-1 << ' ' <<  comb(a+w-i-2, a-1)<< endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8064