akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <string>

using namespace std;

long long dp[(int) (1e5+1)];
long long nums[(int) (1e4+1)];

int main() {
    int n;
    cin >> n;
    vector<int> dp(3);

    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        vector<int> new_dp(3, 0);
        vector<int> c(3);

        for (int i = 0; i < 3; i++)
            scanf("%d", &c[i]);

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i != j)
                    new_dp[j] = max(new_dp[j], dp[i] + c[j]);
            }
        }
        dp = new_dp;
    }

    cout << max({dp[0], dp[1], dp[2]});

    return 0;
}


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

// Shortening code
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef tuple<int, int, int> ti;

// Macros
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = a; i >= b; i--)

ll INF = 1e9 + 5;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // Your code
    int n;
    cin >> n;
    vector<vi> joy(n, vi(3));
    REP(i, 0, n){
        cin >> joy[i][0] >> joy[i][1] >> joy[i][2];
    }
    vector<vi> dp(n, vi(3, -INF));
    dp[0][0] = joy[0][0];
    dp[0][1] = joy[0][1];
    dp[0][2] = joy[0][2];
    REP(i, 1, n){
        REP(j, 0, 3){
            REP(k, 0, 3){
                if(j != k){
                    dp[i][j] = max(dp[i][j], dp[i - 1][k] + joy[i][j]);
                }
            }
        }
    }
    cout << *max_element(dp[n - 1].begin(), dp[n - 1].end());
    return 0;
}

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

class Main {
    public static void main(String args[]){
        String a=A0();
        System.out.println(v1(a.charAt(0)));

    }

    static char v1(char c){
        return ++c;
    }

