akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

inline int popcount(uint x)
{
	x=(x&0x55555555)+(x>>1&0x55555555);
	x=(x&0x33333333)+(x>>2&0x33333333);
	x=(x&0x0f0f0f0f)+(x>>4&0x0f0f0f0f);
	x=(x&0x00ff00ff)+(x>>8&0x00ff00ff);
	return (x&0x0000ffff)+(x>>16&0x0000ffff);
}

int dfs(const vvi& g,int u)
{
	int res=1<<u;
	for(int v:g[u]) res|=dfs(g,v);
	return res;
}

int main()
{
	for(int n,m;~scanf("%d%d",&n,&m) && n|m;){
		vi cs(n);
		vvi g(n);
		rep(i,n){
			scanf("%d",&cs[i]);
			int k; scanf("%d",&k);
			rep(j,k){
				int r; scanf("%d",&r);
				g[i].push_back(r);
			}
		}
		
		vi bs(n);
		rep(i,n) bs[i]=dfs(g,i);
		
		vi sums(1<<n);
		rep(i,n) sums[1<<i]=cs[i];
		rep(i,1<<n) sums[i]=sums[i&-i]+sums[i-(i&-i)];
		
		int res=INF;
		rep(i,1<<n) if(popcount(i)<res){
			int b=0;
			rep(j,n) b|=(i>>j&1)*bs[j];
			if(sums[b]>=m) res=min(res,popcount(b));
		}
		printf("%d\n",res);
	}
}

Measured memory_bytes: 5292
#include<iostream>
#include<map>
int main () {
    
    long long N;
    std::cin >> N;
    std::map<long long,long long> div;
    for (long long i=2;i*i<=N;++i){
        while(N % i ==0) {
            ++div[i];
            N /= i;
        }
    }
    if (N!=1){
        div[N]=1;
    }

    long long u,t,ans=0;

    for (auto itr=div.begin();itr != div.end(); ++itr){
        u=1;
        t=itr->second;
        while(t >= u){
            ++ans;
            t-=u;
            ++u;
        }
    }

    std::cout<<ans;
    return 0;
}

Measured memory_bytes: 3636
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

S = input().rstrip()
l = list(S)
N = len(l)

if S == '1':
    print(1)
    exit()

def getbit(i, length):
    return format(i, '0' + str(length) + 'b')

bits = []
for i in range(2**(N-1)):
    bits.append(getbit(i, N-1))


ans = 0

for i in range(len(bits)):
    s = str(l[0])

    bitlist = list(bits[i])
    for j in range(len(bitlist)):
        if bitlist[j] == '0':
            pass
        else:
            s += '+'

        s += str(l[j+1])

    ans += eval(s)

print(ans)

Measured memory_bytes: 3064
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
constexpr int D=365;
constexpr int beam = 240;
int c[26];
int s[D][26];
int ans[D];

struct State{
    int val = 0;
    int out[D]={0};
    int cnt[26]={0};
};

constexpr bool operator< (const State &a, const State &b){
    return a.val<b.val;
}
constexpr bool operator> (const State &a, const State &b){
    return a.val>b.val;
}


void solve(int ca){
    int waste;
    scanf("%d",&waste);
    for (int i = 0; i < 26; ++i) {
        scanf("%d",c+i);
    }
    for (auto & i : s) {
        for (int & j : i) {
            scanf("%d",&j);
        }
    }

    priority_queue<State> pq[2];
    pq[0].push(State());
    for (int i = 0; i < D; ++i) {
        int prev=i&1,next = prev^1;
        for (int j = 0; !pq[prev].empty()&&j < beam; ++j) {
            auto state = pq[prev].top();
            pq[prev].pop();
            int dec=0;
            for (int k = 0; k < 26; ++k) { 
                state.cnt[k]++;
                dec+=c[k]*state.cnt[k];
            }
            for (int k = 0; k < 26; ++k) {
                const int inc = c[k]*state.cnt[k];
                const int tmp = state.cnt[k];
                const int tmp_val = state.val;
                state.val = state.val-dec+inc+s[i][k];
                state.cnt[k]=0;
                state.out[i]=k;
                pq[next].push(state);
                state.cnt[k]=tmp;
                state.val = tmp_val;
            }
        }
        pq[prev]=priority_queue<State>();
    }
    auto best = pq[D&1].top().out;
    for (int i = 0; i < D; ++i) {
        printf("%d\n",best[i]+1);
    }

}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


Measured memory_bytes: 35076
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 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;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        C solver = new C();
        solver.solve(1, in, out);
        out.close();
    }

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            long n = Long.parseLong(in.next());
            long m = Long.parseLong(in.next());
            long ans = n;
            long tmp = 0;
            if (m >= 2 * n) {
                tmp = m - 2 * n;
                ans += tmp / 4;
            } else {
                tmp = m / 2;
                ans = tmp;
            }

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 35776
#include<bits/stdc++.h>
using namespace std;
//from
//https://atcoder.jp/contests/abc110/submissions/3254887

const int mod=1e9+7;

struct com {
    int mod;
    vector<long long> mfact, rfact;

    com(int sz, int mod) : mfact(sz+1), rfact(sz+1), mod(mod) {
        mfact[0]=1;
        for (int i=1;i<mfact.size();i++) mfact[i]=mfact[i-1]*i%mod;
        rfact[sz]=inv(mfact[sz]);
        for (int i=sz-1;i>=0;i--) rfact[i]=rfact[i+1]*(i+1)%mod;
    }
    long long fact(int k) const {
        return (mfact[k]);
    }

