akhauriyash/Code-Regression huggingface dataset:
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-8;


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

	int N;
	cin >> N;
	if (N == 1) {
		cout << 1 << endl;
		cout << 1 << endl;
		return 0;
	}
	if (N == 2) {
		cout << 2 << endl;
		cout << 0 << endl;
		cout << 11 << endl;
		return 0;
	}
	cout << N - 1 << endl;
	for (int i = 2; i <= N; i++) {
		cout << 0;
		for (int j = 0; j < i - 2; j++)cout << 1;
		cout << 0 << endl;
	}
}


Measured memory_bytes: 3212
n, k = map(int, input().split())
a = list(map(int, input().split()))
from fractions import gcd
g = a[0]
for i in range(n):
  g = gcd(g, a[i])

if k % g != 0 or max(a) < k:
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')
  
  
  


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

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define ll long long

int main() {
    int h, w;
    cin >> h >> w;

    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        cout << s << endl;
        cout << s << endl;
    }

    return 0;
}

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


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

    if((a + b) % 2 == 0) cout << (a + b) / 2 << endl;
    else cout << (a + b) / 2 + 1 << endl;

    return 0;
}


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

using namespace std;

using ll =  long long;

constexpr ll INF = 1LL << 60;
constexpr int MAX_N = 300;