    public static String A0(){

        try(BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String str = reader.readLine();
            return str;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;

    }
}

Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;
  int sum = 0;
  int x;
  for(int i = 0; i < n; i++){
    cin >> x;
    if(x > k){
      sum += x - k;
    }else if(x > k - x){
      sum += k - x;
    }else {
      sum += x;
    }
  }
  cout << sum * 2;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 8;

vector<int> G[MAX_N];
int n;
ll ans;

void dfs(int v,set<int> S)
{
	S.insert(v);
	if(S.size() == n){
		ans++;
		return;
	}
	rep(i,G[v].size()){
		if(S.find(G[v][i]) == S.end()){
			dfs(G[v][i],S);
		}
	}
}

int main()
{
	int m,a,b;
	cin >> n >> m;
	rep(i,m){
		cin >> a >> b;
		G[a-1].push_back(b-1);
		G[b-1].push_back(a-1);
	}
	ans = 0;
	set<int> S;
	dfs(0,S);
	cout << ans << "\n";
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int A, B, T, cnt = 0;
    scanf("%d %d %d",&A, &B, &T);
    int i = 1;
    int time = A;
    while(time < T + 0.5){
        cnt += B;
        i++;
        time = i * A;
    }
    printf("%d\n", cnt);
    return 0;
}

Measured memory_bytes: 128
using System;

class Program
{
    static void Main()
    {
            int a, b,c;
            string inp = Console.ReadLine();
            string[] data = inp.Split(' ');
            a = int.Parse(data[0]);
            b = int.Parse(data[1]);
            c = int.Parse(data[2]);
            if (a < b && a < c&&b<c)
            {
                Console.WriteLine("Yes");
            }else
            {
                Console.WriteLine("No");
            }
    }
}


Measured memory_bytes: 8932
from sys import stdin
inp = stdin.readline

N = int(inp().rstrip())
S = [inp().rstrip() for _ in range(N)]

cnt = [0, 0, 0, 0, 0]

for s in S:
    if s[0] == "M":
        cnt[0] += 1
    elif s[0] == "A":
        cnt[1] += 1
    elif s[0] == "R":
        cnt[2] += 1
    elif s[0] == "C":
        cnt[3] += 1
    elif s[0] == "H":
        cnt[4] += 1

ans = 0

for i in range(3):
    for j in range(i + 1, 4):
        for k in range(j + 1, 5):
            ans += cnt[i] * cnt[j] * cnt[k]

print(ans)


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

int main() {
  
  int N;
  cin >> N;
  int num,max,sum=0;
  
  
  for(int i=0; i<N; i++){
    cin >> num;
    sum += num;
    if(max<num){max=num;}
  }
  sum -= max/2;
  
  cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pr pair<int,int>
#define mod 1000000007
#define endl "\n"

int power(int a,int b,int m=mod)
{
	if(b==0)	return 1;
	if(b==1)	return a;
	int res=power(a,b/2,m);
	res=(res*res)%m;
	if(b&1)	res=(res*a)%m;
	return res;
}
int modinv(int a,int m=mod){ return power(a,m-2,m);}
int add(int a,int b,int m=mod){	return (a+b)%m;}
int sub(int a,int b,int m=mod){	return (a-b+m)%m;}
int mul(int a,int b,int m=mod){	return (a*b)%m;}



void solve()
{
	int k;
	cin>>k;
	int val=100,ans=0;
	while(val<k)
	{
		int x=val/100;
		val=val+x;
		ans++;
	}
	cout<<ans<<endl;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int t=1;//cin>>t;
	while(t--)	solve();
	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };


int main(){cout<<fixed<<setprecision(10);
		   int n;
           cin>>n;
           int x=n*800;
           int y=n/15*200;
           cout<<x-y<<endl;
}

Measured memory_bytes: 3632
A, B, C = map(int, input().split())

n = A % B
if n == 0:
    print('NO')
else:
    f = n
    i = 2
    l = [f]
    while True:
        n = (i * f) % B
        i += 1
        l.append(n)
        if n == f:
            break
    if C in set(l):
        print('YES')
    else:
        print('NO')
        


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main(){
	int n;
	while(cin>>n && n!=0){
		vector<pii> d(n+1);
		int num;
		rep(i,1,n+1){
			cin>>num;
			d[i].fi=num;
		}
		d[0].fi=-1;
		d[0].se=0;
		d[1].se=1;

		rep(i,2,n+1){
			if(!(i%2)){
				if(d[i].fi==d[i-1].fi) d[i].se=d[i-1].se+1;
				else{
					d[i].se=d[i-1].se+d[i-1-d[i-1].se].se+1;
				}
			}else{
				if(d[i].fi==d[i-1].fi) d[i].se=d[i-1].se+1;
				else d[i].se=1;
			}
		}

		int ans=0;
		int i=n;
		while(i>0){
			if(d[i].fi==0) ans+=d[i].se;
			i-=d[i].se;
		}
		o(ans);
	}
}

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

int main(){
    using namespace std;
    unsigned long N, K;
    cin >> N >> K;
    if(K > N)return 0 & puts("0");
    vector<unsigned long> H(N);
    for(auto& i : H)cin >> i;
    nth_element(H.begin(), H.end() - K, H.end());
    cout << accumulate(H.begin(), H.end() - K, 0UL) << endl;
    return 0;
}

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

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

using namespace std;

int main(void)
{
	ui N{ 0 };
	ui A{ 0 };
	ui B{ 0 };
	ui C{ 0 };
	ui D{ 0 };
	string str{ 0 };

	(void)scanf("%d", &N);
	(void)scanf("%d", &A);
	(void)scanf("%d", &B);
	(void)scanf("%d", &C);
	(void)scanf("%d", &D);
	cin >> str;

	str = "#" + str;
	bool result{ true };

	// A番目～C番目及び、
	// B番目～D番目までの部分文字列に
	// "##"が存在するとき、到達不可能
	{
		string sec_ac = str.substr(A, (C - A) + 1);
		result &= (sec_ac.find("##", 0) == sec_ac.npos);
	}
	{
		string sec_bd = str.substr(B, (D - B) + 1);
		result &= (sec_bd.find("##", 0) == sec_bd.npos);
	}

	if (result && C > D)
	{
		// B - 1番目～D + 1番目までの部分文字列に
		// "..."が存在する必要がある
		string sec = str.substr(B - 1, ((D + 1) - (B - 1)) + 1);
		result &= (sec.find("...", 0) != sec.npos);
	}
	
	string ans = result ? "Yes" : "No";

	printf("%s\n", ans.c_str());

	return 0;
}


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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int prev=1, cur;
	int a,b; cin>>a>>b;
	for (int inc=2; inc<1000; inc++) {
		cur=prev+inc;
		if(prev-a==cur-b) {
			cout << prev-a << endl;
			return 0;
		}
		prev=cur;
	}
	return 0;
}


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

using namespace std;


int main(void){
//	FILE* fp_in = freopen("data.txt", "r", stdin);

	while(1) {
		vector<vector<int>> cards;
		int pts[] = {0,0};	//太郎と花子の合計点数
		int ans[2] = {999,999};	//交換するカードの値
		int num[2];

		cin >> num[0] >> num[1];
		if( num[0] == 0 && num[1] == 0) break;

		//各人のカードの合計点数・カード情報を取得する
		for(int i = 0; i < 2; i++) {
			vector<int> newcards;
			for(int j = 0; j < num[i]; j++) {
				int s;
				cin >> s;
				newcards.push_back(s);
				pts[i] += s;
			}
			cards.push_back(newcards);
		}

		//交換の全通りを調べる
		for(int i = 0; i < num[0]; i++) {
			for(int j = 0; j < num[1]; j++) {
				//交換後の点数を調べる
				int tmp[2];
				tmp[0] = pts[0] - cards.at(0).at(i) + cards.at(1).at(j);
				tmp[1] = pts[1] + cards.at(0).at(i) - cards.at(1).at(j);
				if(tmp[0] == tmp[1]) {
					if(ans[0] + ans[1] > cards.at(0).at(i) + cards.at(1).at(j)) {
						ans[0] = cards.at(0).at(i);
						ans[1] = cards.at(1).at(j);
					}
				}
			}
		}

		if(ans[0] == 999 && ans[1] == 999) {
			cout << -1 << endl;
		} else {
			cout << ans[0] << " " << ans[1] << endl;
		}

	}

	//while(1){}
	return 0;
}

Measured memory_bytes: 1216
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long A = sc.nextLong();
		long B = sc.nextLong();

		if ((B + A) % 2 == 0) {
			System.out.println((B - A) / 2);
		} else {
			System.out.println(Math.min(A-1, N-B) + 1 + (B-A-1)/2);
		}

	}
}

Measured memory_bytes: 35504
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=100010;

int n,m,cnt=1,G[N],c[N],ic[N],dfn[N],dpt[N];
struct edge{
  int t,nx;
}E[N<<2];

inline void addedge(int x,int y){
  E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
  E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt;
}

int prty,u,v;

void dfs(int x,int cc){
  c[x]=cc;
  for(int i=G[x];i;i=E[i].nx){
    if(!c[E[i].t]) dfs(E[i].t,3-cc);
    if(c[E[i].t]==c[x]) prty=1,u=x,v=E[i].t;
  }
}

int ans,a[N];

int dfs1(int x,int f){
  int ret=a[x];
  for(int i=G[x];i;i=E[i].nx)
    if(E[i].t!=f && c[E[i].t]!=c[x]) ret+=dfs1(E[i].t,x);
  ans+=abs(ret);
  return ret;
}

int k[N],Q[N],t,ct;

