akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

const int N=1e5+50; 

int m,ans,n,sum[N],dep[N],prt[N],X,Y;
vector<int> g[N];

void dfs(int v,int p,int c){
	sum[v]=c;
	prt[v]=p; 
	dep[v]=dep[p]+1; 
	for(int d:g[v])if(d!=p){
		if(dep[d])X=v,Y=d;
		else{
			dfs(d,v,-c); 
			sum[v]+=sum[d];
		}
	}
}

int lca(int u,int v){
	while(u!=v){
		if(dep[u]>dep[v])u=prt[u];
		else v=prt[v];
	}
	return u;
}

void solveEven(){
	if(sum[1]!=0){
		puts("-1"); 
		exit(0); 
	}
	int L=lca(X,Y);
	vector<int> a;
	for(;X!=L;X=prt[X])a.pb(sum[X]),sum[X]=0;
	for(;Y!=L;Y=prt[Y])a.pb(sum[Y]),sum[Y]=0;
	a.pb(0); 
	nth_element(a.begin(),a.begin()+a.size()/2,a.end()); 
	int mid=a[a.size()/2];
	for(int x:a)ans+=abs(x-mid);
	rep(i,1,n)ans+=abs(sum[i]); 
}

void solveOdd(){
	//printf("Solve Odd\n");
	if(sum[1]%2!=0){
		puts("-1"); 
		exit(0); 
	}
	int k=-sum[1]/2;
	ans+=abs(k);
	for(;X;X=prt[X])sum[X]+=k;
	for(;Y;Y=prt[Y])sum[Y]+=k;
	rep(i,1,n)ans+=abs(sum[i]);
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	//freopen("dat.in","r",stdin);
	//freopen("my.out","w",stdout);
#endif
	read(n),read(m);
	rep(i,1,m){
		int u,v;
		read(u),read(v); 
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,0,1);
	if(m==n-1){
		if(sum[1]!=0){
			puts("-1"); 
			return 0; 
		}
		rep(i,1,n)ans+=abs(sum[i]); 
	}else{
		if(abs(dep[X]-dep[Y])&1)solveEven(); 
		else solveOdd();
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 15356
use text_io::*;
use std::collections::*;
use std::process::exit;

fn main() {
    let mut n:usize = read!();
    let mut v:Vec<usize> = Vec::new();
    let mut ans:usize = 0;
    let mut sum:usize = 0;
    for i in 0..n {
        let a:usize = read!();
        v.push(a);
    }
    for i in 0..n-1 {
        if v[i]>=v[i+1] {
            sum+=1;
        }
        else {
            sum=0;
        }
        if ans<sum {
            ans=sum;
        }
    }
    println!("{}",ans);
}

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

int num[1];
int main(){
	scanf("%d",num);
	int a = num[0] / 100;
	int b = num[0] - a*100;
	if(1 <= a && a <= 12)
	{
		if(1 <= b && b <= 12)
		{
			cout << "AMBIGUOUS" << "\n";
		}
		else
		{
			cout << "MMYY" << "\n";
		}
	}
	else
	{
		if(1 <= b && b <= 12)
		{
			cout << "YYMM" << "\n";
		}
		else
		{
			cout << "NA" << "\n";
		}
	}
	return 0;
}


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

using namespace std;

int a[4];
bitset<4> mark;

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

	int n, m, s, c;
	cin >> n >> m;

	if (n == 1) {
		for (int i = 0; i < m; ++i) {
			cin >> s >> c;
			s--;

			if (mark[0] && c != a[0]) {
				cout << "-1\n";
				return 0;
			}

			mark[0] = true;
			a[0] = c;
		}

		if (!mark[0])
			cout << 0 << '\n';
		else
			cout << a[0] << '\n';

	} else if (n == 2) {
			for (int i = 0; i < m; ++i) {
				cin >> s >> c;
				s--;

				if (mark[s] && c != a[s]) {
					cout << "-1\n";
					return 0;
				}

				mark[s] = true;
				a[s] = c;
		}

		if (!mark[1])
			a[1] = 0;
		if (!mark[0])
			a[0] = 1;

	if (a[0] == 0)
		cout << -1 << '\n';
	else	
		cout << a[0] << a[1] << '\n';

	} else {
				for (int i = 0; i < m; ++i) {
			cin >> s >> c;
			s--;

			if (mark[s] && c != a[s]) {
				cout << "-1\n";
				return 0;
			}

			mark[s] = true;
			a[s] = c;
		}

				if (!mark[2])
					a[2] = 0;
				if (!mark[1])
					a[1] = 0;
				if (!mark[0])
					a[0] = 1;

				if (a[0] == 0)
					cout << -1 << '\n';
				else
					cout << a[0] << a[1] << a[2] << '\n';

	}

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, start, n) for (int i = (int)(start); i < (int)(n); ++i)
void search(vector<vector<int> > &G, int *color, int s, int id)
{
    color[s] = id; //sは訪問済み
    stack<int> q;
    q.push(s);
    while (q.empty() == false)
    {
        int p = q.top();
        q.pop();
        rep(i, 0, G[p].size())
        {
            int new_p = G[p][i];
            if (color[new_p] == 0)
            {
                color[new_p] = id;
                q.push(new_p);
            }
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int> > G(n, vector<int>(0));
    int color[n] = {};
    int s, t;
    rep(i, 0, m)
    {
        scanf("%d %d", &s, &t);
        G[s].push_back(t);
        G[t].push_back(s);
    }
    int id(0);
    rep(i, 0, n)
    {
        if (color[i] == 0)
        {
            search(G, color, i, ++id);
        }
    }
    int q;
    cin >> q;
    rep(i, 0, q)
    {
        scanf("%d %d", &s, &t);
        if (color[s] == color[t])
            printf("yes\n");
        else
            printf("no\n");
    }
}


Measured memory_bytes: 8696
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc126_d

from collections import namedtuple
import sys

sys.setrecursionlimit(10**5)

DistFrom = namedtuple('DistFrom', ['f', 'dist'])

def main():
    # Input
    n, = [int(s) for s in input().split()]
    fs = [[int(s) for s in input().split()] for _ in range(n-1)]
    # Get ans
    gs = [None] * n
    for i in range(n):
        gs[i] = list()
    for x, y, d in fs:
        x -= 1
        y -= 1
        d = d%2
        gs[x].append(DistFrom(y, d))
        gs[y].append(DistFrom(x, d))
    distlist = [None] * n
    def dfs(cur, dist):
        if distlist[cur] != None:
            return
        distlist[cur] = dist
        for i, d in gs[cur]:
            dfs(i, dist^d)
    dfs(0, 0)
    # Output
    for d in distlist:
        print(d)

if __name__ == '__main__':
    main()


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

int tree[100010];
int n;
//BIT
int sum(int k){
    int s=0;
    while(k<=n){
        s+=tree[k];
        k+=(k&-k);
    }
    return s;
}
    
void add(int k, int x){
    while(k>0){
        tree[k]+=x;
        k-=(k&-k);
    }
}

int main(void){
    int q, a, s, t, x;
    cin >> n >> q;
    while(q--){
        cin >> a;
        if(a==0){
            cin >> s >> t >> x;
            add(t, x);
            add(s-1, -x);
        }else{
            cin >> s;
            cout << sum(s) << "\n";
        }
    }
    return 0;
    
}



Measured memory_bytes: 3452
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int
main ()
{
  int a,b,c,x=0;
  cin >> a >> b >> c;
  if(a+b>= c){
      cout << c+b << endl;

  }
  else if(a+b<c){
      x= a+b+b+1;
     cout <<x << endl;


  }
  
}

Measured memory_bytes: 256
h, w = map(int, input().split())
S = [input() for i in range(h)]


picture = []
diff = [-1, 1]

for i_h in range(h):
    row = ''
    for i_w in range(w):
        can_draw = False
        if S[i_h][i_w] == '.': row = row + '.';continue
        else:
            for dh in diff:
                if (i_h+dh<0) or (i_h+dh>h-1):continue
                if S[i_h+dh][i_w] == '#':
                    can_draw = True
            for dw in diff:
                if (i_w+dw<0) or (i_w+dw>w-1):continue
                if S[i_h][i_w+dw] == '#':
                    can_draw = True
                    
        if can_draw:
            row = row + '#'
        else:
            row = row + '.'
    picture.append(row)
    
if picture == S:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#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(void){
  int N;
  cin >> N;
  int l[N], r[N];
  rep(i,N) cin >> l[i] >> r[i];

  int sum = 0;
  rep(i,N){
    sum += r[i] - l[i] + 1;
  }
  cout << sum << endl;
}


Measured memory_bytes: 3536
cards=[[False for j in range(13)]for i in range(4)]
pattern=["S","H","C","D"]
n=int(input())
for elem in range(n):
    ch,rank=input().split()
    rank=int(rank)
    cards[pattern.index(ch)][rank-1]=True

for i in range(4):
    for j in range(13):
        if cards[i][j]==False:
            print(pattern[i],j+1)


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

const int MXN = 3000;
int n, ne;
long double pro[MXN];
long double ans = 0.0;

long double chance[MXN][MXN];

long double get(int done, int got) {
	if (chance[done][got] != -1) return chance[done][got];
	if (done == 0) {
		if (got == 0) return chance[done][got] = 1.0;
		return chance[done][got] = 0.0;
	}
	if (got > done) return chance[done][got] = 0.0;
	
	if (got == 0) return chance[done][got] = get(done-1, got) * (1-pro[done-1]);
	return chance[done][got] = get(done-1, got-1) * pro[done-1] + get(done-1, got) * (1-pro[done-1]);
}

int main() {
	
	cin >> n;
	ne = n - (n / 2);
	for (int i=0; i<n; i++) cin >> pro[i];
	
	for (int i=0; i<MXN; i++) for (int j=0; j<MXN; j++) chance[i][j] = -1;
	
	long double ch = 0;
	for (int i=0; i<=n; i++) {
		if (i * 2 > n) {
			ch += get(n, i);
			// cout << get(n, i) << endl;
		}
	}
	cout << setprecision(10) << ch << endl;
	
}


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

void maxself(ll &a, ll b)
{
    a = max(a, b);
}

void solveTLE(vector<int> &beauty, vector<int> &h)
{
    int n = h.size();
    vector<ll> dp(n);
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        dp[i] = beauty[i];
        for (int j = 0; j < i; j++)
        {
            if (h[i] > h[j] && dp[j] + beauty[i] > dp[i])
                dp[i] = dp[j] + beauty[i];
        }
        maxself(ans, dp[i]);
    }
}

const int maxn = 2e5 + 11;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> h(n);
    vector<ll> beauty(n);
    for (int &x : h)
    {
        scanf("%d", &x);
    }

    for (ll &x : beauty)
    {
        scanf("%lld", &x);
    }

    int base = 1;
    while (base <= n)
    {
        base *= 2;
    }
    vector<ll> tree(2 * base);
    //to find the maximal beauty sum of flowers such h[i] <= h[j]
    //height is monotonically increasing
    ll ans = 0;
    vector<ll> dp(n + 1);
    //dp[i] => stores the max sum of flowers such that last element was at height i

    for (int flower = 0; flower < n; flower++)
    {
        //for flower x , i want to know the max dp[i] in range[0,h[flower]-1]
        ll best = 0;
        int x = h[flower] + base;
        while (x > 1)
        {
            if (x & 1)
            {
                maxself(best, tree[x - 1]);
            }
            x >>= 1;
        }
        dp[h[flower]] = best + beauty[flower];
        for (int i = base + h[flower]; i >= 1; i >>= 1)
        {
            maxself(tree[i], dp[h[flower]]);
        }
        // for (int i = 0; i < h[flower]; i++){
        //     maxself(dp[h[flower]], dp[i] + beauty[flower]);
        // }
    }

    for (int flower = 0; flower < n; flower++)
    {
        maxself(ans, dp[h[flower]]);
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 8320
#include <stdio.h>

int main(){
    int i,k,j,n,a,num;
    int data[205][3];
    int sum[205] = {};
    scanf("%d",&n);
    for(k = 0;k<n;k++){
        for(i = 0;i<3;i++){
            scanf("%d",&data[k][i]);
        }
    }
    for(i = 0;i<3;i++){
        for(j = 0;j<n;j++){
            a = j;
            num = data[a][i];
            for(k = j+1;k<n;k++){
                if(data[k][i] == num){
                    data[k][i] = 0;
                    data[a][i] = 0;
                }
            }
        }
    }
    for(k = 0;k<n;k++){
        for(i = 0;i<3;i++){
            sum[k] = sum[k] + data[k][i];
        }
    }
    for(k = 0;k<n;k++){
        printf("%d\n",sum[k]);
    }
    return 0;
}

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

const int maxn = 60, P = 1000000007;
int n, f[maxn][3][3];
char s[2][maxn];

int main() {
    scanf("%d %s %s", &n, s[0] + 1, s[1] + 1);
    if (s[0][1] == s[1][1]) {
        f[1][0][0] = f[1][1][1] = f[1][2][2] = 1;
    } else {
        f[1][0][1] = f[1][0][2] = 1;
        f[1][1][0] = f[1][1][2] = 1;
        f[1][2][0] = f[1][2][1] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int c1 = 0; c1 < 3; c1++) {
            for (int c2 = 0; c2 < 3; c2++) if (f[i - 1][c1][c2]) {
                for (int c3 = 0; c3 < 3; c3++) {
                    for (int c4 = 0; c4 < 3; c4++) {
                        if (s[0][i - 1] == s[0][i] && c1 ^ c3) continue;
                        if (s[0][i - 1] ^ s[0][i] && c1 == c3) continue;
                        if (s[1][i - 1] == s[1][i] && c2 ^ c4) continue;
                        if (s[1][i - 1] ^ s[1][i] && c2 == c4) continue;
                        if (s[0][i] == s[1][i] && c3 ^ c4) continue;
                        if (s[0][i] ^ s[1][i] && c3 == c4) continue;
                        (f[i][c3][c4] += f[i - 1][c1][c2]) %= P;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            (ans += f[n][i][j]) %= P;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 3832
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        List<Rectangle> data = read();
        new Main().solve(data);
    }

    static Comparator<Rectangle> comparator = (Rectangle o1, Rectangle o2) -> {
        if (o1.v() == o2.v()) {
            return o2.h - o1.h;
        }
        return o1.v() - o2.v();
    };

    static List<Rectangle> list = new ArrayList<>();
    static {
        for (int i = 1; i < 150; i++) {
            for (int j = 1; j < i; j++) {
                list.add(new Rectangle(j, i));
            }
        }
        list.sort(comparator);
    }

    void solve(List<Rectangle> list) {
        for(Rectangle rec: list) {
            int i = this.list.indexOf(rec);
            Rectangle next = this.list.get(i + 1);
            System.out.println(next.toString());
        }
    }

    static class Rectangle {
        final int w;
        final int h;

        public Rectangle(int w, int h) {
            this.w = w;
            this.h = h;
        }

        public int v() {
            return (this.w * this.w) + (this.h * this.h);
        }

        @Override
        public boolean equals(Object obj) {
            Rectangle rec = (Rectangle) obj;
            return rec.w == this.w && rec.h == this.h;
        }

        @Override
        public int hashCode() {
            return v() * 150 + h;
        }

        @Override
        public String toString() {
            return String.valueOf(this.w) + " " + String.valueOf(this.h);
        }
    }

    static List<Rectangle> read() {
        Scanner sc = new Scanner(System.in);
        List<Rectangle> list = new ArrayList<>();

        while (true) {
            Rectangle req = readLine(sc.nextLine());
            if (req == null) {
                break;
            } else {
                list.add(req);
            }
        }
        sc.close();

        return list;
    }

    static Rectangle readLine(String line) {
        String[] split = line.split(" ");
        int w = Integer.parseInt(split[0]);
        int h = Integer.parseInt(split[1]);
        if (w == 0 && h == 0) {
            return null;
        } else {
            return new Rectangle(w, h);
        }
    }


}



Measured memory_bytes: 32848
#include<iostream>
#include<algorithm>

using namespace std;

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

	for (int i = 0; i < N; i++){
		int x,y,b,p;
		cin >> x >> y >> b >> p ;
	
		int futsu = x * b + y * p;
		int oome = ( x * 5 + y * 2 + x * max ( b - 5 , 0 ) + y * max ( p - 2 , 0) ) * 8 / 10;
		

		
		if (b >= 5 && p >= 2){
			cout << futsu *8 / 10 <<endl;
		}else if(oome < futsu){
			cout << oome  <<endl;
		}else{
			cout << futsu << endl;
		}
	
	
	}

	return 0;
}

Measured memory_bytes: 1164
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String T = sc.next();
    char[]ss = S.toCharArray();
    char[]tt = T.toCharArray();

    int cou = 0;
    for(int i=0; i<S.length(); i++){
        if(ss[i]!=tt[i]){
           cou++;
        }
}
	System.out.println(cou);
      }
}


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

int main() {
  int n;
  cin >> n;
  vector<int> b(n-1);
  rep(i,n-1) cin >> b[i];
  vector<int> a(n);
  a[0] = b[0];
  for (int i = 1; i <= n-2; i++) {
    a[i] = min(b[i],b[i-1]);
  }
  a[n-1] = b[n-2];
  int ans = 0;
  rep(i,n) ans += a[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

typedef long long ll;

void solver_main()
{
	int n;
	double sum = 0;
	cin >> n;
	vector<double> v(n);
	for (int i = 0; i < v.size(); i++) {
		cin >> v[i];
	}	
	sort(v.begin(), v.end());
	sum = v[0];
	for (int i = 1; i < v.size(); i++) {
		sum = (sum + v[i]) / 2;
	}
	cout << sum << endl;
}

int main(void)
{
	solver_main();
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int W,H,x,y,r;
    scanf("%d %d %d %d %d\n",&W,&H,&x,&y,&r);
    if (x+r<=W&&y+r<=H&&r<=x&&r<=y)
    puts("Yes");
    else
    puts("No");

    return 0;
}


Measured memory_bytes: 2044
w, h ,n = map(int, input().split())
sq = list(list(True for _ in range(h)) for _ in range(w))##sq[w][h]
for i in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        for ix in range(x):
            for iy in range(h):
                sq[ix][iy] = False
    if a == 2:
        for ix in range(x, w):
            for iy in range(h):
                sq[ix][iy] = False
    if a == 3:
        for ix in range(w):
            for iy in range(y):
                sq[ix][iy] = False
    if a == 4:
        for ix in range(w):
            for iy in range(y, h):
                sq[ix][iy] = False
s = 0
for h in range(w):
    s += sq[h].count(True)
print(s)           
        

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	int l=0,r=n-1;
	int mid=(l+r)>>1;
	string s;
	bool f1,f2,f3;
	cout<<l<<endl;
	cout.flush();
	cin>>s;
	if(s=="Male")f1=true;
	else if(s=="Female")f1=false;
	else return 0;
	cout<<r<<endl;
	cout.flush();
	cin>>s;
	if(s=="Male")f3=true;
	else if(s=="Female")f3=false;
	else return 0;
	while(l<r){
		cout<<mid<<endl;
		cout.flush();
		cin>>s;
		if(s=="Male")f2=true;
		else if(s=="Female")f2=false;
		else return 0;
		if((f1==f2&&(mid-l)%2==0)||(f1!=f2&&(mid-l)%2==1))l=mid,r=r,f1=f2,mid=(l+r+1)>>1;
		else l=l,r=mid,f3=f2,mid=(l+r)>>1;
	}
	cout<<l<<endl;
	cout.flush();
	cin>>s;
	cout<<r<<endl;
	cout.flush();
	cin>>s;
	return 0; 
} 

Measured memory_bytes: 852
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;


int main() {
//    cout << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    string s;
    cin >> s;
    int ans = 0;
    string prev, till;
    for (char c : s) {
        till += c;
        if (till != prev) {
            ans++;
            prev = till;
            till.clear();
            
        }
    }
    
    cout << ans;

}

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

#define FIO ios_base::sync_with_stdio(0); cin.tie(0);
#define T() int tt; cin >> tt; rep1(qq,1,tt)
#define rep(i,start,lim) for(int i=start;i<lim;i++)
#define rep1(i,start,lim) for(int i=start; i<=lim; ++i)
#define repd(i,start,lim) for(int i=start;i>=lim;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define br cout<<"\n"
#define MOD (1000000007LL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eps (1e-6)
#define what_is(x) cerr << #x << " is " << x << "\n";
#define int long long int
#define infll 9e18
#define inf 1e12

#define lnode (2 * node + 1)
#define rnode (2 * node + 2)

using namespace std;

typedef pair<int, int> pii;

const int N = 3005;

int n, s;
int a[N], dp[N][N], ndp[N][N];

int add(int x, int y, int m){
  int res = ((x % m) + (y % m)) % m;
  return res;
}

int mul(int x, int y, int m){
  int res = ((x % m) * (y % m)) % m;
  return res;
}

int sub(int x, int y, int m){
  int res = ((x % m) - (y % m) + m) % m;
  return res;
}

int32_t main()
{

	FIO
	//cout << fixed << setprecision(10);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

  const int M = 998244353;
  cin >> n >> s;
  for(int i = 0; i < n; ++i) cin >> a[i];
  dp[0][a[0]] = (0 + 1);
  ndp[0][a[0]] = 1;
  int res = 0;
  if(a[0] == s) res = n;
  for(int i = 1; i < n; ++i){
    dp[i][a[i]] = (i + 1);
    ndp[i][a[i]] = (i + 1);
    for(int j = 0; j <= s; ++j){
      ndp[i][j] = add(ndp[i][j], ndp[i - 1][j], M);
      if(j > a[i]) ndp[i][j] = add(ndp[i][j], ndp[i - 1][j - a[i]], M);
      if(j > a[i]) dp[i][j] = ndp[i - 1][j - a[i]];
    }
    res = add(res, mul((n - i), dp[i][s], M), M);
    res %= M;
  }
  cout << res << '\n';
  
	return 0;
}





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

int main(){
	ios_base::sync_with_stdio(false);
	vector< pair<pair<string,int>,int> > rest;
	int n;cin>>n;
	for(int i=0;i<n;i++){
		pair<pair<string,int>,int> tmp;
		cin>>tmp.first.first>>tmp.first.second;
		tmp.first.second*=-1,tmp.second=i;
		rest.push_back(tmp);
	}
	sort(rest.begin(),rest.end());
	for(int i=0;i<n;i++)printf("%d\n",rest[i].second+1);
	return 0;
}

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

long long joy[15];

int main ()
{

   long long a;
   vector<long long>v,v1;
   for(long long i=0;i<4;i++) cin>>a,v.push_back(a);
   sort(v.begin(),v.end());
   v1.push_back(1);
   v1.push_back(4);
   v1.push_back(7);
   v1.push_back(9);
   if(v==v1) cout<<"YES"<<endl;
   else cout<<"NO"<<endl;


}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main()
{
    int count[100] = {};
    for (int i = 0; i < 3; i++) {
        int p;
        cin >> p;
        count[p - 1] = 1;
    }
    int ans = 0;
    for (int i = 0; i < 100; i++) {
        ans += count[i];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 998244353;
const int SIZE = 10002;
int dp[SIZE][SIZE];
LL fac[SIZE],inv[SIZE];
LL mypow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1)res=res*x%MOD;
        y>>=1;
        x=x*x%MOD;
    }
    return res;
}
LL C(int x,int y){
    if(y<0||y>x)return 0;
    return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
void build(){
    assert(MOD>=SIZE);
    fac[0]=1;
    REPP(i,1,SIZE)fac[i]=fac[i-1]*i%MOD;
    inv[SIZE-1]=mypow(fac[SIZE-1],MOD-2);
    for(int i=SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%MOD;
}
void ADD(int &x,LL v){
    x=(x+v)%MOD;
}
int main(){
    build();
    string A,B;
    cin>>A>>B;
    int same=0,dif=0;
    REP(i,SZ(A)){
        if(A[i]=='1'){
            if(B[i]=='1')same++;
            else dif++;
        }
    }
    if(!dif)return 0*printf("%d\n",(int)(fac[same]*fac[same]%MOD));
    dp[0][0]=1;
    REP(i,dif+1)REP(j,same+1){
        ADD(dp[i+1][j],dp[i][j]*(LL)(dif-i));
        ADD(dp[i][j+1],dp[i][j]*(j+1LL)*i);
    }
    int an=0;
    REP(i,same+1){
        ADD(an,C(same,i)*C(same+dif,i+dif)%MOD*dp[dif][i]%MOD*fac[same-i]%MOD*fac[same-i]);
    }
    printf("%d\n",(int)(an*fac[dif]%MOD));
    return 0;
}


Measured memory_bytes: 195200
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<utility>
#include<algorithm> // sort
#include<map> // pair
#include<cmath>
#include<cstring>
#include<set>
using namespace std;
using ll = long long;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
const ll mod = 1e9+7;
const int INF = 1e9;
const ll INFLONG = 1e18;
int w,h,k;
ll num[101][8];//w,h
void dp(){
  rep(i,h){
    rep(j,w){
      for(int bit=0;bit < 1<<(w-1);bit++){
        bool can = true;
        for(int k=0;k<w-2;k++){
          if(((1 << k) & bit) > 0 && (((1<<(k+1)) & bit) > 0)){
            can = false;
            break;
          }
        }
        if(!can){continue;}
        int nj = j;
        if(j > 0 && ((1<<(j-1)) & bit) > 0){nj = j-1;}
        else if(((1<<j) & bit) > 0){nj = j+1;}
        num[i+1][nj] += num[i][j];
        num[i+1][nj] %= mod;
      }
    }
    // rep(j,w){
    //   num[i+1][j] = num[i][j] * movin[j][j];
    //   if(j != 0){
    //     num[i+1][j] += num[i][j-1] * movin[j-1][j];
    //     num[i+1][j] %= mod;
    //   }
    //   if(j != w-1){
    //     num[i+1][j] += num[i][j+1] * movin[j+1][j];
    //     num[i+1][j] %= mod;
    //   }
    // }
  }
}
int main(){
  cin >> h >> w >> k; // h:height w:sort k:the number of horioznal line
  memset(num,0,sizeof(num));
  num[0][0] = 1;
  dp();

  // rep(i,h+1){
  //   rep(j,w){
  //     cout << num[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  cout << num[h][k-1];
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t H, W, ans;
  cin >> H >> W;
  ans = H * W / 2;
  if (H * W % 2 == 1) {
    ans++;
  }
  if (H == 1 || W == 1) {
    ans = 1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		if(A > 9 || B > 9) {
			System.out.println(-1);
		} else {
			System.out.println(A * B);
		}
	}
}


Measured memory_bytes: 21844
n = int(input())

if n % 2 == 1:
  print(0)
  
elif n < 9:
  print(0)
else:
  count = 0
  for i in range(30):
    sub = 10 * (5**i)
    count += n // sub
    
    if sub > n:
      break
      
  print(count)
        
  

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


int main() {
  int K;
  cin >> K;
  int Amari=7;
  int Ans=1;
  if(K%2==0){
    Ans=-1;
  }
  if(K%5==0){
    Ans=-1;
  }
  if(Ans>=0){
    while(Amari%K != 0){
      Ans++;
      Amari =(10*Amari+7)%K;
    }
  }
    cout << Ans;
  
}


Measured memory_bytes: 3620
/**********************************************
 * author : deepak nayan
 * file   : e:/Solutions/atcoder/abc104_a.cpp
 * time   : Thu Apr 30 21:55:52 2020
 * quest  : A - Rated for Me
 *********************************************/
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int r;
  cin >> r;
  cout << (r < 1200 ? "ABC" : r < 2800 ? "ARC" : "AGC") << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int dx[]={0,1,0,-1,1,-1,-1,1};
const int dy[]={-1,0,1,0,1,1,-1,-1};
const int INF = 1<<30;
const double EPS = 1e-15;
#define PB push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
#define MOD 1000000007
typedef pair<int,int> Pii;
typedef pair<int,Pii> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
struct Point{
	double x,y;
	Point(){}
	Point(double _x,double _y){
		x = _x;
		y = _y;
	}
	Point operator + (Point p){
		return Point(x+p.x,y+p.y);
	}

	Point operator - (Point p){
		return Point(x-p.x,y-p.y);
	}

	Point operator * (double k){
		return Point(k*x,k*y);
	}


	bool operator<(const Point &p)const{
		return x!=p.x?x<p.x:y<p.y;
	}

};
double dot(Point p, Point q){
	return p.x*q.x+p.y*q.y;
}

double cross(Point p,Point q){
	return p.x*q.y-q.x*p.y;
}

double norm(Point p){
	return p.x*p.x+p.y*p.y;
}

double pabs(Point p){
	return sqrt(norm(p));
}
typedef vector<Point> Polygon;
struct Line : Polygon{
	Line(){}
	Line(Point p,Point q){
		PB(p);
		PB(q);	
	}
};
struct Circle{
	Point p; //中心点
	double r; //半径
	Circle(){}
	Circle(Point _p,double _r){
		p = _p;
		r = _r;
	}
};
int ccw(Point a,Point b,Point c){
	b = b-a;
	c = c-a;
	if(cross(b,c) > 0)return +1; //a→b で反時計に折れて c ccw
	if(cross(b,c) < 0)return -1; //a→b で時計に折れて ccw
	if(dot(b,c) < 0)return +2; // c--a--b;
	if(pabs(b)<pabs(c))return -2; //a--b--c
	return 0; //a--c--b
}
bool intersectSS(Line l,Line m){
	//lとmが交差してるかどうか
	return (ccw(l[0],l[1],m[0])*ccw(l[0],l[1],m[1])<=0)&&
			(ccw(m[0],m[1],l[0])*ccw(m[0],m[1],l[1])<=0);
}

int main(){
	int Q;
	cin >> Q;
	while(Q--){
		Point p[4];
		rep(i,4){
			double x,y;
			cin >> x >> y;
			p[i] = Point(x,y);
		}
		Line l,m;
		l.PB(p[0]);l.PB(p[1]);
		m.PB(p[2]);m.PB(p[3]);
		cout << intersectSS(l,m) << "\n";
	}
	return 0;
}

Measured memory_bytes: 1232
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main(){
	string s;
	int k,x=0;
	cin>>s>>k;
	int n=s.size();
	for(int i=0;i<n;i++){
		if(s[i]=='1'){
			x++;
			continue;
			}
		if(x>=k){
			cout<<'1'<<endl;
			return 0;
			}
		else{
			cout<<s[i]<<endl;
			return 0;
			}
		}
		cout<<'1'<<endl;
		return 0;
}


Measured memory_bytes: 256
import java.util.* ;
public class Main{
       public static void main( String args[] ){
             Scanner cin = new Scanner( System.in ) ;
             int a = cin.nextInt() ;
             int b = cin.nextInt() ;
             if ( a % 2 == 1 && b % 2 == 1 ) System.out.println( "Yes" ) ;
             else System.out.println( "No" ) ;
       }
} 

Measured memory_bytes: 23124
#include<cstdio>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
int a[100],b[100],c[100],d[100];
int Min,ans;
int main(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
			scanf("%d %d",&a[i],&b[i]);
		}
	for(int j = 1;j <= m;j++){
			scanf("%d %d",&c[j],&d[j]);
		}
	for(int i = 1;i <= n;i++){
			Min = 999999999;
		for(int j = 1;j <= m;j++){
			if(Min>(abs(a[i]-c[j])+abs(b[i]-d[j]))){
				Min =  abs(a[i]-c[j])+abs(b[i]-d[j]);
				ans = j;
				}
			}
			printf("%d\n",ans);
		}
	return 0;
	}


Measured memory_bytes: 256
// Input macro
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let 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! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

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

// Test Code
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
    "3 5 2 7" => "15",
    "100 600 200 300" => "60000",
}

fn main() {
    println!("{}", solve(&stdin!()));
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        a: u32,
        b: u32,
        c: u32,
        d: u32,
    }

    let s1 = a * b;
    let s2 = c * d;

    std::cmp::max(s1, s2).to_string()
}

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

using namespace std;

int main()
{
	long long A,B,N,x,ans;
	cin>>A>>B>>N;
	if(N<B)
	{
		x=N;
	}
	else
	{
		x=B-1;
	}
	ans = ((A*x)/B) - (A*(x/B));
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3632
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1e9+7;
const llint big=(llint)(2.19e15+1);
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int main(void){
	while(-1){
		int ans=0;
		string str;cin>>str;
		if(str=="0"){RE;}
		for(auto it:str){ans+=it-'0';}
		cout<<ans<<endl;
	}
	RE;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;
using namespace std;
const int MAX = 200010;

int main(){
    int N;
    int  A[MAX], B[MAX], P[MAX];
    ll K, Ls, Le, ae;
    cin >> N >> K;
    REP(int,i,1,N+1) cin >> A[i];
    REP(int,i,1,N+1) B[i]=-1;
    
    B[1]=1;
    P[1]=1;
    REP(int,i,1,N+1){
        ae=A[P[i]];
        if(B[ae]==-1){
            //cout << ae << endl;
            B[ae]=i+1;
            P[i+1]=ae;
        }else{
            Le=i;
            break;
        }
    }
    Ls=B[ae];

    if(K+1<=Ls){
        cout << P[K+1] << endl;
    }else{
        ae=(K+1-Ls)%(Le-Ls+1);
        cout << P[ae+Ls] << endl;
    }
}


Measured memory_bytes: 5912
fun readInt(): Int {
    val N: Int = readLine()!!.toInt()
    return N
}

fun readString(): String {
    val N: String = readLine()!!
    return N
}

fun getSeqList(): List<Int>{
    return (1..5).toList()
}

fun solveB(): Long{
    val N: Int = readLine()!!.toInt()
    var An: Array<Int?> = arrayOfNulls(N)
    var ans: Long = 0
    for (i in An.indices) {
        val num: Int = (i + 1)
        if (num%3 == 0 || num%5 == 0 ){
            continue
        }
        ans += num
    }
    return ans
}

fun solveA(): String{
    val N: Int = readLine()!!.toInt()
    for (i1 in (1..9).toList()){
        for (i2 in (1..9).toList()){
            if (N == i1*i2){
                return "Yes"
            }
        }
    }
    return "No"
}

fun main(args: Array<String>) {
    //Practice
    //println(getSeqList())
    // 20200421 A problem
    /*
    if (readString().contains('7')){
        println("Yes")
    } else {
        println("No")
    }
    */

    // 20200421 B problem
    //println(solveB())
    println(solveA())
}


Measured memory_bytes: 33528
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,b;
    ll a[100010],c;
    cin>>n>>m;
    for (int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    vector<pair<ll,int>> p;
    for (int i=0;i<m;i++){
        cin>>b>>c;
        p.push_back(make_pair(c,b));
    }
    sort(p.begin(),p.end(),greater<>());
    int r=0;
    ll ans=0;
    for(int i=0;i<m;i++){
        int k=r+p.at(i).second;
        if (k>n) k = n;
        if(p.at(i).first >= a[k-1]){
            ans+=p.at(i).first*(k-r);
            r=k;
        } else {
            for(int j=0;j<k;j++){
                if(p.at(i).first <= a[r+j]) {
                    ans+=p.at(i).first*j;
                    r+=j;
                    break;
                }
            }
            break;
        }
        if (r==n) break;
    }
    
    for(int i=r;i<n;i++){
        ans+=a[i];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <cstdio>
#include <numeric>
#include <climits>
#include <cstring>
#include <map>
#include <utility>
#include <tuple>
#include <set>

using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl

int main() {
    int h, w;
    while (cin >> h >> w) {
        rep(i, h)rep(j, w) {
            string s;
            cin >> s;
            if (s == "snuke") {
                cout << (char)('A' + j) << 1+i << endl;
            }
        }
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<math.h>
#include<queue>
#include<vector>
#include<algorithm>
#define Max (int)450
#define MAX2 (int)1e5+5
#define MOD ((int)1e9+7)
using namespace std;

int main(){
	int n,front[Max],back[Max],a[Max],i;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(i == 0)
			front[i] = a[i];
		else
			front[i] = front[i-1]+a[i];
	}

	for(i=n-1;i>=0;i--){
		if(i == n-1)
			back[i] = a[i];
		else
			back[i] = back[i+1]+a[i];
	}
	int max = back[0];
	for(i=0;i<n-1;i++){
		if(fabs(front[i]-back[i+1]) < max){
			max = fabs(front[i]-back[i+1]);
		}
	}
	if(max > front[n-1])
		max = front[n-1];
	printf("%d\n",max);

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int,int>> vp;
typedef pair<int,int> pii;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9+7;
const int MAX = 10000000;
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
//cout << 'H' << endl;
//next_permutation(ALL(p));
//typedef priority_queue<int> pque;//これは大きい順
//typedef priority_queue<int, vector<int>, greater<int>> pque;//これは小さい順
//factorizeは、素因数分解用の関数

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

	cout << 3 * r * r << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
inline char gc() {
  if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
  return p1 == p2 ? EOF : *(p1++);
}
template <class T> inline void read(T &n) {
  n = 0; RI ch = gc(), f;
  while ((ch < '0' || ch > '9') && ch != '-') ch = gc();
  f = (ch == '-' ? ch = gc(), -1 : 1);
  while (ch >= '0' && ch <= '9') n = n * 10 + (ch ^ 48), ch = gc();
  n *= f;
}

int main() {
  
#ifdef LOCAL
  FILEIO("a");
#endif

  int A, B, C, K;
  cin >> A >> B >> C >> K;
  int ans = 0;
  if (K >= A) ans += A, K -= A;
  else ans += K, K = 0;
  if (K >= B) K -= B;
  if (K >= C) ans -= C, K -= C;
  else ans -= K, K = 0;
  cout << ans;

  return 0;
}

// created by Daniel yuan
/*
     ________
    /        \
   / /      \ \
  / /        \ \
  \            /
   \  ______  /
    \________/
*/


Measured memory_bytes: 3636
import java.util.*;

public class Main {
	int N;
	long K;
	List<Long> A;

	Main() {
		Scanner in = new Scanner(System.in);
		String[] tokens = in.nextLine().split(" ");
		N = Integer.parseInt(tokens[0]);
		K = Long.parseLong(tokens[1]);
		tokens = in.nextLine().split(" ");
		in.close();
		A = new ArrayList<>(N);
		for (int i = 0; i < N; ++i) {
			A.add(Long.parseLong(tokens[i]));
		}
		Collections.sort(A);
	}

	int getKetasuu(long max) {
		int result = 1;
		long temp = 1;
		while (temp < max) {
			temp *= 2;
			result++;
		}
		return result;
	}

	void countOne(long val, int[] oneCounts) {
		int index = 0;
		while (val != 0) {
			if (index >= oneCounts.length) {
				break;
			}
			if (val % 2 == 1) {
				oneCounts[index]++;
			}
			val /= 2;
			++index;
		}
	}

	long calcX(int[] oneCounts) {
		long addVal = (long) Math.pow(2.0, oneCounts.length - 1);
		long x = 0;
		for (int i = oneCounts.length - 1; i >= 0; --i) {
			if (oneCounts[i] < N - oneCounts[i]) {
				if (x + addVal <= K) {
					x += addVal;
				}
			}
			addVal /= 2;
		}
		return x;
	}

	long calc() {
		long x = 0L;
		if (K > 0) {
			int ketasuu = getKetasuu(K);
			int[] oneCounts = new int[ketasuu];
			Arrays.fill(oneCounts, 0);
			for (Long val : A) {
				countOne(val, oneCounts);
			}
			x = calcX(oneCounts);
		}
		long result = 0;
		for (int i = 0; i < A.size(); ++i) {
			result += x ^ A.get(i);
		}
		return result;
	}

	public static void main(String[] args) {
		Main ins = new Main();
		System.out.println(ins.calc());
	}

}

Measured memory_bytes: 57016
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx,avx2")
#define rep(i, n)    for(ll i = 0; i < (n); ++i)
#define repA(i, a, n)  for(ll i = a; i <= (n); ++i)
#define repD(i, a, n)  for(ll i = a; i >= (n); --i)
#define pb push_back
#define X first
#define Y second
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vii;
const ll INF = 1e18+1;
const ll MOD = 1000000007L;
#ifdef umang99m
    #include "/home/umang/Desktop/folder/home/.templates/header.h"
#else
    #define dbg(args...)
    #define timer()
#endif
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    std::cout << std::fixed << std::showpoint;
    std::cout << std::setprecision(15);
    ll n;
    cin>>n;
    vector<ld>p(n);
    vector<vector<ld>>dp(n,vector<ld>(n+1));
    rep(i,n) cin>>p[i];
    dp[0][0] = 1.0-p[0];
    dp[0][1] = p[0];
    repA(j,2,n)dp[0][j] = 0;
    repA(i,1,n-1){
        repA(j,0,n){
            dp[i][j] = (1.0-p[i])*dp[i-1][j];
            if(j>0) dp[i][j] += p[i]*dp[i-1][j-1];
        }
    }
    ld ans =0;
    for(int i=n/2+1; i<=n;i++){
        ans += dp[n-1][i];
    }
    cout<<ans<<endl;
    timer();
    return 0;
}

Measured memory_bytes: 141056
/*
auth - @sportykush
*/

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; 
// using namespace __gnu_pbds;

typedef long long int ll;
typedef long double ld;

//#define mp make_pair
#define bug(v)                    cerr<<#v<<" = "<<(v)<<endl;
#define bug2(v1,v2)               cerr<<#v1<<" = "<<(v1)<< ' ' << #v2<<" = "<<(v2)<<endl;
#define ERASE(x)                  x.erase(unique(x.begin(),x.end()),x.end())
#define pb                        emplace_back
#define vii                       vector<int>
#define vll                       vector<ll>
#define vpll                      vector< pair <ll,ll> >
#define pll                       pair <ll,ll>
#define pii                       pair <int,int>
#define pq                        priority_queue< int >
#define khtm                      "\n"
#define F                         first
#define S                         second
#define fr(i,a,n)                 for(i=a;i<n;i++)
#define mem(arr,l)                memset(arr,l,sizeof arr)
#define ALL(x)                    x.begin(), x.end()
#define frr(i,a,n)                for(i=n-1;i>=a;i--)
#define fast                      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define testcase                  ll T; cin>>T; while(T--)


const double pi = 3.14159265359;
const int MAX = 1e6 +2;
const ll inf =  1e18;
const int N = 1010;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
//const ll mod = 998244353;
const ll mod = 1000000007;
inline ll add(ll a,ll b){a+=b;if(a>=mod)a-=mod;return a;}
inline ll mul(ll a,ll b){return (((a+mod)%mod)*(b+mod)%mod)%mod;}
inline ll power(ll a,ll b){ll rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline ll modInverse(ll n, ll p){ return power(n, p-2)%p; }

/*
important builtin functions
__gcd(value1, value2)
__builtin_ffs(x)
  Number of leading zeroes: __builtin_clz(x)
  Number of trailing zeroes : __builtin_ctz(x)
  Number of set bits: __builtin_popcount(x)
*/
 
void stArt()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}
void eNd()
{
	#ifndef ONLINE_JUDGE
  	cout<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s";
  	#endif
}

//////////////////// start /////////////////////////////////
 

ll i,j,k,l,m,r,n;
//ll a[MAX],b[MAX];


#include <atcoder/all>
using namespace atcoder;

int main()
{
 
stArt();
fast
//cout << setprecision(15) << fixed;

cin >> n;
dsu d(n);
testcase
{
	cin >> k >> l >> r;
	if(k)
		cout << (d.same(r,l)?1:0) << endl;
	else
		d.merge(l,r);
}
  
eNd();
	return 0;
 
}

Measured memory_bytes: 3976