void warshall_floyd(int n, vector<vector<ll>> &d){
    for(int k=0;k<n;++k) {
        for(int i=0;i<n;++i) {
            for(int j=0;j<n;++j) {
                if(d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; ll l;
    cin >> n >> m >> l;

    int a, b; ll c;
    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    for(int i=0;i<m;++i){
        cin >> a >> b >> c;
        if(c > l) continue;
        --a; --b;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    for(int i=0;i<n;++i) {
        dist[i][i] = 0;
    }

    warshall_floyd(n, dist);
    
    vector<vector<ll>> cnt(n, vector<ll>(n, INF));
    for(int i=0;i<n;++i) {
        for(int j=0;j<n;++j) {
            if(dist[i][j] == INF) continue;
            if(dist[i][j] <= l) cnt[i][j] = 1;
        }
    }

    warshall_floyd(n, cnt);

    int q, s, t;
    cin >> q;
    while(q--) {
        cin >> s >> t;
        --s; --t;
        cout << ((cnt[s][t] == INF)?-1:(cnt[s][t]-1)) << endl;
    }
}


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

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> dist(n,inf);
    vector<int> prev(n,-1);
    vector<int> list[n];
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--, b--;
        list[a].push_back(b);
        list[b].push_back(a);
    }
    dist[0] = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u:list[v]){
            if(dist[u] != inf) continue;
            dist[u] = dist[v]+1;
            prev[u] = v;
            q.push(u);
        }
    }
    cout << "Yes" << endl;
    for(int i=1; i<n; i++){
        cout << prev[i]+1 << endl;
    }
}

Measured memory_bytes: 10556
#include<bits/stdc++.h>
using namespace std;
#define int long long
int partition(int* A,int p,int r){
  int x=A[r];
  int i=p-1;
  for(int j=p;j<r;j++){
    if(A[j]<=x){
      i++;
      swap(A[i],A[j]);
    }
  }
  swap(A[i+1],A[r]);
  return i+1;
}
signed main(){
  int n;
  cin>>n;
  int A[n];
  for(int i=0;i<n;i++) cin>>A[i];
  int k=partition(A,0,n-1);
  for(int i=0;i<n;i++){
    if(i) cout<<" ";
    if(i==k) cout<<"[";
    cout<<A[i];
    if(i==k) cout<<"]";
  }
  cout<<endl;
  return 0;
}



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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct MaximumFlow
{
	struct Edge
	{
		int to, cap, rev;
		Edge(int to, int cap) : to(to), cap(cap) {}
	};
	int N, src, sink;
	vector<vector<Edge>> G;
	vector<int> dist, work;
	MaximumFlow(int N, int src, int sink) : N(N), src(src), sink(sink) {
		G.resize(N);
		dist.resize(N);
		work.resize(N);
	}
	void add_edge(int f, int t, int cap) {
		G[f].emplace_back(t,cap);
		G[t].emplace_back(f,0);
		G[f].back().rev=G[t].size()-1;
		G[t].back().rev=G[f].size()-1;
	}
	void add_edge_from_source(int t, int cap) {add_edge(src,t,cap);}
	void add_edge_to_sink(int f, int cap) {add_edge(f,sink,cap);}
	int dfs(int c, int MF=0x7fffffff) {
		int flow;
		if(c==sink) return MF;
		for(int &i=work[c];i<G[c].size();i++) {
			auto &e=G[c][i];
			if(e.cap>0 && dist[e.to]==dist[c]+1 && (flow=dfs(e.to,min(e.cap,MF)))) {
				e.cap-=flow;
				G[e.to][e.rev].cap+=flow;
				return flow;
			}
		}
		return 0;
	}
	int flow() {
		int ret=0;
		queue<int> Q;
		for(;;) {
			int flow=0;
			fill(dist.begin(),dist.end(),0x7fffffff);
			dist[src]=0;
			Q.push(src);
			while(!Q.empty()) {
				int c=Q.front();
				Q.pop();
				for(auto &e: G[c]) if(e.cap>0 && dist[e.to]>dist[c]+1) {
					dist[e.to]=dist[c]+1;
					Q.push(e.to);
				}
			}
			fill(work.begin(),work.end(),0);
			while(int temp=dfs(src)) flow+=temp;
			if(flow==0) break;
			ret+=flow;
		}
		return ret;
	}
};

int V[1000][1000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, A, B;
	cin>>N>>M>>A>>B;
	for(int i=0;i<=N;i++) for(int j=0;j<=M;j++) if(i*A+(N-i)*(M-A)==j*B+(M-j)*(N-B)) {
		MaximumFlow mf(N+M+2,N+M,N+M+1);
		for(int k=0;k<N;k++) mf.add_edge_from_source(k,k<i ? A:M-A);
		for(int k=0;k<M;k++) mf.add_edge_to_sink(k+N,k<j ? B:N-B);
		for(int k=0;k<N;k++) for(int l=0;l<M;l++) {
			V[k][l]=mf.G[k].size();
			mf.add_edge(k,l+N,1);
		}
		mf.flow();
		for(int k=0;k<N;k++) {
			for(int l=0;l<M;l++) {
				cout<<mf.G[k][V[k][l]].cap;
			}
			cout<<'\n';
		}
		return 0;
	}
	cout<<"-1\n";
	return 0;
}

Measured memory_bytes: 29440
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (a + b > c + d) P("Left");
  else if (a + b < c + d) P("Right");
  else P("Balanced");
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
typedef long long ll;
typedef long double ld;
 
#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define deb(x) cerr << #x << " " << x << '\n';
 
#define int ll
 
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
 
using namespace std;
 
void pudge(){ 
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.length(); i++){
        if (s[i] != t[i]) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef PUDGE
    freopen("pudge.in", "r", stdin);
    freopen("pudge.out", "w", stdout);
#endif
 
    //int q; cin >> q; while(q--)
    pudge();
 
    return 0;
}



Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
char s[25][25];
bool vis[25][25];
struct node{
    int x,y,dis;
};
int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void bfs(int x,int y){
    if(s[x][y]=='#'){
    	return ;
	}
    memset(vis,0,sizeof(vis));
    queue<node>q;
    q.push((node){x,y,0});
    vis[x][y]=1;
    while(!q.empty()){
        node now=q.front();
        q.pop();
        ans=max(ans,now.dis);
        for(int i=0;i<4;++i){
            int temp_x=now.x+direction[i][0]; 
			int temp_y=now.y+direction[i][1];
            if(temp_x<=0){
            	continue;
			}else if(temp_x>n){
				continue;
			}else if(temp_y<=0){
				continue;
			}else if(temp_y>m){
				continue;
			}else if(s[temp_x][temp_y]=='#'){
				continue;
			}else if(vis[temp_x][temp_y]){
				continue;
			}
            q.push((node){temp_x,temp_y,now.dis+1});
            vis[temp_x][temp_y]=1;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>s[i]+1;
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		bfs(i,j);
		}
	}
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
  ll n,W;
  cin>>n>>W;
  vector<ll>w(n+1),v(n+1);
  for(int i=1; i<=n; i++)
  {
      cin>>w[i]>>v[i];
  }
  ll dp[W+1][n+1];
  loop(i,n+1){dp[0][i]=0;}
  loop(i,W+1){dp[i][0]=0;}
  for(int i=1; i<=W; i++)
  {
      for(int j=1; j<=n; j++)
      {
          if(w[j]<=i){dp[i][j]=max(v[j]+dp[i-w[j]][j-1], dp[i][j-1])   ;}
          else dp[i][j]=dp[i][j-1];
      }
  }
 // ll ans=max(dp[0][n-1],max(dp[1][n-1], dp[2][n-1]));
  cout<<dp[W][n]<<endl;
}


Measured memory_bytes: 82464
use proconio::input;

fn main() {
    input! {
        h: i64,
        w: i64,
    }

    if h == 1 || w == 1 {
        println!("{}", 1);
    } else if h % 2 == 1 && w % 2 == 1 {
        println!("{}", h * w / 2 + 1);
    } else {
        println!("{}", h * w / 2);
    }
}


Measured memory_bytes: 2100
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d",&x);
#define scs(x) scanf("%s",x);
#define scl(x) scanf("%lld",&x);
#define rep(i,s,e) for(int i=s; i<=e; ++i)
#define dep(i,s,e) for(int i=s; i>=e; --i)
typedef long long ll;
using namespace std;
const ll mod=998244353;
int a[2005][2005],b[2005];
int main()
{
	int n,x,y;
	sc(n);sc(x);sc(y);
	rep(i,1,n-1){
		rep(j,i+1,n){
			if(i<=x){
				if(j<=(x+y)/2)a[i][j]=j-i;
				else a[i][j]=x-i+1+abs(y-j);
			}else if(i<(x+y)/2){
				a[i][j]=min(j-i,i-x+1+abs(j-y));
			}
			else {
				a[i][j]=j-i;
			}b[a[i][j]]++;
			//pf("%d\n",a[i][j]);
		}
	}rep(i,1,n-1){
		pf("%d\n",b[i]);
	}
}


Measured memory_bytes: 15360
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, M, X = map(int, input().split())
A = list(map(int, input().split()))

masu = [0] * N
for a in A:
    masu[a] += 1

ans = min(sum(masu[:X]), sum(masu[X:]))
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)
int main()
{
    string sa, sb, sc;
    cin >> sa >> sb >> sc;
    char c = sa[0];
    sa.erase(sa.begin() + 0);
    while (1)
    {
        // cout << c << endl;
        if (c == 'a')
        {
            if (sa.empty())
            {
                cout << "A" << endl;
                break;
            }
            c = sa[0];
            sa.erase(sa.begin() + 0);
        }
        if (c == 'b')
        {
            if (sb.empty())
            {
                cout << "B" << endl;
                break;
            }
            c = sb[0];
            sb.erase(sb.begin() + 0);
        }
        if (c == 'c')
        {
            if (sc.empty())
            {
                cout << "C" << endl;
                break;
            }
            c = sc[0];
            sc.erase(sc.begin() + 0);
        }
    }
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define MOD 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//↑templete
#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
ll fact_mod(ll n, ll mod) {
    ll f = 1; repq(i,2,n) f = f * (i % MOD) % MOD;
    return f;
}
// 繰り返し二乗法 (再帰バージョン)
ll mod_pow(ll x, ll n, ll mod) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % mod, n / 2 , mod);
    if(n & 1) res = (res * x) % mod;
    return res;
}
// 組み合わせ nCr を求める (modあり)
ll combination_mod(ll n, ll r, ll mod) {
    if(r > n-r) r = n-r;
    if(r == 0) return 1;
    ll a = 1;
    rep(i, 0, r) a = a * ((n-i) % mod) % mod;
    ll b = mod_pow(fact_mod(r, mod), mod-2, mod);
    return (a % mod) * (b % mod) % mod;
}
signed main(){

	ll N, A, B;
	cin>>N>>A>>B;

	ll ans=mod_pow(2, N, MOD);
	(ans+=MOD-combination_mod(N, A, MOD))%=MOD;
	(ans+=MOD-combination_mod(N, B, MOD))%=MOD;

	cout<<ans-1LL<<endl;

	return 0;
}