int dfs2(int x,int f){
  int ret=a[x];
  for(int i=G[x];i;i=E[i].nx)
    if(E[i].t!=f && i!=ct && (i^1)!=ct){
      ret+=dfs2(E[i].t,x);
      k[x]+=k[E[i].t];
    }
  if(k[x]){
    if(k[x]<0) Q[++t]=-ret;
    else Q[++t]=ret;
  }
  else ans+=abs(ret);
  return ret;
}

int vis[N];

void dfs3(int x,int f){
  vis[x]=1;
  for(int i=G[x];i;i=E[i].nx){
    if(E[i].t==f) continue;
    if(!vis[E[i].t]) dfs3(E[i].t,x);
    else u=x,v=E[i].t,ct=i;
  }
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1,x,y;i<=m;i++)
    scanf("%d%d",&x,&y),addedge(x,y);
  dfs(1,1); int num=0;
  for(int i=1;i<=n;i++)
    if(c[i]==2) num++,a[i]=1; else num--,a[i]=-1;
  if(n-1==m){
    if(num) puts("-1");
    else{
      dfs1(1,0); printf("%d\n",ans);
    }
  }
  else{
    if(prty){
      if(num&1) puts("-1");
      else{
	a[u]-=num/2; a[v]-=num/2;
	dfs1(1,0); printf("%d\n",ans+abs(num/2));
      }
    }
    else{
      if(num) puts("-1");
      else{
	dfs3(1,0);
	k[u]=1; k[v]=-1;
	dfs2(1,0); Q[++t]=0;
	sort(Q+1,Q+1+t);
	int cur=Q[t/2];
	for(int i=1;i<=t;i++) ans+=abs(cur-Q[i]);
	printf("%d\n",ans);
      }
    }
  }
  return 0;
}


Measured memory_bytes: 11520
#include<cstdio>
#define swap(a, b) {int c=a; a=b; b=c;}

int main(void){
	int n, m, i, j, a[100];
	scanf("%d%d", &n, &m);
	for(i=0; i<n; ++i){ scanf("%d", a+i); }
	for(i=1; i<=m; ++i){
		for(j=0; j<n-1; ++j){
			if(a[j]%i>a[j+1]%i){ swap(a[j], a[j+1]); }
		}
	}
	for(i=0; i<n; ++i){ printf("%d\n", a[i]); }
	return(0);
}


Measured memory_bytes: 2728
// ※※※ 解答不能 ※※※
// tourist氏.
// https://atcoder.jp/contests/cf16-relay-open/submissions/8978522
#include <bits/stdc++.h>
using namespace std;
#define repx(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second

int main(){
    int n;
    scanf("%d", &n);
    vector<pair<int, int>> ret;
    rep(i, n){
        rep(j, n){
            if((i + j) % 2 == 1 && (i % 3 == 0 || i == n - 1 || j == 0 || j == n - 1)) ret.emplace_back(i, j);
        }
    }
    printf("%d\n", ret.size());
    for(auto& p : ret) printf("%d %d\n", p.a, p.b);
    return 0;
}

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

using ll = long long;
const ll INF = 2e18;

const int MAXN = 6e3;
int N;
const int MAXM = 210;
int M;

ll A[MAXN];
int B[MAXN][MAXM];

