akhauriyash/Code-Regression huggingface dataset:
import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))

    ans = 0
    L = sorted(L)

    for i in range(N):
        a = L[i]
        for j in range(i+1, N):
            b = L[j]
            target = a+b

            c = bisect.bisect_left(L, target)
            ans = ans + (c-j-1)

    print (ans)
if __name__ == "__main__":
    main()


Measured memory_bytes: 42476
#include<bits/stdc++.h>
using namespace std;
double p[3001] ;
double dp[3001][3001] ;

double solve(int n,int m){
	if(n < m)
		return 0 ;
	if(m==0)
		return 1 ;
	if(n==0)
		return 0 ;
	if(dp[n][m] != -1)
		return dp[n][m] ;
	double t = solve(n-1,m-1)*p[n] + solve(n-1,m)*(1-p[n]) ;
	return dp[n][m] = t ;
}
int main(){
	int n ;
	cin >> n ;
	p[0] = 0.0 ;
	for(int i=1;i<=n;i++)
		cin >> p[i] ;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			dp[i][j] = -1 ;	
	cout << fixed << setprecision(10) << solve(n,(n/2+1)) << endl ;
}

Measured memory_bytes: 70784
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long int
#define mkp make_pair
#define maxN 100005
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<endl;
#define debug2(a,b) cout<<a<<' '<<b<<endl;
#define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,a,b) for(int i=a;i<b;i++)
#define pi pair<int,int>
#define pii pair<int,pi>
#define mp map<int,int>
#define ump unordered_map<int,int>
#define  vi vector<int>
#define st set<int>
#define mst multiset<int>
#define pq priority_queue
#define mpq priority_queue<int,vector<int>,greater<int> >
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define in cin>>
#define out cout<<
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> orderedSet;
//typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> orderedMSet;
//*p.find_by_order(index) return value at index
//p.order_of_key(key) return index
void printArray(int arr[],int n)
{
   for(int i=0;i<n;i++)cout<<arr[i]<<' ';
}
void printMp(mp m)
{
  mp ::iterator it;
  for(it=m.begin();it!=m.end();it++)cout<<it->first<<' '<<it->second<<endl;
}
void printUmp(ump m)
{
  ump ::iterator it;
  for(it=m.begin();it!=m.end();it++)cout<<it->first<<' '<<it->second<<endl;
}
void printSt(st s)
{
  st ::iterator it;
  for(it=s.begin();it!=s.end();it++)cout<<*it<<' ';
}
void printMst(mst s)
{
  mst ::iterator it;
  for(it=s.begin();it!=s.end();it++)cout<<*it<<' ';
}
void printVec(vector<int>v)
{
for(int i=0;i<v.size();i++)cout<<v[i]<<' ';
}
void printVec2(vector<int>v[],int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<v[i].size();j++)
            cout<<v[i][j]<<' ';
        cout<<endl;
    }
}
 set<pair<int,int>> primeset;
void SieveOfEratosthenes(int n)
{
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
        for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
    for (int p=2; p<=n; p++)
       if (prime[p])
          primeset.insert(mkp(p,1));
}
int32_t main()
{
fastio;
int n;in n;
double sum=0;
rep(i,n){
    double a;in a;
    sum+=((double)1)/a;
}
out ((double) 1)/sum;
 return 0;
}

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

int main() {
    using namespace std;
    string S;
    cin >> S;
    unsigned long N{S.size()};
    [&]{for(unsigned long i{0}; i < N; ++i)if(S[i] != S[i & 1])return;exit(0 & puts("Second"));}();
    vector<unsigned long> cnt(26);
    unsigned long t{0};
    for(const auto& c : S)if(!(cnt[c - 65]++))++t;
    sort(cnt.begin(), cnt.end());
    if(t == 3 && cnt[2] == 1)puts("First");
    else puts((N & 1) ^ (S[0] == S.back()) ? "First" : "Second");
    return 0;
}

Measured memory_bytes: 512
sX, sY, eX, eY = map(int, input().split())
N = int(input())

circles = [(sX, sY, 0)]
for _ in range(N):
    cx, cy, r = map(int, input().split())
    circles.append((cx, cy, r))
circles.append((eX, eY, 0))

edges = [[float('inf')] * (N + 2) for _ in range(N + 2)]

for i, (cx1, cy1, r1) in enumerate(circles):
    for j, (cx2, cy2, r2) in enumerate(circles):
        cDist = ((cx1 - cx2)**2 + (cy1 - cy2)**2)**0.5
        dist = max(0, cDist - r1 - r2)

        edges[i][j] = dist
        edges[j][i] = dist

minDist = [float('inf')] * (N + 2)
minDist[0] = 0
confilm = [False] * (N + 2)

for _ in range(N + 2):
    md = float('inf')
    minNode = -1
    for n in range(N + 2):
        if not confilm[n] and md > minDist[n]:
            minNode = n
            md = minDist[n]
    confilm[minNode] = True
    for to in range(N + 2):
        minDist[to] = min(minDist[to], minDist[minNode] + edges[minNode][to])

print(minDist[-1])


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

int main(){
  double D,T,S,t;
  cin >> D >> T >> S;
  t = D/S;
  if(t <= T){
  cout << "Yes" <<endl;
  }
  else{
  cout << "No" <<endl;
  }
  return 0;
}