    long long pow(long long x,long long n) const {
        long long ret=1ll;
        while(n>0) {
            if (n&1) (ret*=x)%=mod;
            (x*=x)%=mod;
            n>>=1;
        }
        return (ret);
    }
    long long inv(long long x) const {
        return (pow(x,mod-2));
    }

    long long P(int n, int r) const {
        if (r<0||n<r) return (0);
        return (mfact[n]*rfact[n-r]%mod);
    }

    long long C(int p,int q) const {
        if (q<0||p<q) return (0);
        return (mfact[p]*rfact[q]%mod*rfact[p-q]%mod);
    }

    long long H(int n, int r) {
        if(n<0||r<0) return (0);
        return (r==0?1:C(n+r-1,r));
    }
};

map<int, int> dp[32];

int rec(int x, int rest) {
    if(x==1) return rest==0;
    if(rest<=0) return 0;
    if(dp[rest].count(x)) return dp[rest][x];
    int ret=0;

    vector<int> div;
    for(int i=1;i*i<=x;i++) {
        if (x%i==0) {
            div.emplace_back(i);
            if(i*i!=x) div.emplace_back(x/i);
        }
    }

    for (auto &p:div) {
        if (x!=p) (ret+=rec(p, rest-1))%=mod;
    }
    return dp[rest][x]=ret;
}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    com beet(n+1,mod);
    int ret=0;
    for (int i=0;i<=min(31,n);i++) {
        int rest=n-1;
        auto add = beet.C(n,i);
        (add*=rec(m,i))%=mod;
        (ret+=add)%=mod;
    }
    printf("%d\n",ret);
}



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

const int INF = 1e9;