ll sum[MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 1; i < N; i++) {
		A[i] += A[i-1];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> B[i][j];
		}
	}

	for (int z = 0; z < M; z++) {
		vector<int> v(N);
		for (int i = 0; i < N; i++) {
			v[i] = B[i][z];
		}
		vector<int> lInd(N);
		vector<int> rInd(N);

		{
			vector<int> st;
			for (int i = 0; i < N; i++) {
				while (!st.empty() && v[st.back()] < v[i]) {
					st.pop_back();
				}
				lInd[i] = (st.empty() ? 0 : st.back() + 1);
				st.push_back(i);
			}
		}

		{
			vector<int> st;
			for (int i = N-1; i >= 0; i--) {
				while (!st.empty() && v[st.back()] < v[i]) {
					st.pop_back();
				}
				rInd[i] = (st.empty() ? N-1 : st.back() - 1);
				st.push_back(i);
			}
		}

		auto update = [&](int xlo, int xhi, int ylo, int yhi, int d) -> void { // half open
			assert(xlo < xhi && ylo < yhi);
			sum[xlo][ylo] += d;
			sum[xlo][yhi] -= d; 
			sum[xhi][ylo] -= d;
			sum[xhi][yhi] += d;
		};

		for (int i = 0; i < N; i++) {
			update(lInd[i], i+1, i, rInd[i]+1, v[i]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 1; j < N; j++) {
			sum[i][j] += sum[i][j-1];
		}
	}
	for (int j = 0; j < N; j++) {
		for (int i = 1; i < N; i++) {
			sum[i][j] += sum[i-1][j];
		}
	}

	ll ans = -INF;
	for (int l = 0; l < N; l++) {
		for (int r = l; r < N; r++) {
			ll cost = -A[r] + A[l] + sum[l][r];
			ans = max(ans, cost);
		}
	}
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 240512
from collections import deque

N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
score = dict(r=P, s=R, p=S)
ans = 0
q = deque()
for i in range(K):
    s = T[i]
    ans += score[s]
    q.append(s)
for i in range(K, N):
    s = T[i]
    s_pre_k = q.popleft()
    if s == s_pre_k:
        q.append('n')
    else:
        ans += score[s]
        q.append(s)
print(ans)


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

using namespace std;

#define ll            long long int
#define endl          '\n'

static const int maxn = 2e5 + 5;

struct Seg
{
      int fmax, smax;
      Seg(int fmax = 0, int smax = 0) : fmax(fmax), smax(smax) {}

      void assignLeaf(int num)
      {
            fmax = num;
            smax = 0;
      }
      void marge(const Seg &lchild, const Seg &rchild)
      {
            fmax = max(lchild.fmax, rchild.fmax);
            smax = max({min(lchild.fmax, rchild.fmax), lchild.smax, rchild.smax});
      }
} Tree[maxn * 4];

void build(int node, int a, int b)
{
      if (a == b) return void(Tree[node] = Seg());
      int lchild = node * 2;
      int rchild = lchild + 1;
      int mid = (a + b) / 2;
      build(lchild, a, mid);
      build(rchild, mid + 1, b);
      Tree[node].marge(Tree[lchild], Tree[rchild]);
}

void update(int node, int a, int b, int pos, int val)
{
      if (a > pos or b < pos) return;
      if (a >= pos and b <= pos) return void(Tree[node].assignLeaf(val));
      int lchild = node * 2;
      int rchild = lchild + 1;
      int mid = (a + b) / 2;
      update(lchild, a, mid, pos, val);
      update(rchild, mid + 1, b, pos, val);
      Tree[node].marge(Tree[lchild], Tree[rchild]);
}

Seg query(int node, int a, int b, int i, int j)
{
      if (a > j or b < i) return Seg();
      if (a >= i and b <= j) return Tree[node];
      int lchild = node * 2;
      int rchild = lchild + 1;
      int mid = (a + b) / 2;
      Seg p = query(lchild, a, mid, i, j);
      Seg q = query(rchild, mid + 1, b, i, j);
      Seg res;
      res.marge(p, q);
      return res;
}

ll ans;

void solve(vector <int> &vec)
{
      int n = vec.size() - 1;
      vector <Seg> LEFT(n + 1);
      build(1, 1, n);
      for (int i = 1; i <= n; i++)
      {
            Seg pos = query(1, 1, n, vec[i] + 1, n);
            LEFT[i] = pos;
            ans += 1LL * vec[i] * (LEFT[i].fmax - LEFT[i].smax);
//            cerr << "LEFT " << i << " " << LEFT[i].fmax << " " << LEFT[i].smax <<  " " << 1LL * vec[i] * (LEFT[i].fmax - LEFT[i].smax) << endl;
            update(1, 1, n, vec[i], i);
      }
      reverse(vec.begin() + 1, vec.end());
      vector <Seg> RIGHT(n + 1);
      build(1, 1, n);
      for (int i = 1; i <= n; i++)
      {
            Seg pos = query(1, 1, n, vec[i] + 1, n);
            RIGHT[i] = pos;
            ans += 1LL * vec[i] * (RIGHT[i].fmax - RIGHT[i].smax);
//            cerr << "RIGHT " << i << " " << RIGHT[i].fmax << " " << RIGHT[i].smax <<  " " << 1LL * vec[i] * (RIGHT[i].fmax - RIGHT[i].smax) << endl;
            int j = n - i + 1;
            if (j > LEFT[j].fmax) ans += 1LL * vec[i] * (j - LEFT[j].fmax - 1) * (RIGHT[i].fmax - RIGHT[i].smax);
            if (i > RIGHT[i].fmax) ans += 1LL * vec[i] * (i - RIGHT[i].fmax - 1) * (LEFT[j].fmax - LEFT[j].smax);
            update(1, 1, n, vec[i], i);
      }
}

signed main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);


      int n;
      cin >> n;
      vector <int> vec(n + 1);
      for (int i = 1; i <= n; i++) cin >> vec[i];
      solve(vec);
      cout << ans << endl;
}



Measured memory_bytes: 8448
#include <stdio.h>
#define N 1000