Measured memory_bytes: 3700
import java.math.BigDecimal;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = (Integer.parseInt(sc.next()));
		int i;
		for(i = 0; i < n; i++) {
			BigDecimal x1 = new BigDecimal(sc.next());
			BigDecimal y1 = new BigDecimal(sc.next());
			BigDecimal x2 = new BigDecimal(sc.next());
			BigDecimal y2 = new BigDecimal(sc.next());
			BigDecimal x3 = new BigDecimal(sc.next());
			BigDecimal y3 = new BigDecimal(sc.next());
			BigDecimal x4 = new BigDecimal(sc.next());
			BigDecimal y4 = new BigDecimal(sc.next());
			BigDecimal a1, a2;
			if(x2.equals(x1)) {
				a1 =  y2.subtract(y1);
			}else {
				a1 = (y2.subtract(y1)).divide(x2.subtract(x1), 10, BigDecimal.ROUND_HALF_UP);
			}

			if(x4.equals(x3)) {
				a2 = y4.subtract(y3);
			}else {
				a2 = (y4.subtract(y3)).divide(x4.subtract(x3), 10, BigDecimal.ROUND_HALF_UP);
			}
			if(a1.equals(a2)) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}
		sc.close();

	}

}



Measured memory_bytes: 27200
<?php
$A=[];
for($i=97;$i<123;$i++) $A[$i]=0;

while(1){
  $S=trim(fgets(STDIN));
  if(!$S){break;}

  foreach(str_split($S) as $c){
    $n=ord($c);
    if($n<65);
    elseif($n<91) ++$A[$n+32];
    elseif($n<97);
    elseif($n<123) ++$A[$n];
  }
}

for($i=97;$i<123;$i++) echo chr($i),' : ',$A[$i],PHP_EOL;

Measured memory_bytes: 15376
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#include <numeric>
#include <queue>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001001000
#define mod 1000000007
#define pi 3.1415926535
using namespace std;

template<typename T>
struct SegmentTree{
    ll n;
    T ident;
    vector<T> node;
public:
    SegmentTree(vector<T> &v,T ide){
        ll sz = v.size();
        n = 1;
        ident = ide;
        while(n<sz) n*=2;
        node.resize(2*n-1,ident);
        
        //一番下に元配列を代入
        rep(i,sz) node[i+n-1] = v[i];
        
        //子供の小さいほうをとってく
        //ここは問題によって変わる
        mrep(i,n-2) node[i] = product(node[2*i+1],node[2*i+2]);
    }
    
    SegmentTree(ll nn,T ide){
        ll sz = nn;
        n = 1;
        ident = ide;
        while(n<sz) n*=2;
        node.resize(2*n-1,ident);
        
        //一番下に元配列を代入
        //rep(i,sz) node[i+n-1] = inf;
        
        //子供の小さいほうをとってく
        //ここは問題によって変わる
        mrep(i,n-2) node[i] = product(node[2*i+1],node[2*i+2]);
    }
    
    SegmentTree(){}
    
    void update(ll x,T val){
        //一番下にアクセス
        x += (n-1);
        
        node[x] = val;
        while(x>0){
            x = (x-1)/2;
            node[x] = product(node[2*x+1],node[2*x+2]);
        }
    }
    //区間[a,b)を探す
    T get(ll a,ll b,ll k=0,ll l=0,ll r=-1){
        //最初は区間[0,n)
        if(r<0) r=n;
        
        //返しても常に問題ない値を返してね(minならinf、相和なら0)
        if(r <= a || b <= l) return ident;
        
        if(a<=l && r<=b) return node[k];
        
        ll lv = get(a,b,2*k+1,l,(l+r)/2);
        ll rv = get(a,b,2*k+2,(l+r)/2,r);
        return product(lv,rv);
    }
    
    T product(T &a,T &b){
        return a+b;
    }
};



int main(void){
    ll n,q;
    string s;
    cin>>n>>s>>q;
    vector<SegmentTree<ll> > vst(26,SegmentTree<ll>(n,0LL));
    rep(i,n){
        vst[s[i]-'a'].update(i,1);
    }
    rep(i,q){
        ll t;
        cin>>t;
        if(t == 1){
            ll iq;
            char cq;
            cin>>iq>>cq;
            iq--;
            vst[s[iq]-'a'].update(iq,0);
            vst[cq-'a'].update(iq,1);
            s[iq] = cq;
        }
        else{
            ll l,r;
            cin>>l>>r;
            l--;
            ll ans = 0;
            rep(j,26){
                if(vst[j].get(l,r) > 0){
                    ans++;
                }
            }
            cout<<ans<<endl;
        }
    }
}

Measured memory_bytes: 222212
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sidha(i,a,b) for(int i=a;i<b;i++)
#define vi vector<int> 
#define pb push_back

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
	int n,m,p;cin>>n>>m>>p;
	cout<<min({n+m,m+p,n+p})<<endl;
	return 0;
}

Measured memory_bytes: 3636
from sys import stdin


# 最小化問題
def chmin(a,b):
    if a > b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    h_arr = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [float('inf')] * N  # 最小化問題
    dp[0] = 0                # 初期条件
    
    for i in range(0,N):
        dp[i] = chmin(dp[i],dp[i-1]+abs(h_arr[i]-h_arr[i-1]))
        if i > 1:
            dp[i] = chmin(dp[i],dp[i-2]+abs(h_arr[i]-h_arr[i-2]))
    cnt = dp[N-1]
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Measured memory_bytes: 54412
#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int S, W;
    cin >> S >> W;
    // スペース区切りの整数の入力
    if( S>W ){
      cout << "safe";
     }else{
      cout << "unsafe";
    }

    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define F first