int main(){
    ll N; cin >> N;
    vector<int> memo;
    int dp[100001];
    for(int i = 0; i < 100001; i++) dp[i] = INF;
    int t1 = 6, t2 = 9;
    while(t1 < 100000){
        memo.push_back(t1);
        t1 *= 6;
    }
    while(t2 < 1e5){
        memo.push_back(t2);
        t2 *= 9;
    }
    memo.push_back(1);
    sort(memo.begin(), memo.end());
    for(auto itr: memo){
        dp[itr] = 1;
    }
    for(int i = 1; i <= N; i++){
        if(dp[i] == 1) continue;
        int j = 0;
        while(memo[j] < i){
            dp[i] = min(dp[i-memo[j]] + 1, dp[i]);
            j++;
        }
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 640
from collections import defaultdict

N = int(input())
s = [input().strip() for _ in range(N)]

h = defaultdict(int)
ans = 0
for si in s:
    ans += si.count('AB')
    if si[0] == 'B' and si[-1] == 'A':
        h['BA'] += 1
    elif si[0] == 'B':
        h['B'] += 1
    elif si[-1] == 'A':
        h['A'] += 1

if h['BA'] > 0:
    ans += h['BA']-1
    if h['B'] > 0:
        ans += 1
        h['B'] -= 1
    if h['A'] > 0:
        ans += 1
        h['A'] -= 1

ans += min(h['B'], h['A'])

print(ans)


Measured memory_bytes: 3956
// Ver19.02
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1 << 29
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  char s[11];
  int ans = INF;
  scanf("%s", s);
  for (int i = 0; i < strlen(s) - 2; i++)
  {
    ll maybe = (s[i] - '0') * 100 + (s[i + 1] - '0') * 10 + s[i + 2] - '0';
    maybe = llabs(maybe - 753);
    if (maybe < ans)
      ans = maybe;
  }
  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
    ll n,W;
    cin>>n>>W;
    vector<ll>wt(n),val(n);
    for(int i=0;i<n;i++){
        cin>>wt[i]>>val[i];
    }
    //dp[i][j] max value using first i items,weight of j
    ll dp[n+1][W+1];
    memset(dp,0,sizeof(dp));
    for(int j=0;j<=W;j++)
    dp[0][j]=0;
    for(int i=0;i<=n;i++)
    dp[i][0]=0;
    for(int i=1;i<=n;i++){
        for(int w=1;w<=W;w++){
            if(wt[i-1]<=w){
                //can include
                dp[i][w] =max(dp[i-1][w],val[i-1]+dp[i-1][w-wt[i-1]]);
            }
            else{
                //cant include
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    cout<<dp[n][W];
}
int main(){
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 79104
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n; cin >> n;
    vector< vector<int> > a(2, vector<int>(n));
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];

    int max = 0;
    int idx = 0;
    while (idx < n) {
        int tmp = 0;
        int base = 0;
        for (int i = 0; i < n; ++i) {
            tmp += a[base][i];
            if (idx == i) tmp += a[++base][i];
        }
        if (max < tmp) max = tmp;
        ++idx;
    }

    cout << max << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n)
{LL ret=1;LL b=a;while(n) {if(n&1)
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
#define MAXK 100000
#define MAXN 1000000000
int ar[MAXK];
int get(int n, int k){
    int i=0;
    while(i<k and ar[i]<=n)i++;
    return n-i;
}
typedef unsigned long long int ULL;
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()

bool isSafe(int r, int c, vector<vector<int> > arr) {
	int n = arr.size();
	int m = arr[0].size();
	return (r>=0 && r<n && c>=0 && c<m);
}

/////////////////////////////////////////////////////////////
bool diffSign(int a,int b) {
	return ((a>0 && b<0) || (a<0 && b>0));
}  

int main() 
{ 
	int x,n,k;
	cin>>n;
	cin>>k;
	int cnt=0;
	while(n--) {
		cin>>x;
		cnt += 2*min(x,k-x);
	}
	cout<<cnt;
	return 0; 
} 


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

typedef long long ll;

int main() {
    ll a,b;
    cin >> a >> b;
    bitset<32> bsa, bsb;
    bsa = a;
    bsb = b;
    
    cout << (bsa & bsb) << endl;
    cout << (bsa | bsb) << endl;
    cout << (bsa ^ bsb) << endl;
    

}



Measured memory_bytes: 3152
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner sc= new Scanner(System.in);
		int n = sc.nextInt();
		int i = 1;
		do{
			int x = i;
			if ( x % 3 == 0 ){
				System.out.print(" "+ i);
				continue;
			}
			while (true) {
				if (x % 10 == 3) {
					System.out.print(" " + i);
					break;
				}
				x /= 10;
				if (x != 0) continue;
				else break;
			}

		} while (++i <= n);
		System.out.println();
	}
}

Measured memory_bytes: 28812
L=input()
DIV=10**9+7
dp=[[0 for i in range(2)] for j in range(len(L))]

dp[0][0]=2
dp[0][1]=1

for i in range(1,len(L)):
  x=int(L[i])
  dp[i][0]=(dp[i-1][0]*2*(x==1)+dp[i-1][0]*1*(x==0))%DIV
  dp[i][1]=(dp[i-1][0]*1*(x==1)+dp[i-1][1]*3)%DIV

print((dp[-1][0]+dp[-1][1])%DIV)


Measured memory_bytes: 21228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) fixed << setprecision(x)
#define xout cerr
const ll inf = LLONG_MAX;
const long double pi = acos(-1);
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//const ll p = 1e9 + 7;
	//const ll p = 998244353;

	ll n, k;
	cin >> n >> k;
	vll a(n);
	for (ll i = 0; i < n; i++) cin >> a[i];

	ll x = a[0];
	for (ll i = 1; i < n; i++) x = __gcd(x, a[i]);

	sort(all(a));
	if (k % x == 0 && k <= a[n - 1]) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
using namespace std;
int students[1001];

int main()
{
    int n, mindiff;
    for (; ;) {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 0; i < n; i++) scanf("%d", &students[i]);
        sort(students, students+n);
        mindiff = 1000001;
        for (int i = 1; i < n; i++) {
            mindiff = min(mindiff, students[i] - students[i-1]);
            if (mindiff == 0) break;
        }
        printf("%d\n", mindiff);
    }
    return 0;
}



Measured memory_bytes: 2584
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using p = pair<int,int>;
 
int main() {
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    if (a+b < k) cout << a + a + b - k << "\n";
    else if (a < k) cout << a << "\n";
    else cout << k << "\n";
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define endl '\n'
#define pi pair<int, int>

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	string s;
	cin >> n >> s;
	
	if(n % 2 == 0 && s.substr(0, n / 2) == s.substr(n / 2, n / 2)) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define HMAX 1400
#define WMAX 1400
using namespace std;
int main(){
	int H,W,ms = 0;
	int dp[HMAX+10][WMAX+10] = {};
	cin >> H >> W;
	for (int i = 1; i < H+1; ++i)
	{
		for (int j = 1; j < W+1; ++j)
		{
			cin >> dp[i][j];
			if(dp[i][j] == 0){
				dp[i][j] = 1;
			}else{
				dp[i][j] = 0;
			}
		}
	}
	for (int i = 1; i < H+1; ++i)
	{
		for (int j = 1; j < W+1; ++j)
		{
			if(dp[i][j] != 0){
				int m = min(dp[i-1][j-1],dp[i-1][j]);
				dp[i][j] += min(m,dp[i][j-1]);
				ms = max(ms,dp[i][j]);
			}
		}
	}
	cout << ms*ms << "\n";
	return 0;
}

Measured memory_bytes: 10856
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(i,0,n)cout<<v[i]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tihs if(fopen("inp.txt","r"))freopen("inp.txt", "r", stdin),freopen("out.txt", "w", stdout);
using namespace std;

#define M 1000010


int main(){
	IOS;
	tihs;

	ll a,b,c,k;cin>>a>>b>>c>>k;
	ll mn=min(k,a),ans=0;
	k-=mn,ans+=mn;
	mn=min(k,b);
	k-=mn;
	mn=min(k,c);
	k-=mn,ans-=mn;
	cout<<ans;

	return 0;
}

	

Measured memory_bytes: 3644
import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    t = [[int(i) for i in input().split()] for _ in range(N)]

    dp = [[float("inf")]*(N*10**3+1) for _ in range(N+1)]

    dp[0][0] = 0
    for n in range(1, N+1):
        dp[n][0] = 0
        for v in range(1, N*10**3+1):
            dp[n][v] = min(dp[n-1][v], dp[n-1][max(0, v-t[n-1][1])]+t[n-1][0])
    ans = float("inf")*-1
    for i, v in enumerate(dp[N]):
        if v <= W:
            ans = max(ans, i)

    print(ans)


if __name__ == "__main__":
    main()


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

int s[2][105];
int a[2][105];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < 2; i++) {
    for (int ni = 0; ni < n; ni++) {
      cin >> a[i][ni];
    }
  }
  s[0][0] = a[0][0];
  s[1][0] = s[0][0] + a[1][0];
  for (int ni = 1; ni < n; ni++) {
    s[0][ni] = s[0][ni - 1] + a[0][ni];
    s[1][ni] = max(s[1][ni - 1], s[0][ni]) + a[1][ni];
  }
  cout << s[1][n - 1] << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

using T = tuple<ll, ll, ll>;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  string s;
  cin >> n >> s >> q;
  rep(_, q) {
    int k;
    cin >> k;
    vector<T> res(n);
    ll ans = 0;
    rep(i, n) {
      if (i)
        res[i] = res[i-1];
      if (i-k >= 0) {
        if (s[i-k] == 'D') {
          get<2>(res[i]) -= get<1>(res[i]);
          get<0>(res[i])--;
        }
        if (s[i-k] == 'M')
          get<1>(res[i])--;
      }
      if (s[i] == 'D')
        get<0>(res[i])++;
      if (s[i] == 'M') {
        get<1>(res[i])++;
        get<2>(res[i]) += get<0>(res[i]);
      }
      if (s[i] == 'C')
        ans += get<2>(res[i]);
    }
    cout << ans << '\n';
  }
  return 0;
}

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