Measured memory_bytes: 256
def run_length(a):
    result = []
    N = len(a)
    cnt = 1
    for i in range(N):
        if i == N - 1 or a[i] != a[i + 1]:
            result.append(cnt)
            cnt = 1
        else:
            cnt += 1
    return result

N = int(input())
a = list(map(int, input().split()))

print(sum(map(lambda x: x // 2, run_length(a))))

Measured memory_bytes: 3060
#include <iostream>
#include <map>
#include <ios>
#include <iomanip>
using namespace std;

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

    struct City {
        int pref;
        int year;
        int x;
    };
    City city[100010];
    map<int, map<int, int>> years;

    for (int i = 1; i <= M; i++) {
        int Pi, Yi;
        cin >> Pi >> Yi;
        city[i].pref = Pi, city[i].year = Yi;
        years[Pi][Yi] = i;
    }

    for (int Pi = 1; Pi <= N; Pi++) {
        int x = 1;
        for (auto year : years[Pi]) city[year.second].x = x++;
    }


    for (int i = 1; i <= M; i++) {
        cout << setfill('0') << right << setw(6) << city[i].pref;
        cout << setfill('0') << right << setw(6) << city[i].x;
        cout << endl;
    }
}

Measured memory_bytes: 15232
#include<cstdio>
#include<iostream>
using namespace std;
int s[31];
int main()
{
	int i,n,m,w,a,b,p;
	char d;
	cin>>w;
	for(i=1;i<=w;i++)s[i]=i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a>>d>>b;
		p=s[a];s[a]=s[b];s[b]=p;
	}
	for(i=1;i<=w;i++)cout<<s[i]<<endl;
	return 0;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int inf = 1e9;
double pi = 3.14159265359;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, b, a) for (int i = a - 1; i >= b; i--)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dxx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dyy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    ll a, b1, b2;
    char c;
    cin >> a >> b1 >> c >> b2;
    ll ans = a * b1 + (a * b2) / 100;
    cout << ans << "\n";
}

Measured memory_bytes: 3600
// https://atcoder.jp/contests/abc152/tasks/abc152_c

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