#define S second

string s;

signed main(){
	int a,b;
	cin>>a>>b;
	cout<<max(max(a+a-1,b+b-1),max(a+b,a+b))<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  while(a!=0&&b!=0){
    for(int i=0;i<a;i++){
      for(int j=0;j<b;j++){
	if((i==0||i==a-1)||(j==0||j==b-1)){
	  cout<<"#";
	}
	else cout<<".";
      }
      cout<<endl;
    }
    cout<<endl;
    cin>>a>>b;
  }
  return 0;
}

Measured memory_bytes: 3076
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	int list[20000][2];
	bool f[20000];
	bool ff[20000];
	
	int n, m;
	while (scanf("%d %d", &n, &m), n + m){
		memset(f, 0, sizeof(f));
		memset(ff, 0, sizeof(ff));
		
		for (int i = 0; i < m; i++){
			scanf("%d %d", &list[i][0], &list[i][1]);
			
			if (list[i][0] == 1){
				f[list[i][1]] = true;
			}
			else if (list[i][1] == 1){
				f[list[i][0]] = true;
			}
		}
		
		for (int i = 0; i < m; i++){
			if (f[list[i][0]]){
				ff[list[i][1]] = true;
			}
			else if (f[list[i][1]]){
				ff[list[i][0]] = true;
			}
		}
		
		int cnt = 0;
		for (int i = 2; i <= n; i++){
			if (ff[i] || f[i]){
				cnt++;
			}
		}
		
		printf("%d\n", cnt);
	}
	
	return 0;
}

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

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

Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<map>
#include<set>

double w,h,x,y;
using namespace std;

void solve(){
    cout << (w*h)/2.0 << ' ';
    if(x==w/2.0 && y==h/2.0){
        cout << 1 << endl;
    }
    else{
        cout << 0 << endl;
    }
}