int main(void){
  int r,c,i,j;
  int su[N][N];

  scanf("%d %d", &r, &c);
  for(i=0;i<r;i++){
    for(j=0;j<c;j++){
      scanf("%d", &su[i][j]);
    }
  }
  for(i=0;i<r;i++){
    for(j=0;j<c;j++){
      su[i][c] += su[i][j];
    }
  }
  for(j=0;j<=c;j++){
    for(i=0;i<r;i++){
      su[r][j] += su[i][j];
    }
  }

  for(i=0;i<=r;i++){
    for(j=0;j<=c;j++){
      printf("%d",su[i][j]);
      if(j!=c){
        printf(" ");
      }
    }
    printf("\n");
  }
  return 0;
}



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

    int main(){
        int H, W;
            while(1){
                cin >> H >> W;
                    if(H == 0 && W == 0){
                        return 0;
                    }
                        for(int i = 0; i < H; i++){
                            for(int j = 0; j < W; j++){
                                cout << "#";
                            }
                                cout << endl;
                        }
                            cout << endl;
            }      
    return 0;}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n,i;
    cin>>n;
    for(i=1;i<=n;i++){
        if(n%i==0){
            if(i<10 && (n/i)<10){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  #if len(f[gk])==0:
  #  dg1c.append(a[gk])
  #  continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
ary=[]
cnt=0
#print(dg)
#print(f)
#print(dg1c)

for k in dg.keys():
  t=min(dg[k])
  ans+=t
  cnt+=1
  dg[k].remove(t)
  ary+=dg[k]
ary.sort()
ans+=sum(ary[:(n-m-1)*2-cnt])
print(ans)


Measured memory_bytes: 115500
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int type; cin>>type;
	if(type==1){
		cout<<"Hello World"<<endl;
	}
	else{
		int a,b; cin>>a>>b;
		cout<<a+b<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i,total=0;
	cin>>n;
	vector<int> C(n),V(n);
	for(i=0;i<n;i++){
		cin>>V[i];
	}
	for(i=0;i<n;i++){
		cin>>C[i];
		if(V[i]>C[i])total=total+V[i]-C[i];
	}
	cout<<total<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
const int inf=1e9+7;
const ll INF=1LL<<61;
const ll mod=1e9+7;



ll modinv(ll a) {
    ll m=mod;
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}



map<ll,ll> ma;
map<ll,ll> m2;

void calc(int a){
  for(int i=2;i*i<=a;i++){
    while(a%i==0){
      a=a/i;
      ma[i]++;
      m2[i]++;
    }
  }
  if(a>1) {
    ma[a]++;
    m2[a]++;
  }
}

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

  ll ans=0;
  for(i=0;i<n;i++) {
    ans+=modinv(a[i]);
    ans%=mod;
  }

  for(i=0;i<n;i++) {
    ans*=a[i];
    ans%=mod;
  }

  for(i=0;i<n;i++) calc(a[i]);

  for(auto it=ma.begin();it!=ma.end();++it){
   // cout<<(it->first)<<" "<<(it->second)<<endl;
  }

  for(i=0;i<n;i++){
    map<ll,ll> mm;
    for(j=2;j*j<=a[i];j++){
      while(a[i]%j==0){
        mm[j]++;
        a[i]/=j;
      }
    }
    if(a[i]>1) mm[a[i]]++;
    for(auto it=mm.begin();it!=mm.end();++it){
      //cout<<it->first<<endl;
      m2[it->first]=min(m2[it->first],ma[it->first]-it->second);
    }
  }

  for(auto it=m2.begin();it!=m2.end();++it){
    int v=it->first;
    int u=it->second;
    //cout<<v<<" "<<u<<endl;
    for(int j=0;j<u;j++){
      ans*=modinv(v);
      ans%=mod;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
#define skip continue
#define NAME "code"

using namespace std;
 
typedef long long ll;
typedef long double ld;

const int maxn = 1e6 + 10;
const int inf = 1e6;
const ll mod = 2e3 + 7;
const ld pi = acos(-1);

ll n, a[maxn], ans;

int main(){

cin >> n;

for(int i = 0; i < n * 2; ++i){
	cin >> a[i];
}

sort(a, a + 2 * n);

for(int i = 0; i < n * 2; i += 2)
	ans += a[i];

cout << ans;

return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;


int main() {
  int a,b,c;
  cin >> a >> b >> c;
  cout << min(a*b,c) << endl;
}


Measured memory_bytes: 256
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Measured memory_bytes: 5636
//-----created by xxx-----
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const double pi = acos(-1.0);
inline ll read()
{               
    ll x=0,f=1; char ch=getchar();  
    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f*x;
}
inline void write(ll a)
{
    if(a<0) putchar('-'),a=-a; 
    if (a>=10) write(a/10), putchar(a%10+'0');
}
const int MAX_N=105;
int n;
int a[MAX_N],b[MAX_N],ma=0;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b,b+n);
    int v=unique(b,b+n)-b;
    for(int i=0;i<n;i++){
        a[i]=lower_bound(b,b+v,a[i])-b+1;
        ma=max(a[i],ma);
    }
    int ans=0;
    for(int i=1;i<n;i++){
        if(a[i]==a[i-1]){
            a[i]=++ma;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    ll n;
    cin >> n;
    ll a[n], b[n];
    rep(i, n) { cin >> a[i] >> b[i]; }

    ll ans = 0;
    ll buf = 0;
    repb(i, n) {
        ll m = (a[i] + buf) % b[i];
        if (m != 0) {
            ans += b[i] - m;
            buf += b[i] - m;
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 5172
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
#include <time.h>
#include <complex>
#include <cstdint>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
#define mod 1000000007
typedef long long ll;

unsigned gcd(int a, int b) {
	while (1) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}


ll comb(int n, int r) {
	if (r * 2 > n) r = n - r;
	uintmax_t dividend = 1;
	uintmax_t divisor = 1;
	for (unsigned int i = 1; i <= r; ++i) {
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}

int compare_char(const void* left, const void* right) {
	char *left_char = (char *)left;
	char *right_char = (char *)right;

	return strcmp(left_char, right_char);
}

int main(){


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

	//int N, M, *A, *B, i, j, *W, *flag, sum=0, start, end, length, tmp;
	ll i, j, k, l, m, n, len;
	ll A, B, C, D, N, M, K, num_R, num_G, num_B, ans;
	ll sum = 0, sum_B = 0, sum_C = 0, max, min, count = 0, Q, W, X;
	ll **dp;
	char S[200000];


	ll temp1, temp2;




	cin >> A >> B >> N;


	if (B == 1){

		cout << "0" << endl;
		return 0;
	}
	max = 0;
	i = std::min(B - 1, N);

		temp1 = (A*i / B);
		temp2 = (i / B);
		ans = temp1 - A*temp2;
		if (ans > max)
			max = ans;
	


	
	cout << max << endl;



	return 0;

}
    

Measured memory_bytes: 3604
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W, M= getNM()
query = [getList() for i in range(M)]
bomb_dict = defaultdict(set)

# 縦hに行くとi個飴がもらえる
h_list = defaultdict(int)
w_list = defaultdict(int)
h_len = set()
w_len = set()

for h, w in query:
    h -= 1
    w -= 1
    h_list[h] += 1
    w_list[w] += 1
    h_len.add(h)
    w_len.add(w)
    bomb_dict[h].add(w)

# 飴がj個もらえる行はどこか
candy_h = defaultdict(list)
candy_w = defaultdict(list)

for i in h_list.items():
    candy_h[i[1]].append(i[0])
for i in w_list.items():
    candy_w[i[1]].append(i[0])

opt_h = sorted(candy_h.items(), reverse = True)[0]
opt_w = sorted(candy_w.items(), reverse = True)[0]
h_n = opt_h[0]
w_n = opt_w[0]

flag = False
ser_h = opt_h[1]
ser_w = opt_w[1]

for i in ser_h:
    for j in ser_w:
        # ボンバーマンh列に一つもなければ
        if not j in bomb_dict[i]:
            print(h_n + w_n)
            exit()

print(h_n + w_n - 1)

Measured memory_bytes: 339244
#include<stdio.h>
int main()
{
	int A,B;
	1<=A<=13;
	1<=B<=13;
	scanf("%d%d",&A,&B);
	if(A>B&&B!=1||A==1&&B!=1)
	printf("Alice");
	if(A<B&&A!=1||B==1&&A!=1)
	printf("Bob");
	if(A==B)
	printf("Draw");
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();

		int len = 1;
		int lenMax = 0;
		// st:調べる文字列の先頭
		for ( int st = 0; st + len - 1 < n; st++ ) {
			// 切り出す
			String temp = s.substring(st, st + len);
			// 自分以降に2個目がある限りlenを増やす
			while ( s.indexOf(temp, st + len) > st ) {
				len++;
				temp = s.substring(st, st + len);
			}
			// Maxを記憶（lenは行き過ぎてるので -1）
			lenMax = Math.max(lenMax, len - 1);
			if(lenMax > 1) len = lenMax;
		}

		System.out.println(lenMax);
		in.close();
	}
}

Measured memory_bytes: 39204
//#pragma GCC oplmize(2)
#include <bits/stdc++.h>
#define ll long long
#define sc(x) scanf("%lld",&x)
#define scs(x) scanf("%s",x+1)
#define pr(x) printf("%lld\n",x)
#define prs(x) printf("%s\n",x)
using namespace std;
const int maxn=1e7+5;
const int mod=998244353;
const double pi=acos(-1.0);
const double eps = 1e-8;
char s[maxn];
int a[maxn],len;
ll sum;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    scs(s);
    len=strlen(s+1);
    for(int i=1;i<=len;i++){
        a[i]=s[len-i+1]-'0';
    }
    for(int i=1;i<=len+1;i++){
        if(a[i]==10){
            a[i]-=10;
            a[i+1]++;
        }
        if(a[i]>5){
            sum+=(10-a[i]);
            a[i+1]++;
        }
        else if(a[i]<5){
            sum+=a[i];
        }
        else{
            sum+=5;
            if(a[i+1]>=5){
                a[i+1]++;
            }
        }
    }
    pr(sum);
    return 0;
}

Measured memory_bytes: 8732
#include <iostream>
#include <string>

// 1, 3, 6, 10, 

int main(void) {
  int a, b;

  std::string str;

  std::cin >> a;
  std::cin >> b;

  int tower[999] = {0};

  tower[0] = 1;
  for (size_t i = 1; i < 999; i++) {
    tower[i] = tower[i-1] + (i + 1);
  }

  int diff = b - a;

  int tidx = diff - 1;

  std::cout << tower[tidx] - b << std::endl;

#if 0
  for (size_t guess = 1; guess < 499500; guess++) {
    for (size_t i = 0; i < 998; i++) {
      if (tower[i] == (a + guess) && tower[i+1] == (b + guess)) {
        std::cout << guess << std::endl;
        return 0;
      }
    }
  }
#endif
  return 0;
}

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

//create arrays outside of main()

int a[100];

int main(){

    int a;
    int b;
    
    cin >> a >> b;

    if((a+b)%2 == 0){
        cout << (a+b)/2;
    } else {
        cout << "IMPOSSIBLE";
    }

    return 0;
}

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

void make_name(char *dist[]);
char *name[20];
int m, n;

//data[i]はi桁目(10進数)、これをn乗。
void pwd(int *data, int n) {
	int i, j, k;
	int BigNum[201] = {0}, MBigNum[201] = {0};
	
	BigNum[0] = 1;
	for( i = 0; i < n; i++ ) {
		for( j = 0; j < 100; j++ ) {
			for( k = 0; k < 100; k++ ) {
				MBigNum[j+k] += BigNum[j] * data[k];
				MBigNum[j+k+1] += MBigNum[j+k]/10;
				MBigNum[j+k] %= 10;
			}
		}
		for( j = 0; j < 100; j++ ) {
			BigNum[j] = MBigNum[j];
			MBigNum[j] = 0;
		}
	}
	
	for( j = 0; j < 100; j++ ) {
		data[j] = BigNum[j];
	}
}

int main() {
	int i;
	int BigNum[200] = {0};
	make_name(name);
	while(cin >> m >> n) {
		if(!m) break;
		BigNum[0] = m%10;
		BigNum[1] = m/10;
		pwd(BigNum, n);
		int l, r;
		for(i = 0; i < 100; i++ ) {
			if( BigNum[i] )
				break;
		}
		l = i;
		for(i = 99; i >= 0; i--) {
			if( BigNum[i] )
				break;
		}
		r = i;
		
		bool disp0 = true;
		for(i = r; i >= l; i--) {
			if( BigNum[i] == 0 && !disp0 )
				continue;
			cout << BigNum[i];
			if( BigNum[i] != 0 ) {
				disp0 = true;
			}
			if( i % 4 == 0 ) {
				cout << name[i/4];
				disp0 = false;
			}
		}
		
		if( i % 4 != 3)
			l = i/4 * 4;
		else
			l = i+1;
		for(; i >= l; i--) {
			cout << BigNum[i];
			if( i % 4 == 0 ) {
				cout << name[i/4];
			}
		}
		cout << endl;
		
		for( i = 0; i < 100; i++ )
			BigNum[i] = 0;
	}
	return 0;
}

void make_name(char *dist[]) {
	dist[0] = "";
	dist[1] = "Man";
	dist[2] = "Oku";
	dist[3] = "Cho";
	dist[4] = "Kei";
	dist[5] = "Gai";
	dist[6] = "Jo";
	dist[7] = "Jou";
	dist[8] = "Ko";
	dist[9] = "Kan";
	dist[10] = "Sei";
	dist[11] = "Sai";
	dist[12] = "Gok";
	dist[13] = "Ggs";
	dist[14] = "Asg";
	dist[15] = "Nyt";
	dist[16] = "Fks";
	dist[17] = "Mts";
}

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

using namespace std;

typedef long long int lli;


vector<int> all(3);
string inp,inp2;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>inp>>inp2;
    int sz=inp.size();
    for(int i=0;i<sz;i++)
    {
        if(inp==inp2)
        {
            cout<<"Yes";
            return 0;
        }
        char f=inp[sz-1];
        inp.erase(sz-1,1);
        inp=f+inp;
    }
    cout<<"No";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N),S(N+1);
    rep(i,N){
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    rep(i,N){
        S[i+1] = S[i] + A[i];
    }
    ll L=-1, R=N;
    while(L+1 < R){
        ll X = (L+R)/2;
        ll cur = S[X+1];
        ll compf = true;
        for(ll i=X+1;i<N;i++){
            if(cur*2 >= A[i]){
                cur += A[i];
            }else{
                compf = false;
                break;
            }
        }
        if(compf){
            R = X;
        }else{
            L = X;
        }
    }
    cout << N-R << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

int main()
{
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int s = a[0];
    rep(i, n-1)
        s ^= a[i+1];
    rep(i, n){
        int bi = s^(a[i]);
        cout << bi;
        if(i == n-1) cout << endl;
        else cout << " ";
    }
    return 0;
}

Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main(){
  string s;
  cin >> s;
  if(s == "RRR") cout << 3 << endl;
  else if(s == "RRS" || s == "SRR") cout << 2 << endl;
  else if(s == "SSS") cout << 0 << endl;
  else cout << 1 << endl;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

void ABC104B()
{
	string S;
	cin >> S;
	if (S[0] != 'A')
	{
		cout << "WA" << endl;
		return;
	}
	int ct = 0;
	for (int i = 1; i < S.size(); ++i)
	{
		if (S[i] == toupper(S[i]))
		{
			if (i >= 2 && i < S.size() - 1 && S[i] == 'C')
				++ct;
			else
			{
				cout << "WA" << endl;
				return;
			}
		}
	}
	if (ct != 1)
	{
		cout << "WA" << endl;
		return;
	}
	cout << "AC" << endl;
}

int main()
{
	ABC104B();
	return 0;
}

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

typedef vector<int> vi;
typedef vector<double> vd;

double mypow(double b ,int e){
	  if(e == 0) return 1;
	  if(e%2==0)
			return mypow( b*b, e/2 );
	  else
			return mypow( b*b, e/2 ) * b;
}

int main(){


	  int N,M,L; cin >> N >> M >> L ;
	  if(N==1){
			cout << 1.0 << endl;
			return 0;
	  }
	  vector<vd> prob(N,vd(M+1,0.0));
	  vector<vd> dist(N,vd(M+1,0.0));

	  vd p(N),t(N),v(N);
	  for(int i=0; i<N; i++)	cin >> p[i] >> t[i] >> v[i];

	  // PRE PROCESS
	  for(int i=0; i<N; i++){
			dist[i][0] = (double)L / v[i];
			for(int j=1; j<=M; j++){
				  dist[i][j] = dist[i][j-1] + t[i];
			}
	  }
	  for(int i=0; i<N; i++)
			prob[i][0] = mypow((100-p[i])/100,M);
	  for(int i=0; i<N; i++){
			for(int j=1; j<=M; j++){
				  if(p[i] != 100)
						prob[i][j] = (prob[i][j-1] * (p[i]/100)) / ((100-p[i])/100);
				  else
						prob[i][j] = 1.0;
			}
	  }
	  double comb = 1;
	  for(int j=1; j<=M; j++){
			comb = comb * (M - j + 1) / j; 
			for(int i=0; i<N; i++){
				  prob[i][j] *= comb;
			}
	  }
	  
	  vector<vd> sum = prob;
	  for(int i=0; i<N; i++){
			for(int j=M-1; j>=0; j--){
				  sum[i][j] += sum[i][j+1];
				  if(sum[i][j] > 1) sum[i][j] = 1;
			}
	  }

	  vector<vd> ans = prob;
	  for(int i=0; i<N; i++){
			for(int j=0; j<=M; j++){
				  for(int k=0; k<N; k++){
						if(i==k) continue;
						int id = upper_bound(dist[k].begin(),dist[k].end(), dist[i][j]) - dist[k].begin();
						if(id > M) ans[i][j] = 0.0;
						else 	   ans[i][j] *= sum[k][id];

				  }
			}
	  }

	  for(int i=0; i<N; i++){
			double tmp = 0.0;
			if(p[i] == 100) tmp = ans[i][M];
			else
				  for(int j=0; j<=M; j++)
						tmp += ans[i][j];
			if(tmp > 1) tmp = 0;
			printf("%.10f\n",tmp);
	  }
						
}

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

const int NOT_FOUND=-1;

int binarysearch(int key,int A[],int n){	
 int left =0;
 int right=n;

 while(left<right){
	int mid=(left+right)/2;

	if(A[mid]==key){
		return mid;
	}
	else if(key<A[mid]){
		right=mid;
	}
	else {
		left=mid+1;
	}
 }
 return NOT_FOUND;
}

int main(){
 int n;
 cin>>n;
 int S[100000];
 for(int i=0;i<n;i++){
	cin>>S[i];
 }

 int q;
 cin>>q;

 int T[50000];
 for(int i=0;i<q;i++){
	cin>>T[i];
 }

 int C=0;
 for(int i=0;i<q;i++){
	if(binarysearch(T[i],S,n)!=NOT_FOUND){
		C++;
	}
 }

 cout<< C<<endl;
return 0;
}

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

struct SuccessiveShortestPath {
  struct Edge{ int to, cap, cost, rev; };
  int n, init;
  vector<vector<Edge>> g;
  vector<int> dist, pv, pe, h;

  SuccessiveShortestPath() {}
  SuccessiveShortestPath(int n, int INF = 1e9)
    : n(n), g(n), init(INF), dist(n), pv(n), pe(n) {}

  void addEdge(int u, int v, int cap, int cost) {
    int szU = g[u].size();
    int szV = g[v].size();
    g[u].push_back({v, cap, cost, szV});
    g[v].push_back({u, 0, -cost, szU - 1});
  }
  int dijkstra(int s, int t) {
    dist = vector<int>(n, init);
    using Node = pair<int, int>;
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({dist[s] = 0, s});

    while (!pq.empty()) {
      auto d = pq.top().first;
      auto u = pq.top().second;
      pq.pop();
      if (dist[u] < d) continue;
      for (int i = 0; i < g[u].size(); ++i) {
        Edge& e = g[u][i];
        int v = e.to;
        if (e.cap > 0 && dist[v] > dist[u] + e.cost + h[u] - h[v]) {
          dist[v] = dist[u] + e.cost + h[u] - h[v];
          pv[v] = u;
          pe[v] = i;
          pq.push({dist[v], v});
        }
      }
    }
    return dist[t];
  }
  int build(int s, int t, int f) {
    int res = 0;
    h = vector<int>(n, 0);
    while (f > 0) {
      if (dijkstra(s, t) == init) return -1;
      for (int i = 0; i < n; ++i) h[i] += dist[i];
      int flow = f;
      for (int u = t; u != s; u = pv[u]) {
        flow = min(flow, g[pv[u]][pe[u]].cap);
      }
      f -= flow;
      res += flow * h[t];
      for (int u = t; u != s; u = pv[u]) {
        Edge& e = g[pv[u]][pe[u]];
        e.cap -= flow;
        g[u][e.rev].cap += flow;
      }
    }
    return res;
  }
};

int main() {
  int n, m, f; cin >> n >> m >> f;
  SuccessiveShortestPath ssp(n);
  while (m--) {
    int u, v, c, d; cin >> u >> v >> c >> d;
    ssp.addEdge(u, v, c, d);
  }
  cout << ssp.build(0, n - 1, f) << endl;
  return 0;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,ans=0;
  cin>>n;
  vector<int>vec;
  int x;
  for(int i=0;i<n;i++){cin>>x;vec.push_back(x);}

  for(int i=0;i<n;i++)
  {
    for(int j=i+1;j<n;j++)
    {
      ans+= vec[i]*vec[j];
    }
  }

  cout<<ans;

}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdio>
using namespace std;
using ll = long long;
int main(){
  string s;
  cin >> s;
  int n = s.length();
  cout << s[0] << n - 2 << s[n - 1] << endl;
  return 0;
}

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

static const int INFTY = (1<<29);
static const int N_MAX = 509;
static const int C_MAX = 31;

int N,C,c;

int D[C_MAX][C_MAX];
int X[3][C_MAX];

int main(){

  // 入力
  cin >> N >> C;
  for(int i=1;i<=C;i++){
    for(int j=1;j<=C;j++) cin >> D[i][j];
  }
  for(int i=1;i<=N;i++){
    for(int j=1;j<=N;j++){
      cin >> c;
      X[(i+j)%3][c]++;
    }
  }

  int ans=INFTY;
  for(int i=1;i<=C;i++){
    for(int j=1;j<=C;j++){
      if(i != j){
        for(int k=1;k<=C;k++){
          if(i!=k && j!=k){

            int total=0;
            for(int l=1;l<=C;l++) total+=D[l][i]*X[0][l];
            for(int l=1;l<=C;l++) total+=D[l][j]*X[1][l];
            for(int l=1;l<=C;l++) total+=D[l][k]*X[2][l];

            ans  = min(ans,total);

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, dp[100004][2];
vector<int> edge[100004];
int mul(int a, int b){
	long long ret = 1LL*a*b;
	return ret%mod;
}

void dfs(int here,int par){
	dp[here][0] = 1;
	dp[here][1] = 1;
	if(edge[here].size() == 1 && edge[here][0] == par)
		return;
	for(int there : edge[here]){
		if(there == par)	continue;
		dfs(there,here);
		dp[here][0] = mul(dp[here][0],dp[there][1]);
		dp[here][1] = mul(dp[here][1],(dp[there][0]+dp[there][1])%mod);
	}
	return;
}
int main() {
	cin>>n;
	int x, y;
	for(int i = 0 ; i<n-1;i++){
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(1,0);
	cout<<(dp[1][0]+dp[1][1])%mod;
	return 0;
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    int N;
    cin >> N;
    int x = N % 10;
    set<int> se{2, 4, 5, 7, 9}, se2{0, 1, 6, 8};
    if (se.count(x) == 1) {
        cout << "hon" << endl;
    } else if (se2.count(x) == 1) {
        cout << "pon" << endl;
    } else {
        cout << "bon" << endl;
    }
    return 0;
}

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

int main(void) {
    int A, B, C, D, sum = 0;
    cin >> A >> B >> C >> D;
    if (A < C) {
        if (B < C) {
        }
        else if (D < B) {
            sum = D - C;
        }
        else {
            sum = B - C;
        }
    }
    else {
        if (D < A) {
        }
        else if (B < D) {
            sum = B - A;
        }
        else {
            sum = D - A;
        }
    }
    cout << sum << endl;

}

Measured memory_bytes: 256