signed main(){
    int n , m , a , x;
    long long ans=0;
    priority_queue<int> q;
    
    cin >> n >> m;
    for(int i=0 ;i<n ;i++ ){
        cin >> a;
        q.push(a);
    }
    
    for(int i=0 ;i<m ;i++ ){
        x = q.top();
        q.pop();
        q.push(x/2);
    }
    
    for(int i=0 ;i<n ;i++ ){
        ans += q.top();
        q.pop();
    }
    
    cout << ans << endl;
    
    return(0);
}

Measured memory_bytes: 892
#include <stdio.h>

int main() {
	int x = 0;
	int y = 0;
	while(1) {
		scanf("%d %d", &x, &y);
		if (x == 0 && y == 0) { break; }
		if (x < y) {
			printf("%d %d\n", x, y);
		}
		else {
			printf("%d %d\n", y, x);
		}
	}
	
	return 0;
}

Measured memory_bytes: 1808
import java.util.*;

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

        boolean[] b = new boolean[n];
        for (int i = 0; i < k; i++) {
            int d = sc.nextInt();
            for (int j = 0; j < d; j++) {
                int a = sc.nextInt();
                b[a - 1] = true;
            }
        }
        sc.close();

        int count = 0;
        for (int i = 0; i < b.length; i++) {
            if (!b[i]) {
                count++;
            }
        }

        System.out.println(count);
    }
}


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