int main(){
    cin >> w >> h >> x >> y;
    solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <map>
typedef long long ll;
using namespace std;
const int mod=1e9+7;
const ll inf=(1e14);

ll solve(){
	int n,m,k;
	cin>>n>>m>>k;
	ll a[n+1],b[m+1];
	a[0]=0;b[0]=0;
	for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
	for(int i=1;i<=m;i++) cin>>b[i],b[i]+=b[i-1];
	int x=0,y=m,ans=0;
	while(y>=0){
		while(b[y] > k) y--;
		while(x<=n && a[x]+b[y] <= k) x++;
		ans=max(ans,x-1+y);
		y--;
	}
	return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while(t--) cout<<solve()<<'\n';
    //while(t--) solve(),cout<<'\n';
    return 0;
}


Measured memory_bytes: 6748
tailrec fun gcd(a: Long, b: Long): Long {
    return if (b == 0L) a else gcd(b, a % b)
}

fun lcm(a: Long, b: Long): Long {
    return a * b / gcd(a, b)
}

fun main(args: Array<String>) {
    val (a, b) = readLine()?.split(" ")?.map(String::toLong) ?: return
    println(lcm(a, b))
}


Measured memory_bytes: 37500
#include <stdio.h>

int main(void) {
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    if (a + b > c + d) {
        puts("Left");
    } else if (a + b < c + d) {
        puts("Right");
    } else {
        puts("Balanced");
    }
    return 0;
}

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

using namespace std;
#define int long long
const int N = 1e5 + 10, SGM = 2;
int C[N][2], deg[N], h[N], ts = 0;

void add(string s)
{
    int cur = 0;
    for (int i = 0; i < s.size(); i ++) {
        if (!C[cur][s[i] - '0'])
            C[cur][s[i] - '0'] = ++ts, deg[cur]++, h[ts] = h[cur] + 1;
        cur = C[cur][s[i] - '0'];
    }
}

int32_t main()
{
    int n, L; cin >> n >> L;
    for (int i = 0; i < n; i ++) {
        string s; cin >> s;
        add(s);
    }
    int G = 0;
    queue <int> q;
    q.push(0);
    while (q.size()) {
        int v = q.front(); q.pop();
        int x = L - h[v];
        if (deg[v] == 1) G ^= x&(-x);
        for (int i = 0; i < SGM; i ++) if (C[v][i]) q.push(C[v][i]);
    }
    if (G) cout << "Alice\n";
    else cout << "Bob\n";

    return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+1;
void solve()
{
	ll N,M;
	cin>>N>>M;
	ll a[maxn],sum=0;
	for(ll i=0;i<M;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	if(sum>N) cout<<-1<<"\n";
	else cout<<N-sum<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T=1,p=0;
	//cin>>T;
	do
	{
		solve();
		p++;
	}while(p<T);
	return 0;
}



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

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

    bool check;
    for (int i = 1; i < 10; i++) {
        check = false;
        for (int j = 1; j < 10; j++) {
            if (n == i * j) {
                check = true;
                break;
            }
        }
        if (check == true) break;
    }

    if (check == true) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstring>
using namespace std;
const int M = 5e2 + 10;
int mmp[M][M] , ans[M][M];
int main() {
    int H , W , h , w;
    cin >> H >> W >> h >> w;
    for(int i = 1 ; i <= H ; i++) {
        for(int j = 1 ; j <= W ; j++) {
            ans[i][j] = 1;
        }
    }
    for(int i = 1 ; i <= H ; i++) {
        if(i % h == 0) {
            for(int j = 1 ; j <= W ; j++) {
                if(j % w == 0) {
                    ans[i][j] = -(h * w);
                }
            }
        }
    }
    int count = 0 , cnt = 0;
    for(int i = 1 ; i <= H ; i++) {
        for(int j = 1 ; j <= W ; j++) {
            if(ans[i][j] > 0) count++;
            cnt += ans[i][j];
        }
    }
    if(count - (H * W - count) * (h * w - 1) <= 0 && cnt <= 0) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        int sum = 0;
        for(int i = 1 ; i <= H ; i++) {
            for(int j = 1 ; j <= W ; j++) {
                sum += ans[i][j];
            }
        }
        int num1 = count , num2 = H * W - count;
        int dif = num1 - num2 * (h * w - 1);
        if(sum <= 0) {
            int gg = -sum;
            int ad = gg / dif + 1;
            for(int i = 1 ; i <= H ; i++) {
                for(int j = 1 ; j <= W ; j++) {
                    if(ans[i][j] > 0) ans[i][j] += ad;
                    else ans[i][j] -= ad * (h * w - 1);
                }
            }
        }
        for(int i = 1 ; i <= H ; i++) {
            for(int j = 1 ; j <= W ; j++) {
                cout << ans[i][j] << ' ';
            }
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2304
#include<stdio.h>

const long long MAX = 1e18;
long long a[100001];

int main(){
    int n; scanf("%d", &n);
    int cont = 0;
    for(int i=0; i<n; i++){
        scanf("%lld", &a[i]);
        if(a[i] == 0) cont++;
    }
    

    if(cont>=1){
        printf("0\n");
        return 0;
    }

    long long mult = 1;
    for (int i=0; i<n; i++){
        if(a[i]<=(MAX/mult)){
            mult = mult*a[i]; 
        } else{
            printf("-1\n");
            return 0;
        }
    } printf("%lld\n", mult);

    return 0;
}

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

int asc(const void *a, const void *b);
int desc(const void *a, const void *b);

int main(void) {

  char *S=(char *)calloc(500000,sizeof(int));
  scanf("%s",S);
  long int l=strlen(S);
  //printf("%d\n",l);

  long int i;
  long int *a=(long int *)calloc(l+1,sizeof(long int));
  for(i=0;i<l;i++){
    //printf("%d %c\n",l,S[i]);
    if(S[i]=='<' && (S[i-1]!='>' || i==0)){
      a[i]=-1;
    }
    else if(S[i]=='>' && (S[i+1]=='<' || i==l-1)){
      a[i+1]=-1;  
  	}
  }
  for(i=0;i<l+1;i++){
    if(S[i]=='<'){
      a[i+1]=a[i]+1;  
  	}
  }
  for(i=l-1;i>=0;i--){
    if(S[i]=='>'){
      a[i]=a[i+1]+1;
    }
  }
  
  
   for(i=0;i<l+1;i++){
   //printf("%d %d\n",i,a[i]);
  	}
  
  long int min=10000000;
  for(i=0;i<l+1;i++){
    //printf("%d %d\n",i,a[i]);
  	if(min>a[i])
    {min=a[i];}
   }
  //printf("%d\n",min);
  long int sum=0;
    for(i=0;i<l;i++){
    if(S[i]=='<' && S[i+1]=='>'){
      	a[i+1]=(a[i]>a[i+2]?a[i]+1:a[i+2]+1);
    }
    }
  
  for(i=0;i<l+1;i++){
   //printf("%d %d\n",i,a[i]-min);
    sum+=a[i]-min;
   }
  printf("%ld\n",sum);
  
}

int asc(const void *a, const void *b) {
  return *(int *)a - *(int *)b;
}
int desc(const void *a, const void *b) {
  return *(int *)b - *(int *)a;
}


Measured memory_bytes: 6016
#include<stdio.h>
int main(){
	int i,n,h=0,m=0,s=0;
	scanf("%d",&i);
	while(i/3600){
		h++;
		i-=3600;
	}
	while(i/60){
		m++;
		i-=60;
	}
	printf("%d:%d:%d\n",h,m,i);
} 


Measured memory_bytes: 2760
package main

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

var sc = bufio.NewScanner(os.Stdin)
func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	
	n := scanInt()
	p := make([]int,n)
	for i := 0; i < n; i++ {
		p[i] = scanInt()
	}

	miss := 0
	for i := 0; i < n; i++ {
		if i+1 != p[i] {
			miss++
		}
	}

	if miss == 2 || miss == 0 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 640
import java.util.Scanner;

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

        while(true){
            int n = sc.nextInt();
            int [] array;
            array = new int[n];
            int r = sc.nextInt();
            int i;
            for(i=0;i<n;i++){
                array[i] = n-i;
            }
            if(n == 0 && r == 0){
                break;
            }
            int j;
            for(j=0;j<r;j++){
                int p = sc.nextInt();
                int c = sc.nextInt();
                int [] P;
                P = new int[c+p-1];

                for(i=0;i<p-1;i++){
                    P[i]= array[i];
                }
                for(i=0;i<c;i++){
                    P[i+p-1] = array[i+p-1];
                }
                for(i=0;i<c;i++){
                    array[i] = P[i+p-1];

                }
                for(i=0;i<p-1;i++){
                    array[i+c] = P[i];
                }
            }
            System.out.println(array[0]);
        }

        sc.close();
    }
}


Measured memory_bytes: 37628
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace atCorder_A1222
{
    class Program
    {
        static void Main(string[] args)
        {
            int cnt = int.Parse(Console.ReadLine());

            int gCnt = 0;
            for (int i = 0; i < cnt; i++)
            {
                if(0 == (long.Parse(Console.ReadLine()) % 2))
                {
                    gCnt++;
                }
            }

            string ret = "first";
            if (cnt == gCnt)
            {
                ret = "second";
            }

            Console.WriteLine(ret);
        }
    }
}


Measured memory_bytes: 17232
object Main extends App {
  val in = new java.util.Scanner(System.in)
  val K = in.nextInt
  def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

  val gcds = for {
    a <- 1 to K
    b <- 1 to K
    c <- 1 to K
  } yield gcd(gcd(a, b), c)

  println(gcds.sum)
}

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

#define ll long long
using namespace std;

int main() {
    ll n;
    cin >> n;
    ll N = 0;
    ll p = 0;
    for (ll i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if ( x % 2 == 0) p++;
            else N++;
    }
    if (N % 2 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
INF = 1 << 60
MOD = 10**10 + 1
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class NTT(object):
    def __init__(self, prime, root):
        self._prime = prime
        self._root = root

    def _fmt(self, A, inverse = False):
        N = len(A)
        logN = (N - 1).bit_length()
        prime = self._prime
        base = pow(self._root, (prime - 1) // N * (1 - 2 * inverse) % (prime - 1), prime)
        step = N
        for k in range(logN):
            step >>= 1
            w = pow(base, step, prime)
            wj = 1
            nA = [0] * N
            for j in range(1 << k):
                for i in range(1 << logN - k - 1):
                    s, t = i + j * step, i + j * step + (N >> 1)
                    ps, pt = i + j * step * 2, i + j * step * 2 + step
                    nA[s], nA[t] = (A[ps] + A[pt] * wj) % prime, (A[ps] - A[pt] * wj) % prime
                wj = (wj * w) % prime
            A = nA
        return A

    def convolution(self, f, g):
        N = 1 << (len(f) + len(g) - 2).bit_length()
        prime = self._prime
        Ff, Fg = self._fmt(f + [0] * (N - len(f))), self._fmt(g + [0] * (N - len(g)))
        N_inv = pow(N, prime - 2, prime)
        fg = self._fmt([a * b % prime * N_inv % prime for a, b in zip(Ff, Fg)], inverse = True)
        del fg[len(f) + len(g) - 1:]
        return fg

def Garner(R, M):
    n = len(R)
    M.append(MOD)
    coeffs, consts = [1] * (n + 1), [0] * (n + 1)
    for i in range(n):
        a, b, u, v = coeffs[i], M[i], 1, 0
        while b:
            u, v = v, u - a // b * v
            a, b = b, a - a // b * b
        t = (R[i] - consts[i]) * (u % M[i]) % M[i]
        for j in range(i + 1, n + 1):
            consts[j] = (consts[j] + t * coeffs[j]) % M[j]
            coeffs[j] = coeffs[j] * M[i] % M[j]
    M.pop()
    return consts[-1]

class arbitrary_mod_NTT(object):
    def __init__(self, primes, roots):
        self._ntts = [NTT(prime, root) for prime, root in zip(primes, roots)]
        self._primes = primes

    def convolution(self, f, g):
        res = [0] * (len(f) + len(g) - 1)
        fgs = [ntt.convolution(f, g) for ntt in self._ntts]
        for i in range(len(res)):
            res[i] = Garner([fg[i] for fg in fgs], self._primes)
        return res

def resolve():
    n, m = map(int, input().split())
    f = [0] * (100001)
    for a in map(int, input().split()):
        f[a] += 1
    ff = arbitrary_mod_NTT([167772161, 469762049, 1224736769], [3, 3, 3]).convolution(f, f)

    ans = 0
    n = len(ff)
    for i in range(n - 1, -1, -1):
        add = min(m, ff[i])
        m -= add
        ans += i * add

    print(ans)
resolve()

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

int main(void) {
	int n,q;
	
	while(cin>>n>>q){
		int a[1000]={0};
	    int m=0;
	    int k=0;
	    int max=0;
	    int max_num=0;
	    int count_max=0;
		if(n==0&&q==0){
			break;
		}
		for(int i=0;i<n;i++){
			cin>>m;
			for(int j=0;j<m;j++){
				cin>>k;
		        if(k>max) max=k;
				a[k]++;
			}
		}
		count_max=0;
		
		for(int i=1;i<=max;i++){
			if(a[i]>count_max){
				count_max=a[i];
				max_num=i;
			}
		}
		if(count_max<q) max_num=0;
		cout<<max_num<<endl;	
		
	}
	return 0;
}

Measured memory_bytes: 3060
#include <iostream>
#include <array>

#define MAX 200000

using namespace std;

int main()
{
        int n, i, minv, maxv;
        array< int, MAX > ar;

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


        minv = ar[0];
        maxv = ar[1] - ar[0];
        for ( i = 1 ; i < n ; i++ )
        {
                if ( maxv < ar[i] - minv ) { maxv = ar[i] - minv; }
                if ( minv > ar[i] ) { minv = ar[i]; }
        }
        cout << maxv << endl;

        return 0;
}



Measured memory_bytes: 3884
#include <bits/stdc++.h>
#define rep(i, z, n) for(int i = z; i <= n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

int main(){
  int S,W;
  cin >> S >> W;
  if(S>W){
    cout << "safe" << endl;
  }else{
    cout << "unsafe" << endl;
  }
  return 0;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

ll solve(ll x){
  if(x<=0) return 0;

  ll ans = (x+1)/2%2;

  if(x%2==0) ans ^= x;

  return ans;
}

int main() {
  ll a,b;
  cin >> a >> b;

  ll ansa = solve(a-1);
  ll ansb = solve(b);

  // cout << ansa << " " << ansb << endl;

  cout << (ansa^ansb) << endl;


}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
    int main(){
    int a, b, c, d, e, k;
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    cin >> e;
    cin >> k;
    if(e - a > k)
    cout << ":(" << endl;
    else 
    cout << "Yay!" << endl;
    return 0;
}


Measured memory_bytes: 256
use std::collections::HashMap;
use std::num;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: usize,
        b: usize,
    }
    println!("{}", if a * b % 2 == 0 { "Even" } else { "Odd" });
}


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

int main () {
  int n;
  cin >> n;
  long long sum = 0;
  int a[n];
  int min = -1;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum = sum + a[i];
    if (a[i] % 10 != 0) {
      if (min == -1 || min > a[i]) {
        min = a[i];  
      }  
    }  
  }  
  if (sum % 10 != 0) {
    cout << sum << endl;  
  }
  else {
    if (min == -1) {
      cout << 0 << endl;  
    }  
    else {
      cout << sum - min << endl;  
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rep(i,from,to) for(int i=from; i<to; ++i)
#define REP(i,from,to) for(int i=from; i<=to; ++i)
using namespace std;
template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& v) {
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i] << endl;
	}
	return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
	out << "[";
	size_t last = v.size() - 1;
	for (size_t i = 0; i < v.size(); ++i) {
		out << v[i];
		if (i != last) {
			out << ",";
		}
	}
	out << "]";
	return out;
}

int a, b;
int gcd(int x, int y) { //x>y
	if (x < y) {
		swap(x, y);
	}
	if (y == 0) {
		return x;
	} else {
		return gcd(y, x % y);
	}
}
void solve() {
	cin >> a >> b;
	cout << gcd(a, b) << endl;
}

int main() {
	solve();
}

Measured memory_bytes: 3088
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[100005];
int b[100005];

bool cmp(int x,int y){
	return a[x]<a[y];
}

int main()

{
	ios::sync_with_stdio(false);
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i];

	for (int i=1;i<=n;i++)
		b[i]=i;

	sort(b+1,b+1+n,cmp);
	for (int i=1;i<=n;i++)
		cout<<b[i]<<" ";
	cout<<endl;
	return 0;
}

Measured memory_bytes: 1664
#include <cstdio>

using namespace std;

int n;
int a[100];

int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int cnt = 0;
    int prev = 0;
    for (int i = 0; i < n; i++) {
        if (prev != a[i]) {
            prev = a[i];
            continue;
        }
        cnt++;
        prev = 0;
    }
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb push_back
#define mp make_pair
#define nt _ll128
#define ld long double
long double PI =3.14159265358979323846;
using ll = long long;



const ll modo=1e9+7;
const ll inf=1e17;
const ll ms=(1e5)+5;

int ar[600][600];

int ans[ms][4];

int main() {
    idfc;

    int r, c;
    cin >> r >> c;
    int i, j;

    for (i = 1; i <= r; i++)for (j = 1; j <= c; j++)cin >> ar[i][j];

    int aa=0;
    for (i = 1; i <= r; i++) {
        for (j = 1; j <= c; j++) {
            if (ar[i][j] % 2) {
                if ((j + 1) <= c) {
                    aa++;
                    ans[aa][0]=i;
                    ans[aa][1]=j;
                    ans[aa][2]=i;
                    ans[aa][3]=j+1;
                    ar[i][j + 1]++;
                    ar[i][j]--;
                } else if ((i + 1) <= r) {
                    aa++;
                    ans[aa][0]=i;
                    ans[aa][1]=j;
                    ans[aa][2]=i+1;
                    ans[aa][3]=j;
                    ar[i + 1][j]++;
                    ar[i][j]--;
                }
            }
        }
    }
    cout<<aa<<"\n";

    for(i=1;i<=aa;i++)
    {
        cout<<ans[i][0]<<" "<<ans[i][1]<<" "<<ans[i][2]<<" "<<ans[i][3]<<"\n";
    }


    return 0;
}

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

int main()
{
	string S;
	int K;

	vector < string > vec;
	
	cin >> S >> K;

	for ( int i = 0; i < S.size(); i++ ) {
		for ( int j = 1; i + j <= S.size() && j <= K; j++ ) {
			vec.push_back(S.substr(i, j));
		}
	}
	sort(begin(vec), end(vec));	
	vec.erase(unique(begin(vec), end(vec)), end(vec));

	cout << vec[K - 1] << endl;

	return (0);
}


Measured memory_bytes: 1660
import Data.IntMap ((!))
import qualified Data.IntMap.Strict as M
import Data.List
import Data.Maybe
import Control.Applicative

untilFix f x = if f x == x then x else untilFix f (f x)

main = do
 [n,q] <- map read . words <$> getLine
 cxys <- map ((\[c,x,y]->(c,(x,y))) . map read . words) . lines <$> getContents
 mapM_ print (uft n q cxys)

uft :: Int -> Int -> [(Int,(Int,Int))] -> [Int]
uft n q = reverse . fst . foldl' process ([],(M.fromDistinctAscList (zip [0..n-1] [0..])))

process (lg,m) (c,(x,y))
 | c==0 = (lg, M.insert (max x y) v1 (M.insert v2 v1 m))
 | c==1 = ((if v1==v2 then 1 else 0) : lg, m)
 where
  v1 = untilFix (m!) (min x y)
  v2 = untilFix (m!) (max x y)

Measured memory_bytes: 94208
#include <stdio.h>
#include<string.h>



int main(void){
    
    char s[200];
    char p[100];
    char ring[200];
    
    scanf("%s",s);
    scanf("%s",p);
    strcpy(ring,s);
    strcat(ring,s);
    
   // printf("%s\n",ring);
    
    if(strstr(ring, p)){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    
    return 0;
}

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

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

int A,B,C,D,E,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D>>E>>K;
	if(E-A>K) cout<<":("<<endl;
	else cout<<"Yay!"<<endl;
	
}


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


Measured memory_bytes: 256
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  998244353ll
using namespace std;
ll ans=1;
int n,cnt[10];
char c[300005];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*3;++i)scanf(" %c",c+i);
    for(int i=1;i<=n*3;++i){
        int k=0;
        if(c[i]=='R')k=1;
        else if(c[i]=='G')k=2;
        bool ok=0;
        for(int _=6;_>0;--_){
            if(_&(1<<k)) continue;
            if(!cnt[_]) continue;
            ans=ans*cnt[_]%orz;
            --cnt[_];
            ++cnt[_^(1<<k)];
            ok=1;
            break;
        }
        if(!ok)++cnt[1<<k];
    }
    for(int i=1;i<=n;++i)ans=ans*i%orz;
    printf("%I64d\n",ans);
    //system("pause");
    return 0;
}


Measured memory_bytes: 512
// https://atcoder.jp/contests/abc151/tasks/abc151_f
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)