int main()
{
    long a, b;
    cin >> a >> b;
    long ans = 0;
    for (int x = a; x <= b; x++)
    {
        string s, t;
        s = to_string(x);
        t = s;
        reverse(t.begin(), t.end());
        if (s == t)
        {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3672
import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    N,M = map(int,input().split())
    print((N*(N-1)+M*(M-1))//2)

if __name__ == "__main__":
  main()


Measured memory_bytes: 21796
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
const int maxm=1e5+5;
const int mod=1e9+7;
int d[105][100005];
pair<int,int>p[maxm];
map<int,int>mark;
int n,k;
signed main(){
    cin>>n>>k;
    int m=0;
    for(int i=1,j;i<=n;i=j+1){
        j=n/(n/i);
        p[++m]={j,j-i+1};
        mark[j]=m;
    }
    for(int i=1;i<=m;i++){
        d[1][i]=(d[1][i-1]+p[i].second)%mod;
    }
    for(int i=2;i<=k;i++){
        for(int j=1;j<=m;j++){
            d[i][j]=(d[i][j-1]+p[j].second*d[i-1][mark[n/p[j].first]]%mod)%mod;
        }
    }
    cout<<d[k][m]<<endl;
    return 0;
}
/*

*/


Measured memory_bytes: 58236
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,M,X;
    cin>>N>>M>>X;
    vector<int> mp(N+1,0);
    REP(i,M){
        int k;cin>>k;
        mp[k]++;
    }
    int lcos=0,ucos=0;
    REP(i,N+1){
        if(i<=X&&mp[i]==1)lcos++;
        if(i>=X&&mp[i]==1)ucos++;
    }
    cout<<min(lcos,ucos)<<endl;
}

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

// ダイクストラ法
// 参照：蟻本　p97
// O(ElogV)
struct edge{int to,cost;};
typedef pair<int,int> P; // firstは最短距離、secondは頂点の番号

int V; // 頂点の数
vector<edge> G[100010];
int d[100010];

void dijkstra(int s){
    priority_queue<P,vector<P>, greater<P>> que;
    fill(d,d+V,INF);
    d[s]=0;
    que.push(P(0,s));

    while(!que.empty()){
        P p=que.top(); que.pop();
        int v=p.second;
        if(d[v]<p.first) continue;
        rep(i,G[v].size()){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

int main(){
    cin >> V;
    int x,y;
    cin>>x>>y;
    x--,y--;

    rep(i,V-1){
        G[i].push_back({i+1,1});
        G[i+1].push_back({i,1});
    }
    G[x].push_back({y,1});
    G[y].push_back({x,1});

    vector<int> ans(V,0);
    rep(i,V){
        dijkstra(i);
        for(int j=i+1;j<V;j++){
            ans[d[j]]++;
        }
    }
    
    for(int i=1;i<V;i++) cout<<ans[i]<<endl;
}




Measured memory_bytes: 2688
/*
char s[5];
scanf("%s",s);
int l;
l = strlen(s);
int d[5],i,j;
char ans[10];
REP(i,4)
{
	d[i] = s[i] - '0';
	ans[2*i] = s[i];
}
ans[7] = '=';
の様にしていたがうまくいかなかった。
*/
#include<stdio.h>
#define REP(i,n) for(i=0;i<n;i++)
int main(void)
{
	char a,b,c,d;
	scanf("%c%c%c%c",&a,&b,&c,&d);
	int i;
	REP(i,8)//可変であればbit探索
	{
		long long ans = a-'0';//ASCII code
		ans += ((i>>0)&1)? b-'0':'0'-b;
		ans += ((i>>1)&1)? c-'0':'0'-c;
		ans += ((i>>2)&1)? d-'0':'0'-d;
		if(ans==7)
		{
			printf("%c%c%c%c%c%c%c=7\n",a,((i>>0)&1)? '+':'-',b,((i>>1)&1)? '+':'-',c,((i>>2)&1)? '+':'-',d);
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>

int
main()
{
	int n;
	scanf("%d", &n);

	int i, x;
	for (i = 1; i <= n; i++)
	{
		if (i % 3 == 0)
		{
			printf(" %d", i);
			continue;
		}
		if (i % 10 == 3)
		{
			printf(" %d", i);
			continue;
		}

		x = i / 10;
		while (x != 0)
		{
			if (x % 10 == 3)
			{
				printf(" %d", i);
				break;
			}
			x /= 10;
		}
	}
	printf("\n");

	return 0;
}

Measured memory_bytes: 600
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(vec) (vec).begin(), (vec).end()
#define SUM(...) accumulate(ALL(__VA_ARGS__),0LL)
#define DSUM(...) accumulate(ALL(__VA_ARGS__),0.0)
using namespace std;
using ll = long long;
using P = pair<int, int>;

// 便利関数
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

// 出力
void print() { std::cout << '\n'; }
template <class T>void print(const T &x) {std::cout << x <<'\n';}
template <class T, class... Args>void print(const T &x, const Args &... args) {std::cout << x << " ";print(args...);}

const int INF = 2002002002;

void solve(long long A, long long B, long long C){
    if (A == B) print(C);
    if (A == C) print(B);
    if (B == C) print(A);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
	int N; cin >> N;
	vector<int> A(N, 0);
	for (int i = 0; i < N; i++) {
		int a; cin >> a; a--;
		A[a]++;
	}
	sort(A.begin(), A.end(), greater<int>());

	vector<int> B(N, 0);
	int c = 0;
	if (A[N - 1] == 1) { B[c] = N; c++; }
	for (int i = N - 2; i >= 0; i--) {
		if (A[i] != A[i + 1]) {
			while (c < A[i]) {
				B[c] = i + 1;
				c++;
			}
		}
	}
	vector<int> v(N, 0);
	int s = 0;
	for (int i = 0; i < N; i++) {
		s += B[i];
		v[i] = s / (i + 1);
	}

	c = N - 1;
	for (int i = 0; i < N; i++) {
		while (c >= 0 && v[c] < (i + 1)) { c--; }
		cout << c + 1 << endl;
	}

	return 0;
}

Measured memory_bytes: 4352
import java.util.ArrayDeque;
import java.util.Iterator;
import java.util.Scanner;

// Java8
public class Main
{
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) throws Exception
	{
		new Main().run();
	}
	
	void run()
	{
		int n = sc.nextInt();
		ArrayDeque<Integer> deq = new ArrayDeque<>(n+1);
		for(int i=0; i<n; i++)
		{
			int a = sc.nextInt();
			if((i&1)==0)
			{
				deq.offerLast(a);
			}
			else
			{
				deq.offerFirst(a);
			}
		}
		Iterator<Integer> itr = (n&1)==0 ? deq.iterator() : deq.descendingIterator();
		System.out.print(itr.next());
		while(itr.hasNext())
		{
			System.out.print(" ");
			System.out.print(itr.next());
		}
		System.out.println();
	}
}


Measured memory_bytes: 96156
s = input()

def kaibun(s):
    if len(s) % 2 == 1:
        l = len(s) //2
        return s[:l] == s[:l:-1]
    else:
        l = len(s) //2
        return s[:l] == s[:l-1:-1]
n = len(s)

if (kaibun(s) and kaibun(s[:n//2]) and kaibun(s[n//2 + 1:])):
    print("Yes")
else:
    print("No")


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

long long gcd(long long a, long long b) {
  if (b == 0) return a;
  gcd(b, a % b);
}

int main(void) {
  long long A, B, C, D;
  cin >> A >> B >> C >> D;
  long long lcm = C * D / gcd(max(C, D), min(C, D));

  cout << B - A + 1 -
              ((B / C - (A - 1) / C) + (B / D - (A - 1) / D) -
               (B / lcm - (A - 1) / lcm))
       << endl;
  return 0;
}

Measured memory_bytes: 256
/* ex_5-3. nknm */

#include <stdio.h>
#include <math.h>


int main(void){

    int ver, hor, count;
    char imput[100][100];
    int i, j, k, l;

    //マス目の数と記号を入力
    scanf("%d%d", &hor, &ver);

    for(i = 0; i < hor; i++){
        for(j = 0; j < ver ; j++){
            scanf(" %c", &imput[i][j]);
        }
    }

    
    count = 0;

    //ある列の記号を調べる
    for(j = 0; j < ver; j++){
        for(i = 0; i < hor; i++){
            if(imput[i][j] == '.'){
                count += 1;
            }
        }
        //列がすべて"."ならば１つ右の列をコピー
        if(count == hor){
            for(k = j; k < ver - 1; k++){
                for(i = 0; i < hor; i++){
                    imput[i][k] = imput[i][k + 1];
                }    
            }
            //最後の列は消去
            for(l = 0; l < hor; l++){
                imput[l][ver - 1] = ' ';
            }
            ver = ver - 1;
            j = j - 1;
        }
        count = 0;        
    }

    //上の操作を行についても行う
     for(i = 0; i < hor; i++){
            for(j = 0; j < ver; j++){
                if(imput[i][j] == '.'){
                    count += 1;
                }
            }
            if(count == ver){
                for(k = i; k < hor - 1; k++){
                    for(j = 0; j < ver; j++){
                        imput[k][j] = imput[k + 1][j];
                    }
                } 
                for(l = 0; l < ver; l++){
                    imput[hor - 1][l] = ' ';
                }
                hor = hor - 1;
                i = i - 1;
            }
            count = 0;        
    }

    //結果を出力
    for(i = 0; i < hor; i++){
        for(j = 0; j < ver; j++){
            printf("%c", imput[i][j]);

        }
        printf("\n");
    }

    return 0;
}

Measured memory_bytes: 128
// AtCoder Beginner Contest 124 - Problem A: Buttons (https://atcoder.jp/contests/abc124/tasks/abc124_a)
#include <iostream>

using namespace std;

int solve(int A, int B)
{
    return max(max(2*A - 1, 2*B - 1), A + B);
}

int main()
{
    int A, B;
    cin >> A >> B;

    cout << solve(A, B) << '\n';

    return 0;
}


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

int main() {
  int n,m;
  cin >> n >> m;
  vector<int> cnt_wa(n+1,0);
  vector<int> status(n+1,0);
  int wa = 0,ac = 0;
  rep(i,0,m) {
    int p; string s;
    cin >> p >> s;
    if (s == "AC") {
      if (status[p] != 2) {
        status[p] = 2;
        ac++;
      }
    } else {
      if (status[p] != 2) {
        status[p] = 1;
        cnt_wa[p]++;
        wa++;
      }
    }
  }
  rep(i,1,n+1) {
    if (status[i] == 1) {
      wa -= cnt_wa[i];
    }
  }
  cout << ac << " " << wa << endl;
  return 0;
}


Measured memory_bytes: 4040
#include <cstdio>

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

using namespace std;

int main(){
	for(int h,w=5;scanf("%d",&h),h;){
		int B[10][5];
		rep(i,h) rep(j,w) scanf("%d",B[i]+j);

		int ans=0;
		while(1){
			bool changed=false;

			// vanish
			for(int i=h-1;i>=0;i--){
				int cont=1;
				for(int j=1;j<=w;j++){
					if(j==w || B[i][j-1]!=B[i][j]){
						if(cont>=3 && B[i][j-1]!=0){
							ans+=B[i][j-1]*cont;
							rep(k,cont) B[i][j-k-1]=0;
							changed=true;
						}
						cont=1;
					}
					else cont++;
				}
			}

			// fall
			rep(j,w){
				rep(_,h) rep(i,h-1) {
					if(B[i][j]!=0 && B[i+1][j]==0) B[i+1][j]=B[i][j], B[i][j]=0;
				}
			}

			if(!changed) break;
		}
		printf("%d\n",ans);
	}

	return 0;
}

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

using namespace std;
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  for (int i = 0; i < k; ++i) {
    vector<int> b(n + 1);
    for (int j = 0; j < n; ++j) {
      int l = max(1, j + 1 - a[j]);
      int r = min(n, j + 1 + a[j]);
      b[l]++;
      if (r + 1 <= n)
        b[r + 1]--;
    }
    bool end = true;
    for (int j = 0; j < n; ++j) {
      b[j + 1] += b[j];
      a[j] = b[j + 1];
      if (a[j] != n)
        end = false;
    }
    if (end)
      break;
  }
  for (int i : a)
    cout << i << " ";
}


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

using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;



int main() {
    string s;
    cin >> s;

    if(s=="SUN") {
        cout << 7 << endl;
        return 0;
    } else if(s=="MON") {
        cout << 6 << endl;
        return 0;
    } else if(s=="TUE") {
        cout << 5 << endl;
    } else if(s=="WED") {
        cout << 4 << endl;
    } else if(s=="THU") {
        cout << 3 << endl;
    } else if(s=="FRI") {
        cout << 2 << endl;
    } else if(s=="SAT") {
        cout << 1 << endl;
    }

    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, start, end) for(int i = start; i < (int)(end); ++i)

int main(){
    string s;
    cin >> s;
    bool a = false, b = false;
    for(char c: s){
        if(c == 'A') a = true;
        if(c == 'B') b = true;
    }
    if(a & b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
H, W, A, B = map(int, input().split())
ans = [[0 for w in range(W)] for h in range(H)]
for i in range(B):
    for j in range(A):
        ans[i][j] = 1
    print(''.join(map(str, ans[i])))
for i in range(B, H):
    for j in range(A, W):
        ans[i][j] = 1
    print(''.join(map(str, ans[i])))

Measured memory_bytes: 84144
#include<stdio.h>

int main(){
  int a,b;
  double a1,b1;
  int d,r;
  double f;

  scanf("%d %d",&a,&b);

  a1=a;
  b1=b;
  d=a/b;
  r=a%b;
  f=a1/b1;
  printf("%d %d %lf\n",d,r,f);

  return 0;
}
  
	

Measured memory_bytes: 636
/* {{{ Shinobu kawaii */
/*
  ______   __        _                  __                 
.' ____ \ [  |      (_)                [  |                
| (___ \_| | |--.   __   _ .--.   .--.  | |.--.   __   _   
 _.____`.  | .-. | [  | [ `.-. |/ .'`\ \| '/'`\ \[  | | |  
| \____) | | | | |  | |  | | | || \__. ||  \__/ | | \_/ |, 
 \______.'[___]|__][___][___||__]'.__.'[__;.__.'  '.__.'_/ 

*/
/* }}} */

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

// #define int long long

/* cpp template {{{ */

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()
#define X Fi
#define Y Se

/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

/* typedef */
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;
typedef pair<int, int> pii;
typedef double D;

/* const */
const int INF = 999999999;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* class */
class P {
  public:
    D x, y;
    P(D x, D y) { this->x = x; this->y = y; }
    P operator+ (P a) { return P(this->x + a.x, this->y + a.y); }
    P operator- (P a) { return P(this->x - a.x, this->y - a.y); }
};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; std::cin >> x; return x;}
inline D dot(P a, P b) { return a.x * b.x + a.y * b.y; }
inline D cross(P a, P b) { return a.x * b.y - a.y * b.x; }
template <typename T> void print(T x) { std::cout << x << '\n'; }
template <typename T>
void print(std::vector<T>& v, char c = ' ') {
  REP(i, v.size()) {
    if (i != 0) std::cout << c;
    std::cout << v[i];
  }
  std::cout << '\n';
}

/* }}} */

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

  int n = in(), m = in();
  vector<pii> v(n + 1, mp(0, 1));
  v[1].Fi = -1;
  REP(i, m) {
    int a = in(), b = in();
    v[a].Se--; v[b].Se++;
    if (v[a].Fi == -1) {
      v[b].Fi = -1;
    }
    if (v[a].Se == 0) {
      v[a].Fi = 0;
    }
  }
  int ans = 0;
  RREP(i, n) {
    if (v[i].Fi == -1 && v[i].Se > 0) ans++;
  }
  print(ans);

  return 0;
}



Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int n, c2, c5, t;
  while (scanf("%d", &n) && n) {
    c2 = c5 = 0;
    t = 2;
    while (t <= n) {
      c2 += n / t;
      t *= 2;
    }
    t = 5;
    while (t <= n) {
      c5 += n / t;
      t *= 5;
    }
    printf("%d\n", min(c2, c5));
  }
  return 0;
}

Measured memory_bytes: 1028
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n; cin >> n;
	vector<int> a(n), b(n), c(n);
	rep(i, n)cin >> a[i];
	sort(all(a));
	rep(i, n)cin >> b[i];
	rep(i, n)cin >> c[i];
	sort(all(c));
	ll res = 0;
	rep(i, n)
	{
		ll acnt = lower_bound(all(a), b[i]) - a.begin();
		ll ccnt = c.end() - upper_bound(all(c), b[i]);
		res += acnt * ccnt;
	}
	cout << res << endl;
}

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

int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	cout << x2 - (y2 - y1) << " " << y2 + (x2 - x1) << " " << x2 - (y2 - y1) - (x2 - x1) << " " << y2 + (x2 - x1) - (y2 - y1);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>

#define MAX_N 100000
#define MAX_K 100000

#define REP(i, N) for (int i = 0; i < (int)(N); ++i)

int N, K;
int dp[MAX_N];

void solve()
{
  dp[0] = 0;
  for (int i = 1; i <= N; ++i) {
    int sum = i;
    int cnt = 0;
    while (sum < K) {
      sum = sum * 2;
      cnt++;
    }
    dp[i] = cnt;
  }
  double result = 0.0;
  for (int i = 1; i <= N; ++i) {
    result += pow(0.5, dp[i]);
  }
  printf("%.11f\n", result * 1.0 / (double)N);
}

int main(void)
{
  scanf("%d %d", &N, &K);
  solve();
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
//#include <set>
//#include <map>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
//#include <vector>
#include <string>
//#include <unordered_map>
//typedef long long LL;
//typedef long double LD;
using namespace std;

//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

int main() {
    string n;
    cin >> n;
    for(int i=0; i<n.size(); i++){
        if(n[i]=='1'){
            n[i]='9';
        }else{
            n[i]='1';
        }
    }
    cout << n << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>  
int main(void)
{
   int a, b;
   scanf("%d %d", &a, &b);
   if ( a < b ) {
     printf("a < b\n");
   } else if(a > b){
     printf("a > b\n");
   } else{
     printf("a == b\n");
   }
   return 0;
}

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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define all(v) (v).begin(), (v).end()

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n,minus=0,minn=INF,ans=0;
  cin >> n;
  vector<ll> a(n);
  rep(i,n){
    cin >> a[i];
    if(a[i]<0) minus++;
    ans += abs(a[i]);
  }
  if(minus%2){
    rep(i,n){
      if(minn > abs(a[i])) minn = abs(a[i]);
    }
    ans -= minn*2;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
#include<vector>
#define int long long int
#define inf 1000000000000000
int function(int arr[],int initial,int final,int curr,int memo[][3])
{
	if(initial>final)
	{
		if(curr==2)
		{
			return -inf;
		}
		if(curr==1&&initial==final+3)
		{
			return -inf;
		}
		else
		  return 0;
	}
	if(memo[initial][curr]!=-1)
	  return memo[initial][curr];
	else
	{
		if(curr==0)
		{
			int val=arr[initial]+function(arr,initial+2,final,curr,memo);
			memo[initial][curr]=val;
			return memo[initial][curr];
		}
		else
		{
			int val1=arr[initial]+function(arr,initial+2,final,curr,memo);
			int val2=arr[initial]+function(arr,initial+3,final,curr-1,memo);
			memo[initial][curr]=max(val1,val2);
			return memo[initial][curr];
		}
	}
}
int function2(int arr[],int initial,int final,int curr,int memo[][2])
{
	if(initial>final)
	{
        if(curr==1)
        {
			return -inf;
		}
		if(curr==0&&initial==final+4)
		{
			return -inf;
		}
		return 0;
    }
    if(memo[initial][curr]!=-1)
      return memo[initial][curr];
    else
    {
		if(curr==0)
		{
			
			int x=arr[initial]+function2(arr,initial+2,final,curr,memo);
			memo[initial][curr]=x;
			return memo[initial][curr];
		}
		else
		{
			int x=arr[initial]+function2(arr,initial+2,final,curr,memo);
			int y=arr[initial]+function2(arr,initial+4,final,curr-1,memo);
			memo[initial][curr]=max(x,y);
			return memo[initial][curr];
		}
	}
}
int32_t main()
{
		int n;
		cin>>n;
		int arr[n+1];
		int j;
		for(j=1;j<=n;j++)
		{
			cin>>arr[j];
		}
		int memo[n+1][3];
		int i;
		for(i=0;i<=n;i++)
		{
			for(j=0;j<3;j++)
			{
				memo[i][j]=-1;
			}
		}
		if(n%2==0)
		{
			int val1=function(arr,1,n,1,memo);
			int val2=function(arr,2,n,0,memo);
			cout<<max(val1,val2)<<endl;
		}
		else
		{
			int val1=function(arr,1,n,2,memo);
			int val2=function(arr,2,n,1,memo);
			int val3=function(arr,3,n,0,memo);
			int answer2=max(val1,max(val2,val3));
			int memo2[n+1][2];
			for(i=0;i<=n;i++)
			{
				memo2[i][0]=-1;
				memo2[i][1]=-1;
			}
			int val4=function2(arr,1,n,1,memo2);
			answer2=max(answer2,val4);
			cout<<answer2<<endl;
		}
}


Measured memory_bytes: 22392
#include<stdio.h>
#define N 100
#define White 0
#define Gray 1
#define Brack 2

int n,A[N][N],c[N],d[N],f[N],t;

void dfsst(int x){
  int v;
  c[x]=Gray;
  d[x]=++t;
  for(v=0;v<n;v++){
    if(A[x][v]==0)continue;
    if(c[v]==White){
      dfsst(v);
    }
  }
  c[x]=Brack;
  f[x]=++t;
}

void dfs(){
  int i;
  for(i=0;i<n;i++){
    c[i]=White;
  }
  t=0;

  for(i=0;i<n;i++){
    if(c[i]==White)dfsst(i);
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
}
int main(){
  int u,v,k,i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      A[i][j]=0;
           }
    }
    for(i=0;i<n;i++){
      scanf("%d %d",&u,&k);
      u--;
      for(j=0;j<k;j++){
        scanf("%d",&v);
        v--;
        A[u][v]=1;
      }
    }
    dfs();

    return 0;
  }






Measured memory_bytes: 2060
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<type_traits>
#include<numeric>
#include<deque>
#include<limits>
#include<iomanip>
#include<set>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long long int ll;

//define
#define INF 100000000
#define NUM 1000000007
#define all(x) begin(x), end(x)

int main() {
	int n;
	cin >> n;
	ll a;
	deque<ll> dq;
	cin >> a;
	dq.push_back(a);
	if (n % 2 == 0) {
		for (int i = 1; i < n; i++) {
			cin >> a;
			if (i % 2 == 0) {
				dq.push_back(a);
			} else {
				dq.push_front(a);
			}
		}
	}else {
		for (int i = 1; i < n; i++) {
			cin >> a;
			if (i % 2 == 0) {
				dq.push_front(a);
			} else {
				dq.push_back(a);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		cout << dq[i];
		if (i != n - 1) {
			cout << " ";
		}else {
			cout << "\n";
		}
	}
	return 0;
}

Measured memory_bytes: 3840
#include <iostream>
#include <iomanip>
#include <vector>
using ld = long double;
int main()
{
    int N;
    std::cin >> N;
    std::vector<ld> p(N);
    for (int i = 0; i < N; i++) { std::cin >> p[i]; }
    std::vector<ld> P(N + 1, 0);
    P[0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = i; j >= 0; j--) { P[j + 1] += P[j] * p[i], P[j] = P[j] * (1 - p[i]); }
    }
    ld ans = 0;
    for (int i = (N + 1) / 2; i <= N; i++) { ans += P[i]; }
    std::cout << std::fixed << std::setprecision(15) << ans << std::endl;
    return 0;
}


Measured memory_bytes: 384
//
// Created by 10940 on 2020/7/25.
//

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

const int MAX_N = 1e5;

int main() {
    int x;
    cin >> x;
    if (x >= 30) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }



    return 0;
}

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

#define MAXN 200005

using namespace std;

int n, a[MAXN], b[MAXN], maxi;

int read() {
	char c = getchar();
	int x = 0;
	while (!isdigit(c))
		c = getchar();
	while (isdigit(c)) {
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x;
}

bool check(int w) {
	for (int i = 1; i <= 2 * n - 1; ++i) 
		b[i] = a[i] >= w;
	for (int i = 0; i < n - 1; ++i)
		if ((b[n - i] && b[n - i - 1]) || (b[n + i] && b[n + i + 1]))
			return true;
		else if ((!b[n - i] && !b[n - i - 1]) || (!b[n + i] && !b[n + i + 1]))
			return false;
	return b[1];
}

int solve() {
	int l = 1, r = 2 * n - 1, res = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			res = mid;
			l = mid + 1;
		}
		else 
			r = mid - 1;
	}
	return res;
}

int main() {
	n = read();
	for (int i = 1; i <= 2 * n - 1; ++i) 
		maxi = max(maxi, a[i] = read());
	int ans = solve();
	printf("%d\n", ans);
}

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

int main() {
  int N;
  cin >> N;
  vector<int> w(N);
  for (auto&& w_ : w)
    cin >> w_;
  
  const int sum = accumulate(w.begin(), w.end(), 0);
  int ad = sum, s = 0;
  for (int i = 0; i < w.size(); ++i) {
    s+=w[i];
    ad = min(ad, abs(sum - 2*s));
  }
             
  cout << ad << endl;
  return 0;
}

Measured memory_bytes: 256
#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>;

const long long mod = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> s(m);
    vector<int> p(m);
    rep(i, m) {
        int k;
        cin >> k;
        s[i].resize(k);
        rep(j, k) cin >> s[i][j];
    }

    rep(i, m) cin >> p[i];

    int ans = 0;
    for(int bit = 0; bit < (1 << n); ++bit) { //スイッチの組み合わせを生成
        vector<int> on(m);
        rep(i, m) { //各電球について
            vector<int> cnt(n);
            for(int j = 0; j < n; ++j) { //ビットを取り出す位置j
                if(bit & (1 << j)) { // j番目のビットが立っているなら
                    rep(k, s[i].size()) { // sにつながっているか確認
                        if(s[i][k] == j + 1)
                            cnt[i] += 1;
                    }
                }
            }
            // onのスイッチの数によって点灯
            if(cnt[i] % 2 == p[i]) {
                on[i] = 1;
            }
        }
        //全て点灯なら++
        if(accumulate(on.begin(), on.end(), 0) == m) {
            ans++;
        }
        //cout << accumulate(on.begin(), on.end(), 0) << endl;
    }

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

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

int main() {
    ll H;
    cin >> H;
    ll N = 1;
    ll ans = 0;
    while (H > 0) {
        ans += N;
        H /= 2;
        N *= 2;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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 (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;
vector<int>x;
template <class Monoid>
class SegmentTree
{
public:
  using Func = function<Monoid(Monoid, Monoid)>;
  const Func F;
  const Monoid M1;
  int sz;
  vector<Monoid> seg;

  SegmentTree(int n,const Func fu, const Monoid &m1): F(fu) , M1(m1) {init(n);}
  void init(int n)
  {
      sz= 1;
      while (sz < n) sz *= 2;
      seg.assign(sz * 2, M1);
  }
  void update(int k,const Monoid &x)
  {
    k+=sz;
    seg[k]=x;
    while(k>>=1)
    {
      seg[k]=F(seg[k*2],seg[k*2+1]);
    }
  }
  Monoid query(int l,int r)
  {
    Monoid L=M1,R=M1;
    l+=sz;r+=sz;
    for(;l<r;l>>=1,r>>=1)
    {
      if(l&1)L=F(L,seg[l++]);
      if(r&1)R=F(seg[--r],R);
    }
    return F(L,R);
  }
};
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,q,a,b;
  cin>>n>>q>>a>>b;
  a--;b--;
  x.resize(q);
  rep(i,q){cin>>x[i];x[i]--;}
  SegmentTree<ll> seg1(n+1,[](ll a,ll b){return min(a,b);},1e16),
                  seg2(n+1,[](ll a,ll b){return min(a,b);},1e16);
  rep(i,n)
  {
    ll f1=min(abs(a-i)+abs(b-x[0]),abs(b-i)+abs(a-x[0]));
    seg1.update(i,f1+n-i-1);
    seg2.update(i,f1+i+1);
  }
  ll dans=0;
  repi(i,1,q)
  {
    dans+=abs(x[i]-x[i-1]);
    ll next=min(seg1.query(0,x[i])-n+x[i]+1,seg2.query(x[i],n)-x[i]-1);
    next-=abs(x[i]-x[i-1]);
    seg1.update(x[i-1],next+n-x[i-1]-1);
    seg2.update(x[i-1],next+x[i-1]+1);
  }
  ll ans=1e16;
  rep(i,n)
  {
    chmin(ans,seg2.query(i,i+1)-i-1);
  }
  cout<<dans+ans<<endl;



  return 0;

}


Measured memory_bytes: 9216
N = int(input())
S = input()
X = [0] * 10
Y = [0] * 100
Z = [0] * 1000

for i in range(N):
    k = int(S[i])
    for j in range(100):
        if Y[j]:
            Z[j*10+k] = 1
    for j in range(10):
        if X[j]:
            Y[j*10+k] = 1
    X[k] = 1

print(sum(Z))

Measured memory_bytes: 42732
#include <stdio.h>
 
int main(){
int N;
int i;
scanf("%d",&N);
int A[N];
for(i = 0; i<N ;i++){
scanf("%d",&A[i]);
}
int max=A[0];
int min=A[0];
for(i = 0; i<N ;i++){
  
if(A[i]>max){
  max=A[i];
}
if(A[i]<min){
  min=A[i];
}
}
printf("%d\n",max-min);
return 0;
}

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

int main(){
  int N,M;
  cin >> N>>M;
  int X=1,Y=N;
  for(int i=0;i<M;i++){
    int L,R;
    cin>>L>>R;
    
    if(X<L){
      X=L;
    }
    if(R<Y){
      Y=R;
    }
  }
  
  if(Y-X+1>0){
  cout << Y-X+1 << endl ;
  }
  else{
    cout << 0 << endl;
  }
    
}

Measured memory_bytes: 256