int main() {
	int N; cin >> N;
	vector<int> V(N), C(N);
	for (int i = 0; i < N; i++)
		cin >> V[i];
	for (int i = 0; i < N; i++)
		cin >> C[i];
	int res = 0;
	for (int i = 0; i < N; i++) {
		res += max(0, V[i] - C[i]);
	}
	cout << res << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define _ << " _ " <<
#define TRACE(x) cerr << #x << " = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug
//#define TRACE(x)

using namespace std;

typedef long long llint;

const int MAXN = 100010;
const int MOD = 1e9 + 7;

int n, x[MAXN];

int main(void) {
  scanf("%d",&n);
  REP(i, n) scanf("%d",&x[i]);

  llint sol = 1;
  
  int t = 0;
  REP(i, n) {
    int b = t;
    sol = sol * (b + 1) % MOD;
    ++t;
    while (t > (x[i] + 1) / 2)
      --t;
  }

  cout << sol << endl;
  
  return 0;
}


Measured memory_bytes: 640
from math import gcd
A, B = map(int, input().split())
def factorize(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i ==0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr

n = gcd(A, B)
ans = factorize(n)
if ans[0][0] == 1:
    print(1)
    exit()
print(len(ans)+1)

Measured memory_bytes: 9408
#include<iostream>
using namespace std;
int main(){
	int N,K,i,j,S[100],B,a;
	while(a=1,cin>>N>>K,N||K){
		for(i=K;i--;)cin>>S[i];
		for(i=N;i--;)for(j=K;j--;)cin>>B,S[j]-=B,S[j]<0?a=0:0;
		cout<<(a?"Yes":"No")<<endl;
	}
}

Measured memory_bytes: 1152
L = input()
l = len(L)
MOD = 10**9 + 7
ans = 0
c = 0
for k in range(l):
    if L[k] == "1":
        ans += pow(3,l-k-1,MOD) * pow(2,c,MOD)
        ans %= MOD
        c += 1
ans += pow(2,c,MOD)
print(ans%MOD)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define deb(x) cout << #x << ':' << x << endl;
#define loop3(i, k, n) for(i=k; i<n; i++)
#define ll  long long 
#define loop(i,n) for(int i=0;i<n;i++)
#define loop2(i,n) for(int i = 1;i<=n;i+=1)
#define pb push_back
#define mp make_pair
#define v1d vector<ll> 
#define v2d vector<vector<ll>>
const ll INF = 1e18 +5 ;
void self_min(ll &a, ll b)
{
    a= min(a,b);
}
int main()
{
    ll N,W;
    cin>>N>>W;
    v1d w(N),v(N);
    loop(i,N)
    {
        cin>>w[i]>>v[i];
    }
    ll sum = 0;
    loop(i,N)
        sum+=v[i];
    v1d dp(sum+1,INF);
    dp[0] = 0;
    loop(i,N)
    {
        for(ll j = sum - v[i];j>=0;j--)
        {
            self_min(dp[j+v[i]],dp[j] + w[i]);
        }
    }
    
    ll ans = 0;
    for(ll i = 0; i<=sum; i++)
    {
        if(dp[i] <= W)
        ans = max(i,ans);
    }
    cout<<ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
	bool war = true;
	int N, M, X, Y;

	cin >> N >> M >> X >> Y;

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

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

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	for (int i = X + 1; i <= Y; i++)
	{
		if (x.back() < i && y.front() >= i)
		{
			war = false;
			break;
		}
	}

	if (war) cout << "War" << endl;
	else cout << "No War" << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;;
public class Main {
static Scanner s = new Scanner(System.in);
static int Time = 0;
static int[] l;
static int a,b = 1;
public static void main(String[] args) {
	int n = s.nextInt();
	int[][] gr = new int[n+1][n];
	int[] d = new int[n+1];
	l = new int[n+1];

	for(int i = 0;i < n;i++) {
		int u = s.nextInt();
		int k = s.nextInt();
		d[u] = -1;
		for(int j = 0;j < k;j++) {
			gr[u][j] = s.nextInt();
		}
	}
	d[1] = 0;
	l[0] = 1;

	mas(gr,d);

	for(int i = 1;i <= n;i++) {
		System.out.println(i + " " + d[i]);
	}
}

static void mas(int[][] gr,int[] d) {
	for(a = 0;a < b;a++) {
		int e = l[a];
		for(int i = 0;i < gr[e].length;i++) {
			int f = gr[e][i];
			if(d[f] == -1) {
				d[f] = d[e] + 1;
				l[b++] = f;
			}
		}
	}
}
}


Measured memory_bytes: 27960
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n,m;
int w[maxn];
ll v[maxn];
ll dp[maxn];
int main()
{
    gbtb;
    cin>>n>>m;
    repd(i,1,n)
    {
        cin>>w[i]>>v[i];
    }
    repd(i,1,n)
    {
        for(int j=m;j>=w[i];j--)
        {
            dp[j]=max(dp[j],1ll*dp[j-w[i]]+v[i]);
        }
    }
    cout<<dp[m];
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}


Measured memory_bytes: 5120
N, M = input().split()
H = input().split()
x2 = []
count = 0
for i in range(0, int(N)):
  x2.append(1)
for i in range(0, int(M)):
  A, B = input().split()
  if int(H[int(A)-1]) > int(H[int(B)-1]):
    x2[int(B)-1] = 0
  elif int(H[int(A)-1]) == int(H[int(B)-1]) :
    x2[int(B)-1] = 0
    x2[int(A)-1] = 0
  else:
    x2[int(A)-1] = 0
for j in range(0, int(N)):
  if x2[j-1] == 1:
    count += 1
print(count)
  

Measured memory_bytes: 17808
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;
int cnt[N];
vector<pair<int, int>> v1[N], v2[N], v3[N * 2 + 10], v4[N * 2 + 10];
void check(vector<pair<int, int>> v[], int n)
{
	for (int i = 0; i < n; i++)
	{
		if (v[i].empty()) continue;
		sort(v[i].begin(), v[i].end());
		for (int j = 0; j + 1 < v[i].size(); j++)
		{
			cnt[v[i][j].second]++;
			cnt[v[i][j + 1].second]++;
		}
	}
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	vector<int> v(n);
	for (auto &x : v) cin >> x;
	v.push_back(-1);
	int ans = 0;
	int cnt = 0;
	int pre = 0;
	for (auto &x : v)
	{
		if (x == pre) cnt++;
		else
		{
			ans += cnt / 2;
			cnt = 1;
			pre = x;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 28928
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<complex>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define DBL(x) ((x)*(x))
#define EPS 1e-10

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef complex<double> P;

int main(){
  int a,b;
  int c = 0;
  while(scanf("%d%d",&a,&b), a+b){
    bool flag = false;
    if(c++ != 0) puts("");
    do{
      if( (a%4 == 0 && a%100 != 0) || (a%400 == 0) ){
	flag = true;
	printf("%d\n",a);
      }
    }while(++a <= b);
    if(!flag) puts("NA");
  }
}

Measured memory_bytes: 0
n =int(input()) 
t = 0
for k in range(1,n+1,2):
  K = k
  ans = 1
  for i in range(1,int(K/2)+1,2):
    if k % i == 0:
      ans  += 1
  if ans == 8:
    t += 1
print(t)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define REP(i, n) for(long long 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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
 
int main(){
  string s1,s2,s3;
  cin >> s1 >> s2 >> s3;
  cout << s1[0] << s2[1] << s3[2];
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 10000

int NIL = -1;

typedef struct {
  int parent;
  int left,right;
} Node;

Node T[MAX];
int n;
int D[MAX],H[MAX];

void depth(int u,int p){
  if(u == NIL)return;
  D[u] = p;

  depth(T[u].left,p+1);
  depth(T[u].right,p+1);
}

int height(int u){
  int h1 = 0;
  int h2 = 0;

  if(T[u].left != NIL){
    h1 = height(T[u].left)+1;
  }  
  if(T[u].right != NIL){
    h2 = height(T[u].right)+1;
  }

  if(h1 > h2){
    H[u] = h1;
  } else {
    H[u] = h2;
  }
  
  return H[u];
}

int sibling(int u){
  if(T[u].parent == NIL)return NIL;
  
  if(T[T[u].parent].left != u && T[T[u].parent].left != NIL){
    return T[T[u].parent].left;
  }
  if(T[T[u].parent].right != u && T[T[u].parent].right != NIL){
    return T[T[u].parent].right;
  }
  
  return NIL;
}

void get(int u){
  int deg = 0;
  
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",sibling(u));

  if(T[u].left != NIL)deg++;
  if(T[u].right != NIL)deg++;
  
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].parent == NIL){
    puts("root");
  } else if(T[u].left == NIL && T[u].right == NIL){
    puts("leaf");
  } else {
    puts("internal node");
  }
}

  
  
int main(void){
  int i = 0;
  int l,r,v;
  int root = 0;
  
  scanf("%d",&n);

  for(i = 0;i < n;i++){
    T[i].parent = NIL;
  }
  
  for(i = 0;i < n;i++){
    scanf("%d %d %d",&v,&l,&r);
    
    T[v].left = l;
    T[v].right = r;
    if(l != NIL){
      T[l].parent = v;
    }
    if(r != NIL){
      T[r].parent = v;
    }
  }
  
  for(i = 0;i < n;i++)
    if(T[i].parent == NIL){
      root = i;
    }
    
  depth(root,0);
  height(root);

  for(i = 0;i < n;i++){
    get(i);
  }

  return 0;
}
  



Measured memory_bytes: 2052
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;
int c = 0;
void merge(vector<int>& orig, int l, int mid, int r) {
	int nl = mid - l;
	int nr = r - mid;
	vector<int> left(nl+1), right(nr+1);
	for (size_t i = 0; i < nl; i++)
	{
		left[i] = orig[l+i];
	}
	for (size_t i = 0; i < nr; i++)
	{
		right[i] = orig[mid+i];
	}
	left[nl] = INT_MAX;
	right[nr] = INT_MAX;

	int i = 0, j = 0;
	for (size_t k = 0; k < nl+nr; k++)
	{
		c++;
		if(left[i] < right[j]) {
			orig[l+k] = left[i];
			i++;
		} else {
			orig[l+k] = right[j];
			j++;
		}
	}
}



void mergesort(vector<int>& a, int l, int r) {
	if(l+1 >= r) return;
	
	int mid = (l+r)/2;
	mergesort(a, l, mid);
	mergesort(a, mid, r);
	merge(a, l, mid ,r);
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (size_t i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	mergesort(a, 0, n);
	for (size_t i = 0; i < n; i++)
	{
		if(i == 0) {
			cout << a[i];
			continue;
		}
		cout << " " << a[i];
	}
	cout << endl;
	cout << c << endl;

}



Measured memory_bytes: 6744
#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a,int b,int c){
    int d,e;
    d=__gcd(a, b);
    e=__gcd(c, d);
    return e;
}
int main()
{
    int a,b,c,k,sum=0,x;
    cin>>k;
for(a=1;a<=k;a++){
    for(b=1;b<=k;b++){
        for(c=1;c<=k;c++){
            int x=gcd(a,b,c);
            sum=sum+x;
        }
    }
}
    cout<<sum;
    return 0;
}


Measured memory_bytes: 3676
#include<stdio.h>
#include<string.h>
#define LEN 500001
#define NIL -1

int trance_command(char []);
void insert(int);
int find(int, int);
void print();
void inorder(int);
void preorder(int);

int P[LEN], L[LEN], R[LEN], Key[LEN];
int root=NIL;

int main()
{
  char command[10];
  int n, id;
  int z=0;
  int i, j, k;

  //intelization
  for(i=0; i<LEN; i++)
    {
      P[i]=NIL;
      L[i]=NIL;
      R[i]=NIL;
      Key[i]=NIL;
    }

  //read
  scanf("%d", &n);
  for(i=0; i<n; i++)
    {
      scanf("%s", command);
      //insert
      if(trance_command(command)==0)
	{
	  scanf("%d", &id);
	  Key[z]=id;
	  insert(z);
	  z++;
	}
      //print
      else if(trance_command(command)==1)
	{
	  inorder(root);
	  printf("\n");
	  preorder(root);
	  printf("\n");
	}
      //print
      else if(trance_command(command)==2)
	{
	  scanf("%d", &id);
	  j=find(root, id);
	  if(j!=NIL)printf("yes\n");
	  else printf("no\n");
	}
    }

  return 0;
}


//-------------------------
//this method is trancing command.
int trance_command(char c[])
{
  if(strcmp(c, "insert")==0)return 0;
  else if(strcmp(c, "print")==0)return 1;
  else if(strcmp(c, "find")==0)return 2;
}

void insert(int z)
{
  int y=NIL;
  int x=root;

  while(x!=NIL)
    {
      y = x;
      if(Key[z]<Key[x])x = L[x];
      else x = R[x];
    }
  P[z]=y;

  if(y==NIL)root=z;
  else if(Key[z]<Key[y])L[y]=z;
  else R[y]=z;
}

int find(int x, int key)
{
  while(x!=NIL && key!=Key[x])
    {
      if(key < Key[x])x=L[x];
      else x=R[x];
    }
  return x;
}

void inorder(int t)
{
  if(t!=NIL)
    {
      inorder(L[t]);
      printf(" %d", Key[t]);
      inorder(R[t]);
    }
}

void preorder(int t)
{
  if(t!=NIL)
    {
      printf(" %d", Key[t]);
      preorder(L[t]);
      preorder(R[t]);
    }
}

Measured memory_bytes: 8240
#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int(i)=int(a);i<=int (b);i++)
#define ff(i,a,b) for(int(i)=int (a);i<int (b);i++)
#define F(i,a,b) for(int (i)=int (a);i>=int (b);i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define vt vector
#define ll long long
#define ld long double
#define all(x) x.begin(),x.end()
#define lower(p,x) lower_bound(all(p),x)
#define upper(p,x) upper_bound(all(p),x)
#define ms(a,x) memset(a,x,sizeof a)
typedef pair<int,int> ii;
const double pi=acos(-1.0);
const double eps=1e-5;
const int mod=1e9+7,INF=1<<30,N=801;
int n,w;
int main(){
	cin>>n>>w;
	f(x,0,n){
		f(y,0,n){
			int sum=10000*x+y*5000;
			int z=n-x-y;
			if(z<0) continue;
			if(sum+1000*z==w){
				cout<<x<<" "<<y<<" "<<z;
				return 0;
			}
		}
	}
	cout<<"-1 -1 -1";
}





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

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

  vector<string> s(10);
  s[0] = "pon";
  s[1] = "pon";
  s[2] = "hon";
  s[3] = "bon";
  s[4] = "hon";
  s[5] = "hon";
  s[6] = "pon";
  s[7] = "hon";
  s[8] = "pon";
  s[9] = "hon";

  cout << s[N%10] << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#include <complex>
#include <unordered_map>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define DUPLE(a,b,c,d) (RANGE(a,c,d) || RANGE(b,c,d) || RANGE(c,a,b) || RANGE(d,a,b))
#define INCLU(a,b,c,d) (RANGE(a,c,d) && (b,c,d))
#define PW(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MODU 1000000007
#define bitcheck(a,b)   ((a >> b) & 1)
#define bitset(a,b)      ( a |= (1 << b))
#define bitunset(a,b)    (a &= ~(1 << b))
#define MP(a,b) make_pair((a),(b))
#define Manh(a,b) (abs((a).first-(b).first) + abs((a).second - ((b).second))
#define pritnf printf
#define scnaf scanf
#define itn int
#define PI 3.141592653589


#define izryt bool

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*) array, (T*) (array + N), val);
}
pii Dir[8] = { //?§????
	{ 0 ,1 },{ -1 ,0 },{ 1 ,0 },{ 0 ,-1 },
	{ 1 ,1 },{ 1 ,-1 },{ -1 ,1 },{ -1 ,-1 }
};



signed main() {
	int n;

	scanf("%d", &n);

	vector<ll> bam(n+1);
	ll sum = 0;
	REP(i, n) {
		scnaf("%lld", &bam[i+1]);
		sum += bam[i+1];
	}
	REP(i, n) {
		bam[i+1] += bam[i];
	}

	ll l = 0, r = sum/3+3;

	while (1) {
		ll mid = (l + r) / 2;
		bool f = 0;
		REP(i, n) {
			auto itr = lower_bound(bam.begin()+i,bam.end(), mid + bam[i]);
			if (itr == bam.end())
				break;
			auto bufi = itr;
			bufi++;
			auto itr2 = lower_bound(bufi, bam.end(), mid + *itr);
			if (itr2 != bam.end()) {
				if ((bam[i] + sum - *itr2) >= mid) {
					f = 1;
					break;
				}
			}
		}
		if (f) {
			l = mid;
		}
		else {
			r = mid;
		}
		if (r-l <= 1) {
			printf("%lld\n", l);
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 3616
MOD = 10 ** 9 + 7
N = gets.to_i
A = gets.split.map &:to_i

b = Array.new(N+1, 0) # 累積和テーブル
N.times { |i| b[i+1] = b[i] + A[i] }

ans = 0
N.times do |i|
  # 累積和を使って A[i+1] + ... + A[N] を求める
  sum = (b[-1] - b[i+1]) % MOD

  ans += A[i] * sum
  ans %= MOD
end

p ans

Measured memory_bytes: 29696
#include<stdio.h>
#include<math.h>
#include<string.h>


int main(){
	long long int uriage[4000][3],n,no,tanka,su,i,j,newflag,naflag;
	
	while(0<=scanf("%lld",&n)){
		if(n==0) break;
		
		memset(uriage,0,sizeof(uriage));
		
		for(i=0;i<n;i++){
			scanf("%lld%lld%lld",&no,&tanka,&su);
			
			newflag=0;
			
			for(j=0;j<n;j++){
				if(uriage[j][0]==no){
					uriage[j][1]+=tanka*su;
					newflag=1;
					break;
				}
			}
			
			if(newflag==0){
				for(j=0;j<n;j++){
					if(uriage[j][0]==0){
						uriage[j][1]+=tanka*su;
						uriage[j][0]=no;
						break;
					}
				}
			}
		}
		naflag=0;
		for(i=0;i<n;i++){
			if(uriage[i][0]==0)break;
			if(uriage[i][1]>=1000000){
				printf("%lld\n",uriage[i][0]);
				naflag=1;
			}
		}
		if(naflag==0)printf("NA\n");
	}
	return 0;
}

Measured memory_bytes: 0
# -*- coding: utf-8 -*-
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
seen = [[False for __ in range(w)] for _ in range(h)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
black_count = 0
white_count = 0


def dfs(x: int, y: int):
    global black_count, white_count

    if s[x][y] == '#':
        black_count += 1
    else:
        white_count += 1

    seen[x][y] = True

    for k in range(4):
        next_x = x + dx[k]
        next_y = y + dy[k]

        if 0 <= next_x < h and 0 <= next_y < w:
            if s[x][y] != s[next_x][next_y] and not seen[next_x][next_y]:
                dfs(next_x, next_y)


def main():
    from sys import setrecursionlimit
    setrecursionlimit(200000)

    global black_count, white_count
    ans = 0

    # See:
    # http://drken1215.hatenablog.com/entry/2019/01/13/035500
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#' and not seen[i][j]:
                black_count = 0
                white_count = 0
                dfs(i, j)
                ans += black_count * white_count

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 149492
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

#define MAX_N 2500

template <typename T>
struct edge{
    int from, to;
    T cost;
    edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost){}
    bool operator < (const edge & e) const{
        return cost < e.cost;
    }
};

/*
    sからたどりつける負の閉路を検出したとき、空の vector を返す
    頂点数 V, 始点 s, 辺の集合 es, INF として LINF を使うとき : 
    vector<ll> dist = BellmanFord(V, s, es, LINF);
*/
template <typename T>
vector<T> BellmanFord(int V, int s, vector<edge<T>> & es, const T INF = 1e9){
    int E = es.size();
    vector<T> dist(V, INF);
    dist[s] = 0;
    for(int i = 0; i < V - 1; i++){
        for(edge<T> & e : es){
            if(dist[e.from] == INF) continue;
            dist[e.to] = min(dist[e.to], dist[e.from] + e.cost);
        }
    }
    for(edge<T> & e : es){
        if(dist[e.from] == INF) continue;
        if(dist[e.from] + e.cost < dist[e.to]) return vector<T>();
    }
    return dist;
}

//グラフ全体をみて、負の閉路が存在するとき true を返す
template <typename T>
bool Find_Negative_Loop(int V, vector<edge<T>> & es){
    vector<T> dist(V, 0);
    for(int i = 0; i < V; i++){
        for(edge<T> & e : es){
            if(dist[e.to] > dist[e.from] + e.cost){
                dist[e.to] = dist[e.from] + e.cost;
                if(i == V - 1) return true;
            }
        }
    }
    return false;
}

bool use1[MAX_N + 1], use2[MAX_N + 1];
vector<int> G1[MAX_N + 1], G2[MAX_N + 2];

void DFS1(int now){
    use1[now] = true;
    REP(i,G1[now].size()){
        if(!use1[G1[now][i]]) DFS1(G1[now][i]);
    }
}

void DFS2(int now){
    use2[now] = true;
    REP(i,G2[now].size()){
        if(!use2[G2[now][i]]) DFS2(G2[now][i]);
    }
}

signed main(){
    int n,m;
    ll p;
    cin >> n >> m >> p;
    int a[m],b[m];
    ll c[m];
    REP(i,m){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
        G1[a[i]].emplace_back(b[i]);
        G2[b[i]].emplace_back(a[i]);
    }
    DFS1(0);
    DFS2(n - 1);
    vector<edge<ll>> es;
    REP(i,m){
        if(use1[a[i]] && use1[b[i]] && use2[b[i]] && use2[b[i]]){
            es.emplace_back(a[i], b[i], -(c[i] - p));
        }
    }
    vector<ll> dist = BellmanFord(n, 0, es, LINF);
    if(dist.size() == 0){
        cout << -1 << endl;
    }else{
        if(-dist[n - 1] < 0) cout << 0 << endl;
        else cout << -dist[n - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 896
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  string w;
  cin >> w;
  vector<int> alpha(26,0);
  for(int i=0;i<w.size();i++) ++alpha.at(w.at(i)-'a');

  for(int i=0;i<26;i++){
    if(alpha.at(i)%2==1){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
class ModInt {
  static int MOD;
  long long x;

 public:
  static void mod(int m) { MOD = m; }

  ModInt(long long v = 0) : x(v % MOD) {
    if (x < 0) x += MOD;
  }

  ModInt& operator+=(const ModInt& r) {
    x += r.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }

  ModInt& operator-=(const ModInt& r) {
    x -= r.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    x = (x * r.x) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; }
  ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; }
  ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; }
  ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; }
  bool operator==(const ModInt& r) const { return x == r.x; }
  bool operator!=(const ModInt& r) const { return x != r.x; }

  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(long long n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.x; }

  friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; }

  int getMod() { return MOD; }

  long long val() { return x; }
};
int ModInt::MOD = 1000000007;

using mint = ModInt;
int N, M;
vector<int> S, T;
int main() {
  cin >> N >> M;
  S.resize(N), T.resize(M);
  rep(i, N) cin >> S[i];
  rep(i, M) cin >> T[i];

  vector<vector<mint>> dp(N + 1, vector<mint>(M + 1, 0));

  rep(i, N) rep(j, M) {
    dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j];
    if (S[i] == T[j]) dp[i + 1][j + 1] += dp[i][j] + 1;
  }

  cout << dp[N][M] + 1 << endl;

  return 0;
}


Measured memory_bytes: 31616
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2e5;

char s[maxn + 5];
char t[maxn + 5];
char a[maxn + 5];
char b[maxn + 5];
bool flag;

int main(){
	memset(a, '#', sizeof(a));
	memset(b, '#', sizeof(b));
	scanf("%s", s);
	scanf("%s", t);
	int len = strlen(s);
	for(int i = 0; i <= len - 1; i++){
		if(a[s[i] - 'a'] == '#' || a[s[i] - 'a'] == t[i]){
			a[s[i] - 'a'] = t[i];
		}
		else flag = 1;
		if(b[t[i] - 'a'] == '#' || b[t[i] - 'a'] == s[i]){
			b[t[i] - 'a'] = s[i];
		}
		else flag = 1;
		if(flag){
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 1024