// https://kmjp.hatenablog.jp/entry/2020/01/13/1030

void solve() {
    int N;
    cin >> N;
    vector<complex<double>> v;
    REP(i, N) {
        double x, y;
        cin >> x >> y;
        v.emplace_back(x, y);
    }
    double ret = 1e9;
    const auto hoge = [&](complex<double> a) {
        double r = 0;
        for (auto &x : v) {
            r = max(r, abs(x - a));
        }
        ret = min(ret, r);
    };

    REP(z, N) REP(y, z) {
        // 2点間の中心からの距離最大値で更新
        // double rx = (v[y].real() + v[z].real()) * 0.5;
        // double ry = (v[y].imag() + v[z].imag()) * 0.5;
        hoge((v[y] + v[z]) * 0.5);

        // 3点を頂点とする三角形の外心からの距離最大値で更新
        REP(x, y) {
            double a = abs(v[y] - v[z]);
            double b = abs(v[z] - v[x]);
            double c = abs(v[x] - v[y]);

            // 三角形の最長の辺 = それ以外の2辺の和なら三角形が作れない
            if (abs(a + b - c) < 1e-9)
                continue;
            if (abs(a + c - b) < 1e-9)
                continue;
            if (abs(c + b - a) < 1e-9)
                continue;

            // 外心の中心座標を求める
            double rx = (a * a * (b * b + c * c - a * a) * v[x].real() +
                         b * b * (a * a + c * c - b * b) * v[y].real() +
                         c * c * (b * b + a * a - c * c) * v[z].real()) /
                        (a * a * (b * b + c * c - a * a) +
                         b * b * (a * a + c * c - b * b) +
                         c * c * (b * b + a * a - c * c));
            double ry = (a * a * (b * b + c * c - a * a) * v[x].imag() +
                         b * b * (a * a + c * c - b * b) * v[y].imag() +
                         c * c * (b * b + a * a - c * c) * v[z].imag()) /
                        (a * a * (b * b + c * c - a * a) +
                         b * b * (a * a + c * c - b * b) +
                         c * c * (b * b + a * a - c * c));
            hoge({rx, ry});
        }
    }
    cout << fixed << setprecision(12) << ret << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 3816
/*Knapsack problem
Input:
N W
w1 v1
w2 v2
.
.
.
wn vn 

Output: print ma possible sum of the values if time that knapsack of capacity W can contain.
*/

#include<bits/stdc++.h>
using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 

const long long MOD=1e9+7;
using ll=long long;

void add_self(int &a, int b) {
	a += b;
	if(a >= MOD) {
		a -= MOD;
	}
}

void sub_self(int &a, int b) {
	a -= b;
	if(a<=0) {
		a += MOD;
	}
}

int main(){
	int N, K;
	cin >> 	N >> K;
	vector<int> dp(K + 1);//0-K candies   dp[i] = count when i candies used
	dp[0] = 1;
	for(int child = 0; child < N; ++child) {
		int up_to;
		cin >> up_to;
		vector<int> fake(K+1);
	 	for(int used =  K; used >= 0; --used) {
	 		int l = used + 1;
	 		int r = used + min(up_to, K - used);
	 		if(l <= r) {
	 			add_self(fake[l], dp[used]);
	 			if(r+1 <= K) {
	 				sub_self(fake[r+1], dp[used]);
	 			}
	 		}
	 	}
	 	int prefix_sum = 0;
	 	for(int i = 0; i <= K; ++i) {
	 		add_self(prefix_sum, fake[i]);
	 		add_self(dp[i], prefix_sum);
	 	}
	 }
	printf("%d\n", dp[K]);
}

Measured memory_bytes: 1024
/*
 * atcoder/dp_3rd/n.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const ll INF = 100000000000000000;
const int MAX = 410;
ll N;
vector<ll> A;

/*
 * dp[l][r] := [l:r)までのスライムを合体させる最小コスト
 * dp[l][r] = dp[l][r] = A[l] if len == 1
 * dp[l][r] = sum(A[l:r]) + min([dp[l][k] + dp[k][r] for k in [l+1:r)]) if len >= 2
 */
ll dp[MAX][MAX] = {0};
ll acc[MAX] = {0};

void input() {
  cin >> N;
  ll a;
  acc[0] = 0;
  loop(n,0,N) {
    cin >> a;
    A.push_back(a);
    acc[n+1] = acc[n] + A[n];
  }
}

void solve() {
  for (int len=1; len<=N; len++) {
    for (int l=0; l+len<=N; l++) {
      if (len==1) { continue; }
      int r = l+len;
      ll self = acc[r] - acc[l];
      ll child = INF;
      for (int k=l+1; k<r; k++) {
        chmin(child, dp[l][k] + dp[k][r]);
      }
      dp[l][r] = self + child;
    }
  }
  cout << dp[0][N] << endl;
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
#define rep(i, n) for(int i=0;i<(n);i++)
#define all(v) v.begin(), v.end()
#define MOD 1e7
const long long INF = 1LL<<60;

void fast() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int main() {
    fast();
    string n;
  	cin>>n;
    int s=0;  
    for(int i=0;i<n.size();i++)
        s+= n[i]-'0';
    if(s%9 == 0)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 3748
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

const int lim = 100000 + 100;

int N;
vec<int, 2> G;

ll MOD;

ll dp[lim], ans[lim];
vector<ll> dp2[lim];

void dfs(int v, int p = -1) {
  dp[v] = 1;
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i];
    if (u == p) {
      continue;
    }
    dfs(u, v);
    dp[v] = dp[v] * (1 + dp[u]) % MOD;
  }
}

void dfs2(int v, int p = -1, int vi = -1) {
  dp2[v].clear();
  dp2[v].resize(G[v].size(), 0);
  ll pre = 1;
  if (p != -1) {
    pre = (dp2[p][vi] + 1) % MOD;
  }
  vector<ll> f(G[v].size(), 1);
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i];
    if (u == p) {
      continue;
    }
    f[i] = (1 + dp[u]) % MOD;
  }
  vector<ll> L(G[v].size() + 1, 1), R(G[v].size() + 1, 1);
  for (int i = 0; i < G[v].size(); i++) L[i + 1] = L[i] * f[i] % MOD;
  for (int i = G[v].size() - 1; i >= 0; i--) R[i] = R[i + 1] * f[i] % MOD;
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i];
    if (u == p) {
      continue;
    }
    dp2[v][i] = pre * L[i] % MOD * R[i + 1] % MOD;
    dfs2(u, v, i);
  }
  ans[v] = dp[v] * pre % MOD;
}

int main() {
  while (cin >> N >> MOD) {
    G.clear();
    G.resize(N);
    for (int i = 0; i < N - 1; i++) {
      int x, y;
      cin >> x >> y;
      --x;
      --y;
      G[x].push_back(y);
      G[y].push_back(x);
    }
    dfs(0);
    dfs2(0);
    for (int v = 0; v < N; v++) cout << ans[v] << endl;
  }
  return 0;
}


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

int main() {
	char c;
	cin >> c;

	if (c == 'a' || c == 'e' || c == 'i' || c == 'u' || c == 'o') {
		cout << "vowel" << endl;
	}
	else {
		cout << "consonant" << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;

int main() {
	string N;
	cin >> N;
	if(N=="SUN"){
      cout << 7 << endl;
    }
  else if(N=="MON"){
    cout << 6 << endl;
  }
  else if(N=="TUE"){
    cout << 5 << endl;
  }
  else if(N=="WED"){
    cout << 4 << endl;
  }
  else if(N=="THU"){
    cout << 3 << endl;
  }
  else if(N=="FRI"){
    cout << 2 << endl;
  }
  else{
    cout << 1 << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

namespace mp = boost::multiprecision;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

string str;

signed main()
{
  const string ans = "keyence";
  cin >> str;
  if(str == ans) {
    cout << "YES" << endl;
    return 0;
  }

  REP(i,str.size()) {
    REP(k,str.size()-i+1) {
      string substr = str;
      substr.erase(i,k);
      if(substr == ans) {
        cout << "YES" << endl;
        return 0;
      }
    }
  }

  cout << "NO" << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <functional>
#include <iostream>
#define  pb push_back
#define  xx first
#define  yy second
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;
char a[1001][1001];
 int main(){

    string s,t,u;
    int a, b;
    cin >> s >> t;
    cin >>a >>b;
    cin >> u;
    if(s==u) a--;
    else if(u==t) b--;
    cout << a << " " << b << '\n';


    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	string s[3];
	for (int i = 0; i < 3; i++) cin >> s[i];
	int idx[3] = {};
	int turn = 0;
	while (1) {
		if (idx[turn] == s[turn].size()) {
			printf("%c\n", 'A' + turn);
			return 0;
		}
		int nturn = s[turn][idx[turn]] - 'a';
		idx[turn]++;
		turn = nturn;
	}
}

Measured memory_bytes: 256
H = int(input())
#N,K,M= map(int,input().split())
#A =list(map(int,input().split()))
#L = [list(map(str,input().split())) for i in range(N)]
h = H
count = 0
while h:
    h = h//2
    count += 1

print(2**count-1)


Measured memory_bytes: 2940