akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <sstream> //string stream its useful!
#include<string>
#include<iostream>
#include<utility> //pair
#include <vector> // vector
#include <algorithm>    // swap,sort,binary_search
#include <functional>   // std::greater
#include <map> //map
#include<set> //set
#include<queue> //queue
#include<list> //list
#include<cmath>
#include<numeric>
#include<cassert>
#include <iomanip> //cout<<setprecision
#include <regex>



typedef long long ll;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
ll W = 1000000007;


using namespace std;
void omajinai() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<setprecision(15);
    //freopen("txt.csv","r",stdin);
}

class Main{
public:
    static void printYN(bool b){
        cout<<(b ? "YES" : "NO")<<endl;
    }
    
    int N;
    vector<ll> a;
    
    Main(){
        cin>>N;
        a = vector<ll>(N);
        REP(i,N) cin>>a[i];
    }
    
    void run(){
        vector<ll> sum(N),sa(N);
        ll m = accumulate(a.begin(),a.end(),0LL);
        sum[0] = a[0];
        
        FOR(i,1,N) sum[i] = sum[i-1] + a[i];
        REP(i,N) sa[i] = abs(m- sum[i] -sum[i]);
        cout<<*min_element(sa.begin(),sa.end()-1)<<endl;
    }
};

int main(){
    omajinai();
    Main().run();
    
}


Measured memory_bytes: 4992
#include <iostream>
using namespace std;
int dice[3];
int main() {
	while(true){
	int N,sum=0,l;
	dice[0]=1;
	dice[1]=2;
	dice[2]=3;
	string aim;
	cin >> N;
	if(N==0)
		break;
	for(int i=0;i<N;i++){
		cin >> aim;
		int w,x;
		if(aim=="East"){
			w=2;
			x=0;
		}
		else if(aim=="West"){
			w=0;
			x=2;
		}
		else if(aim=="North"){
			w=0;
			x=1;
		}
		else if(aim=="South"){
			w=1;
			x=0;
		}
		else if(aim=="Right"){
			w=1;
			x=2;
		}
		else if(aim=="Left"){
			w=2;
			x=1;
		}
		l=7-dice[w];
		dice[w]=dice[x];
		dice[x]=l;
		sum+=dice[0];
	}
	
		
	cout << sum+1 << endl;
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 1212
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;


class Main{

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		final int NUM = 28;
		final int NUMs = 30;
		ArrayList<Integer> al = new ArrayList<Integer>();
		HashSet<Integer> h = new HashSet<Integer>();
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		for(int i = 0; i < NUM ;i++){
			h.add(Integer.parseInt(in.readLine()));
		}
		for(int i= 0;i < NUMs ;i++){
			if(!h.contains(i+1)){
				System.out.println(i+1);
			}
		}
	}

}

Measured memory_bytes: 16872
local n, k, l = io.read("*n", "*n", "*n")

local function uf_initialize(n)
  local parent = {}
  for i = 1, n do parent[i] = i end
  return parent
end

local function uf_findroot(idx, parent)
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

local p1 = uf_initialize(n)
for i = 1, k do
  local p, q = io.read("*n", "*n")
  local pr, qr = uf_findroot(p, p1), uf_findroot(q, p1)
  p1[qr], p1[q] = pr, pr
end

local p2 = uf_initialize(n)
for i = 1, l do
  local r, s = io.read("*n", "*n")
  local rr, sr = uf_findroot(r, p2), uf_findroot(s, p2)
  p2[sr], p2[s] = rr, rr
end

local group = {}
for i = 1, n do
  local r1, r2 = uf_findroot(i, p1), uf_findroot(i, p2)
  if not group[r1] then group[r1] = {} end
  if not group[r1][r2] then
    group[r1][r2] = 1
  else
    group[r1][r2] = group[r1][r2] + 1
  end
end
for i = 1, n do
  local r1, r2 = uf_findroot(i, p1), uf_findroot(i, p2)
  io.write(group[r1][r2])
  io.write(i == n and "\n" or " ")
end


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

#define int long long
#define double long double

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;
using P = pair<int, int>;
using ll=long long;
using ld=double;

constexpr int MOD = 1e9+7;

template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

// https://twitter.com/vane11ope ←フォローしましょう
// (ノ)>◡<(ヾ)ﾓﾁﾓﾁ
signed main(signed argc, char* argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    cout<<(1000-n%1000)%1000<<endl;
}


Measured memory_bytes: 3608
from itertools import accumulate
from collections import Counter
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0, ] + list(accumulate(A))
    c = Counter(B)
    ans = 0
    for k, v in c.items():
            ans += v * (v - 1) // 2
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 44472
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {


    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);

        long n = s.nextInt(),x=s.nextInt();
        n*=500;
        if(n>=x) System.out.println("Yes");
        else System.out.println("No");


    }




}


class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {return Integer.parseInt(next());}

    public long nextLong() throws IOException {return Long.parseLong(next());}

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25324
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #arr=list(map(int, readline().rstrip().split()))
    n=int(readline())
    mod=10**9+7
    p10=pow(10,n,mod)+mod*5
    p8=pow(8,n,mod)
    p9=pow(9,n,mod)
    ans=p10+p8-p9-p9
    ans=ans%mod


    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Measured memory_bytes: 16208
#include<iostream>
#include<algorithm>
using namespace std;
int num[100010];
#define ll long long 
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
    }
    sort(num+1,num+1+n);
    ll cnt=0;
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=j+1;k<=n;k++)
            {
                if(num[i]+num[j]>num[k])
                {
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 888
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int Path[26][200010];
int From[200010];
string A;
void dp(){
    for(int i = 0; i < 200010; i++)From[i] = -1;
    A = "#" + A;
    int L = A.size();
    for(int i = 0; i < 26; i++){
        Path[i][L-1] = 200005;
        for(int j = L-1; j > 0; j--){
            if(A[j] - 'a' == i)Path[i][j-1] = j;
            else Path[i][j-1] = Path[i][j];
        }
    }
}
int main(){
    cin >> A;
    dp();
    queue<int>Q;
    Q.push(0);
    while(true){
        int pos = Q.front();
        Q.pop();
        if(pos == 200005)break;
        for(int i = 0; i < 26; i++){
            if(From[Path[i][pos]] != -1)continue;
            From[Path[i][pos]] = pos;
            Q.push(Path[i][pos]);
        }
    }
    string ans = "";
    for(int pos = 200005; pos; pos = From[pos]){
        for(int i = 0; i < 26; i++){
            if(Path[i][From[pos]] == pos){
                ans += string(1, 'a'+i);
                break;
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 21696
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,h,i,j,k,l,m,n,x,y,r,w;
	ll		ans = 0;
	string	s;
	cin >> n >> s;
	r = w = 0;
	for(i=0;i<n;i++) {
		if (s[i]=='R') r++;
		else w++;
	}
	if (r==n || w==n) {
		ans = 0;
	} else {
		i = 0;
		j = n-1;
		while(1) {
			while(s[i]=='R'&&i<n-1) i++;
			while(s[j]=='W'&&j>0) j--;
			if (i>j) break;
			ans++;
			swap(s[i],s[j]);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
constexpr const int INF=1<<30,MOD=1000000007;constexpr const ll LINF=1ll<<60;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,v.size())
#define all(v)(v).begin(),(v).end()
#define bit(n)(1ll<<(n))
#define uniq(v)sort(all(v));v.erase(unique(all(v)),v.end())
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
#ifndef LOCAL
struct osd{template<class T>osd&operator<(const T&t){return*this;}template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;template<class...T>void _print(osd&a,T&&...t){}
#define cerr cer_
#endif
template<class T>ostream&operator<(ostream&o,const T&t){return o<<t;}template<class T>istream&operator>(istream&i,T&t){return i>>t;}
void _print(ostream&s){}template<class T,class...U>void _print(ostream&s,T&&t,U&&...u){s<t<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(T&&...t){_print(cout,t...);}template<class...T>void dprint(T&&...t){_print(cerr,t...);}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&v){for(auto&&i:v)o<i<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>j;return i;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<p.F<' '<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>p.F>p.S;}
template<class T>ostream&operator<<(ostream&o,const set<T>&v){for(auto&&i:v)o<i<' ';return o;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>queue<T>&operator<<(queue<T>&q,const T&t){q.push(t);return q;}template<class T>queue<T>&operator<<(T&t,queue<T>&q){t=q.front();q.pop();return q;}
template<class T>deque<T>&operator>>(const T&t,deque<T>&q){q.push_front(t);return q;}template<class T>deque<T>&operator<<(T&t,deque<T>&q){t=q.front();q.pop_front();return q;}
template<class T>deque<T>&operator<<(deque<T>&q,const T&t){q.push_back(t);return q;}template<class T>deque<T>&operator>>(deque<T>&q,T&t){t=q.back(t);q.pop_back();return q;}
template<class T>stack<T>&operator<<(stack<T>&s,const T&t){s.push(t);return s;}template<class T>stack<T>&operator>>(stack<T>&s,T&t){t=s.top();s.pop();return s;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    string s;
    cin>s;
    bool flag=false;
    REP(i,3){
        if(s[i]==s[i+1])flag=true;
    }
    if(flag){
        cout<<"Bad\n";
    }else{
        cout<"Good\n";
    }
    return 0;
}


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

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

	string ans = "AC";
	if( S[0] != 'A' ) ans = "WA";
	else {
		string s = S.substr( 2, S.size() - 2 - 1 );
		int n = s.find( 'C' );
		if( n == string::npos ) ans = "WA";
		else if( s.find( 'C', n + 1 ) != string::npos ) ans = "WA";
		else {
			for( int i = 0; i < S.size(); i++ ) {
				if( i == 0 || S[i] == 'C' && 2 <= i && i <= S.size() - 2 ) continue;
				if( islower( S[i] ) == false ) ans = "WA";

			}
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define lli unsigned long long
#define rep0(i,j) for(int i=0; i<j; i++)
#define rep1(i,j) for(int i=1; i<=j; i++)
#define all(a) a.begin(), a.end()
using namespace std;

void dfs(lli ed, lli num, vector<map<lli,lli>>& vec){
    lli n=1;
    for(auto e: vec[num]){
        if(n == ed)n++;
        if(e.second != -1)continue;
        vec[num][e.first] = n;
        vec[e.first][num] = n;   
        dfs(n, e.first, vec);
        n++;
    }
}

int main(){
    lli a,b;
    cin >> a >> b;
    lli ans=0, ad = ((a >> 1) & 1) ^ (a & 1), bd = ((b >> 1) & 1) ^ (b & 1);
    for(int i=1, temp = 2; a >= temp; i++){
        temp <<= 1;
        ad += (a % temp) & (!(a&1) * (temp >> 1));
    }
    for(int i=1, temp = 2; b >= temp; i++){
        temp <<= 1;
        bd += (b % temp) & (!(b&1) * (temp >> 1));
    }
    cout <<(bd ^ ad ^ a);

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define INF (ll)1e18+7
#define md (ll)1e9+7
#define mk make_pair
#define pi pair<int,int>
#define pb emplace_back 
#define all(s) s.begin(),s.end()
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define sz(x) ((long long)x.size())
#define mez(s) memset(s,0,sizeof s)
#define mex(s) memset(s,-1,sizeof s)
typedef vector<int> vi; 
typedef vector<ll>vl;
typedef map<int,int> mp;
typedef queue<int> que;
typedef vector<pi> vp;




void solve(){
int n;
cin>>n;
vi a(n+1);
int k=0;
fr(i,1,n){
	cin>>a[i];
	if(a[i]%2&&i%2)
	k++;
}
cout<<k<<"\n";



}



int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
   int t=1;
  //cin>>t;
     while(t--){
     	solve();
	 }
     return 0;
}

Measured memory_bytes: 3640
//Coded by Abhijay Mitra
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <numeric>
#include <vector>
#include <iterator> 
#include <map>
#include <set>
#include <climits>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <bitset>
// #include <bits/stdc++.h>
#define double long double
#define int long long int
#define ll int
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define bp __builtin_popcount
#define pb push_back
#define res(v) v.resize(unique(v.begin(), v.end()) - v.begin());
#define cnt_res(v) std::distance(v.begin(),std::unique(v.begin(), v.end())); 
#define timer cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using pii = std::pair<int,int>;
using vpii = std::vector<pii>;
using vvpii = std::vector<vpii>;
#define mp         make_pair
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,b,a) for (int i = b; i >= a; i--)
#define all(x)     x.begin(), x.end()
using namespace std;
const int N=5e2+10;
const int inf = /*0x3f3f3f3f*/1e18+10;
// const ll M = 998244353 ; // Mulo
const int M = 1e9+7 ; // Mulo
const double Pi = 3.14159265;
#define F first
#define S second
int mul(int a,int b){
  return ((a%M)*(b%M))%M;
}
int add(int a,int b){
  return ((a%M)+(b%M))%M;
}
int n;
vvi p(vvi a,vvi b){
  vvi x(n,vi(n,0));
  rep(i,0,n-1)
    rep(j,0,n-1)
      rep(k,0,n-1)
        x[i][j]=add(x[i][j],mul(a[i][k],b[k][j]));
  return x;
}
vvi a;
//this return pow(A,x) where A is matrix
vvi matrix_power_final(vvi A, int x){
  vvi result(n,vi(n,0));
  rep(i,0,n-1)result[i][i]=1;
  while(x){
    if (x&1)result = p(result , A);
    A = p(A , A);
    x = x / 2;
  }
  return result;
}
void solve(){
  int k;cin>>n>>k;a=vvi(n,vi(n,0));
  rep(i,0,n-1)rep(j,0,n-1)cin>>a[i][j];
  a=matrix_power_final(a,k);
  int ans=0;
  rep(i,0,n-1)rep(j,0,n-1)ans=add(ans,a[i][j]);
  cout<<ans;
}
int32_t main()
{
  ibs;cti;
  solve()
  /*,cout<<"\n"*/;
  // cout<<"\n";
  int xx=0;
  // int t;cin>>t;while(t--){/*xx++;cout<<"Case "<<xx<<":\n"*/;solve();cout<<"\n";}
  return 0;
}

Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
 
int main() {
long long N;
  cin >> N;
 for(int a = int(sqrt(N));a >= 1;a--){
  if(N % a == 0){
   cout << a + N/a -2<< endl;
    break;
  }
 }
}

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

int main() {
	int h, w;
	std::cin >> h >> w;
	std::vector <std::string>s(h);
	for (int i = 0; i < h; i++) std::cin >> s[i];
	std::vector<std::vector<int>>score(h, std::vector<int>(w, -1));

	score[0][0] = 1;
	std::queue<std::pair<int, int>>q;
	int dx[4] = { 0,0,1,-1 };
	int dy[4] = { 1,-1,0,0 };
	q.push(std::make_pair(0, 0));
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx == -1 || nx == w || ny == -1 || ny == h)continue;
			if (s[ny][nx] == '#')continue;
			if (score[ny][nx] >= 0)continue;
			score[ny][nx] = score[y][x] + 1;
			q.push(std::make_pair(nx, ny));
		}
	}
	int white = 0;
	for (int i = 0; i < h*w; i++)white += s[i / w][i%w] == '.' ? 1 : 0;
	if (score[h - 1][w - 1] == -1)white = -2;
	printf("%d\n", white - score[h - 1][w - 1]);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main(void)
{
    int N;
    cin >> N;
    
    vector<string> S(N);
    map<string, int> mp;
    for (int i = 0; i < N; i ++) {
        cin >> S[i];
        mp[S[i]] ++;
    }
    
    cout << mp.size() << endl;
    
    
}

Measured memory_bytes: 24996
from copy import deepcopy
N, M = map(int, input().split())
graph = dict()
for i in range(N):
    graph[i] = []
ab = [tuple(map(int, input().split())) for _ in range(M)]

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse import csr_matrix
inf = float("inf")

graph = np.zeros((N, N))

for a, b in ab:
    graph[a - 1][b - 1] = 1
counter = 0
for a, b in ab:
    g = deepcopy(graph)
    g[a - 1][b - 1] = 0
    g = csr_matrix(g)
    shortest_paths = shortest_path(g, directed=False, method="D")
    if inf in shortest_paths[0]:
        counter += 1
print(counter)


Measured memory_bytes: 17268
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int n;
  int a,ans=0;
  map<int,int> d;
  vector<int> v,c;
  int da[1000005]={};
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    d[a]++;
    if(d[a]==1) v.push_back(a);
  }
  for(int i=0;i<v.size();i++){
    for(int j=v[i];j<=1000000;j+=v[i]){
      da[j]+=d[v[i]];
    }
  }
  sort(v.begin(),v.end());
  for(int i=1;i<=v[v.size()-1];i++){
    if(da[i]==1){
      if(d[i]!=0) c.push_back(i);
    }
  }
  cout<<c.size()<<"\n";
}

Measured memory_bytes: 51452
def main():
    S = input()
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    pow2 = [2**i for i in range(26)]
    S = [pow2[a[i]] for i in S]

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= s
        if parity in dict_parity:
            ans = min(i+1, dict_parity[parity]+1)
        else:
            ans = i+1
        ans = min(
            [ans]+[dict_parity.get(parity ^ j, ans)+1 for j in pow2])
        dict_parity[parity] = min(ans, dict_parity.get(parity, ans))
    print(ans)


main()

Measured memory_bytes: 34460
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<pair<int,pair<int,int> > > abc(n);
	vector<int> a(n),b(n),c(n);
	long long ans=0;
	for(int i=0;i<n;i++)
	{
		cin >> a[i];
		a[i]--;
	}
	for(int i=0;i<n;i++)
	{
		cin >> b[i];
	}
	for(int i=0;i<n-1;i++)
	{
		cin >> c[i];
	}
	for(int i=0;i<n;i++)
	{
		//abc[i]=make_pair(a[i],make_pair(b[i],c[i]));
		ans+=b[a[i]];
		if(a[i]<n-1 and a[i+1]==a[i]+1)
			ans+=c[a[i]];
	}
	
	cout << ans << endl;





}

Measured memory_bytes: 256
n = int(input())
a = [0]*n
b = [0]*n
c = []
for i in range(n):
    a[i],b[i] = input().split()
    c.append([a[i],100-int(b[i])])
d = sorted(c)
for j in d:
    print(c.index(j)+1)

Measured memory_bytes: 3064
#include<iostream>
#include<cmath>
using namespace std;
  
double get_distance(int *a, int *b, int length){
  double res = 0;
  for (int i = 0; i < length; i++) {
    res += pow(a[i] - b[i], 2.0);
  }
  res = sqrt(res);
  return res;
}
  
int main(){
  int N, D;
  int i, j;
  cin >> N >> D;
  
  int arr[N][D];
  
  for(i = 0; i < N; i++){
  	for(j = 0; j < D; j++){
      cin >> arr[i][j];
    }
  }
  
  int count = 0;
  double temp;
  for(i = 0; i < N; i++){
  	for(j = i + 1; j < N; j++){
      temp = get_distance(arr[i], arr[j], D);
      if (temp - floor(temp) == 0) {
        count++;
      }
    }
  }
  
  cout << count << endl;
  
  return 0;
}

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

signed main() {
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    ll ans = 0;
    ans += min(a, k);
    k -= a;
    if (k > 0) {
        k -= b;
    }
    if (k > 0) {
        ans -= k;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    int n;
    int d[100];
    d[0] = 1;
    d[1] = 1;
    d[2] = 2;
    for (int i = 3; i < 100; i++)
    {
        d[i] = d[i - 1] + d[i - 2] + d[i - 3];
    }
    while (1)
    {
        cin >> n;
        if (n == 0)
            break;
        cout << d[n] / 365 / 10 + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 1156
#include <stdio.h>

int main(void)
{
	int a , b ,x;
	scanf("%d %d" ,&a ,&b);
	if(a > b){printf("a > b\n");
	}else if(a == b){
	printf("a == b\n");
	}else if(a < b){
	printf("a < b\n");
	}
	return 0;
}


Measured memory_bytes: 2044
N, K = map(int, input().split())

V = list(map(int, input().split()))

max_score = 0
searched_list = []
for k in range(K+1):
    #print(k)
    for l in range(k+1):
        for r in range(k+1-l):
            if l + r > N:
                break
            taken = V[:l]
            taken.extend(V[N-r:])
            sorted_taken = sorted(taken)
            #print(sorted_taken)
            neg_count = len([n for n in sorted_taken if n < 0])
            remove_count = min(k-l-r, neg_count)
            score = sum(sorted_taken[remove_count:])
            if max_score < score:
                max_score = score
                #print(sorted_taken)
                #print(remove_count)
print(max_score)


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

int main() {
   string S;
   cin >> S;
  if( ((S[0]==S[1])&&(S[1]==S[2])) || ((S[1]==S[2])&&(S[2]==S[3])) ){
    cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define PI acos(-1)
#define bp __builtin_popcountll
#define all(x) x.begin(),x.end()
#define sp fixed<<setprecision
#define pii pair<long long,long long>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int MOD = (1e9)+7;
const int N = (1e6)+5;

signed main()
{
    FAST
    int tc=1;
    //cin>>tc;
    for(int ti=1;ti<=tc;ti++)
    {
        int n;
        cin>>n;
        int ans = (n*(n+1))/2;
        int sub = n/3;
        sub*=(sub+1);sub/=2;
        ans-=(3*sub);
        sub = n/5;
        sub*=(sub+1);sub/=2;
        ans-=(5*sub);
        sub = n/15;
        sub*=(sub+1);sub/=2;
        ans+=(15*sub);
        cout<<ans<<endl;
    }
    return 0;
}
/*
Test Case
*/


Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;

int digitSum(int n){
  if(n < 10) return n;
  return digitSum(n/10) + n%10;
}

int digitSum(string s){
  int x = atoi(s.c_str());
  return digitSum(x);
}

int main() {
  int n;
  cin >> n;
  int minsum = INF;
  REP2(i,1,n){
    int a = i;
    int b = n - a;

    int sum = digitSum(a) + digitSum(b);

    minsum = min(sum, minsum);
  }


  cout << minsum << endl;
  return 0;
}


Measured memory_bytes: 3600
//int a = s - '0'; 文字から数字
//小文字から大文字
//transform(a.begin(), a.end(), a.begin(), ::toupper);
//map 全探索
//auto begin = p.begin(), end = p.end();
//for (auto it = begin; it != end; it++) {}
//mapのキー：it->first mapのバリュー：it->second
//大文字判定 isupper(文字) 小文字判定 islower(文字)
//do{}while(next_permutation(ALL(配列)))
//小文字に対応する文字コード：S[i] - 'a'
//文字コード→小文字：(char)(数字+'a')
//グラフの距離:隣接行列で扱う
//bool型　初期値はTrue
//島渡りの問題：中間ノードに着目
//数が大きい時の比較はstring型で行う
//全て0になったか調べたい->0になるたびにcntする
//例外処理は最初にする
//x = p^m + q^n...の約数の個数:(n+1)*(m+1)....
//N!のどの素因数で何回割れるか
//⇔1~Nまでの数がそれぞれどの素因数で何回割り切れるかの和
//パズルの問題->一般化して全探索
//stack<ll> s;
//s.push(要素);s.top();s.pop();
//queue<ll> q;
//q.push(要素);q.front();q.pop();
//同じ作業繰り返す系の問題：収束先を見つける
//過半数：N/2.0で判定
//優先度付きキュー
//priority_queue<
//ll,
//vector<ll>
//> q;
#include <bits/stdc++.h>
#define rep(i,N) for(int i = 0; i < N;i++)
#define ALL(a) (a).begin(),(a).end()
#define ll long long int
#define PI 3.14159265358979323846264338327950L
using namespace std;

//割るやつ
const ll MOD = (pow(10, 9) + 7);

// K進数でのNの桁数
ll dig(ll N, ll K) {
	ll dig = 0;
	while (N) {
		dig++;
		N /= K;
	}
	return dig;
}
// a,bの最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

//a,bの最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

//階乗計算
ll f(ll n) {
	if (n == 0 || n == 1) return 1;
	else return (n * f(n - 1));
}

//Nのd桁目の数
ll dignum(ll N, ll d) {
	ll x = pow(10, d);
	N %= x;
	ll y = pow(10, d - 1);
	N /= y;
	return N;
}

//Nをdで何回割れるか
ll divcnt(ll N, ll d) {
	ll ans = 0;
	while (1) {
		if (N%d == 0) {
			ans++;
			N /= d;
		}
		else break;
	}

	return ans;
}

//素数判定
bool prime(ll num) {
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false;
	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false;
	}
	return true;
}

//フィボナッチ数列
vector<ll> memo(pow(10, 6) + 1);
ll fibo(ll n) {
	if (n == 1) return 1;
	else if (n == 2) return 1;
	else if (memo[n] != 0) return memo[n];
	else return memo[n] = fibo(n - 1) + f(n - 2);
}

ll RS(ll N, ll P, ll M) {
	if (P == 0) return 1;
	if (P % 2 == 0) {
		ll t = RS(N, P / 2, M);
		return t * t % M;
	}
	return N * RS(N, P - 1, M);
}

vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

int main() {
	ll K;cin >> K;

	ll sum = 0;
	for(int a = 1; a <= K; a++){
		for(int b = 1; b <= K; b++){
			for(int c = 1; c <= K; c++){
				sum += gcd(gcd(a,b),c);
			}	
		}
	}

	cout << sum << endl;
}	

Measured memory_bytes: 11000
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.io.UncheckedIOException;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CColorfulLeaderboard solver = new CColorfulLeaderboard();
        solver.solve(1, in, out);
        out.close();
    }

    static class CColorfulLeaderboard {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            int n = in.ints();
            int[] c = new int[8];
            int r = 0;
            for (int i = 0; i < n; i++) {
                int a = in.ints() / 400;
                if (a < 8) {
                    c[a]++;
                } else {
                    r++;
                }
            }
            long ans = Arrays.stream(c).filter(i -> i > 0).count();
            out.print(Math.max(1, ans));
            out.print(' ');
            out.println(ans + r);
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

    }
}



Measured memory_bytes: 26580
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  int c = 0;
  while(1 <= N){
    if(10*10*10*10 <= N && N < 10*10*10*10*10){
      c++;
    }
    else if(10*10 <= N && N < 10*10*10){
      c++;
    }
    else if(1<= N && N < 10){
      c++;
    }
    N--;
  }
  cout << c <<endl;
}

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

int main() {
  int N, num1, num2, num3, remaining1, remaining2, remaining3, remaining4;
  cin >> N;

  remaining1 = N % 10;
  num1 = N / 10;
  remaining2 = num1 % 10;
  num2 = num1 / 10;
  remaining3 = num2 % 10;
  num3 = num2 / 10;
  remaining4 = num3 % 10;
  
  if ((remaining4 == remaining3 && remaining3 == remaining2) || (remaining3 == remaining2 && remaining2 == remaining1)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


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

using namespace std;
int main(){
int N; cin >> N;
  double dp[3010][3010];
  
  //dp[i][j]は、x[1],x[2],,,x[i]目までの中でj枚(0<=j<=i)が表を向いている確立を表す
  
  for(int i = 0; i < 3010; i++){for(int j = 0; j < 3010; j++){ dp[i][j] = 0.0;}}
  vector<double> p(N+1);
 for(int i = 1; i <= N; i++){ cin >> p[i];}
  
  dp[1][0] = 1-p[1]; dp[1][1] = p[1];
  
  for(int i = 1; i < N; i++){
    for(int j = 0; j <= i+1; j++){
       dp[i+1][j] = dp[i][j]*(1-p[i+1]);
      if(j){dp[i+1][j] += dp[i][j-1]*p[i+1];}
    }
  }
  
  double res = 0.0;
  
  for(int i = (N+1)/2; i <= N; i++){ res += dp[N][i];}
  cout << setprecision(10) << res << endl; return 0;}
      

Measured memory_bytes: 71040
n=input()


ans=""

if n[0]=="1":
	ans=ans+"9"
else:
	ans=ans+"1" 

if n[1]=="1":
	ans=ans+"9"
else:
	ans=ans+"1" 

if n[2]=="1":
	ans=ans+"9"
else:
	ans=ans+"1"


print(ans) 

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

struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define MOD 1000000007



int main() {
    int N, M, C; cin >> N >> M >> C;
    vi B(M);
    rep(i, M) cin >> B[i];
    int ans = 0;
    rep(j, N) {
        vi A(M);
        int sum = C;
        rep(i, M) {
            cin >> A[i];
            sum += A[i] * B[i];
        }
        if (sum > 0) ans++;
    }
    cout << ans << endl;
}







Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

int n;

struct Edge{
	int from, to, cost;
	Edge(int from, int to, int cost) : from(from), to(to), cost(cost){}
};

vector<vector<int>> to;
vector<vector<int>> rev_to;
vector<bool> reach1; 
vector<bool> reach2; 

void dfs(int v){
	if(reach1[v])return;
	reach1[v] = true;
	for(auto nv : to[v])dfs(nv);
}

void dfs2(int v){
	if(reach2[v])return;
	reach2[v] = true;
	for(auto nv : rev_to[v])dfs2(nv);
}


int ng = 0;

vector<Edge> es;
vector<int> dist;
void bellman_ford(int s){	
	dist.assign(n, INF);
	dist[s] = 0;
	for(int i = 0; i < n; ++i){	
		for(auto e : es){
			if(e.from == INF)continue;
			if(!reach1[e.from] || !reach2[e.from])continue;
			if(!reach1[e.to] || !reach2[e.to])continue;
			if(dist[e.from] + e.cost < dist[e.to]){
				dist[e.to] = dist[e.from] + e.cost;
				if(i == n - 1)ng = 1;
			}
		}
	}
}

int main(){
  int m, p;
  cin >> n >> m >> p;
  to.resize(n);
  rev_to.resize(n);
  for(int i = 0; i < m; ++i){
  	int a, b, c;
  	cin >> a >> b >> c;
  	--a;
  	--b;
  	c -= p;
  	c *= -1;
  	es.push_back(Edge(a, b, c));
  	to[a].push_back(b);
  	rev_to[b].push_back(a);
  }

  reach1.assign(n, false);
  reach2.assign(n, false);
  dfs(0);
  dfs2(n - 1);
  bellman_ford(0);
  if(ng)cout << -1 << endl;
  else cout << max(0, -dist[n - 1]) << endl;
  return 0;
}


Measured memory_bytes: 768
import java.util.*;
import java.util.stream.*;

class Main {
  static final List<String> RESULT_TYPE = 
  Collections.unmodifiableList(Arrays.asList("AC", "WA", "TLE", "RE"));
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Map<String, Integer> result = new HashMap<>();
    int N = sc.nextInt();
    for (int i = 0; i < N; i++) {
      String judge = sc.next();
      result.put(judge, result.get(judge) == null ? 1 : result.get(judge) + 1);
    }
    dispResult(result);
  }
  static void dispResult(Map<String, Integer> result) {
    for (String R : RESULT_TYPE) {
      System.out.println(R + " x " + (result.get(R) == null ? 0 : result.get(R)));
    }
  }
}




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

using namespace std;
using ll = long long;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W;
  cin >> H >> W;
  vector<string> S(H + 2);
  S[0]     = '.' * W;
  S[H + 1] = '.' * W;
  for (int h = 1; h <= H; h++)
    cin >> S[h];
  for (int h = 1; h <= H; h++) {
    for (int w = 1; w <= W; w++) {
      if (S[h][w] != '#') continue;
      int cnt = 0;
      for (int i = 0; i < 4; i++)
        if (S[h + dy[i]][w + dx[i]] == '#') cnt++;
      if (cnt == 0) {
        cout << "No" << '\n';
        return 0;
      }
    }
  }
  cout << "Yes" << '\n';
  return 0;
}


Measured memory_bytes: 256
# -*- coding:utf-8 -*-
import sys
 
 
def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * (y_length + 1) for i in range(x_length + 1)]
    for i, ch_x in enumerate(x, 1):
        row = memo[i]
        pre_row = memo[i-1]
        for j, ch_y in enumerate(y, 1):
            if ch_x == ch_y:
                row[j] = pre_row[j-1] + 1
            elif pre_row[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = pre_row[j]
    return memo[-1][-1]
 
 
if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
    print(*result, sep="\n")


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

using namespace std;

using ll = long long;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    int win = 0, lose = 0;
    int p = 0, r = 0;
    r++;
    if (s[0] == 'p') {
        lose++;
    }
    for (int i = 1; i < n; i++) {
        if (s[i] == 'g') {
            if (p < r) {
                p++;
                win++;
            } else {
                r++;
            }
        } else {
            if (p < r) {
                p++;
            } else {
                r++;
                lose++;
            }
        }
    }
    cout << win - lose;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
typedef long long ll;

int ord[100010], low[100010];
int k;
vector<int> G[100010];
vector<pair<int, int>> bridge;
vector<int> articulation;
bool visit[100010] = {};

void dfs(int v, int p, int &k) {
    visit[v] = 1;
    ord[v] = k++;
    low[v] = ord[v];

    bool isArticulation = 0;
	int ct = 0;
    for (int i = 0; i < G[v].size(); i++) {
        if (!visit[G[v][i]]) {
            ct++;
            dfs(G[v][i], v, k);
            low[v] = min(low[v], low[G[v][i]]);
            if (~p && ord[v] <= low[G[v][i]]) isArticulation = 1;
            if (ord[v] < low[G[v][i]]) 
                bridge.emplace_back(min(v, G[v][i]), max(v, G[v][i]));
        }
        else if (G[v][i] != p) {
            low[v] = min(low[v], ord[G[v][i]]);
        }
    }
    if (p == -1 && ct > 1) isArticulation = 1;
	if (isArticulation) articulation.push_back(v);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int s, t;
        cin >> s >> t;
        G[s].push_back(t);
        G[t].push_back(s);
    }

    int k = 0;
	for (int i = 0; i < n; i++){
		if (!visit[i]) dfs(i, -1, k);
	}
    sort(bridge.begin(), bridge.end());
	sort(articulation.begin(), articulation.end());

    for (int i = 0; i < bridge.size(); i++) {
        //cout << bridge[i].first << " " << bridge[i].second << endl;
    }
    for (int i = 0; i < articulation.size(); i++) {
        cout << articulation[i] << endl;
    }
}


Measured memory_bytes: 6920
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long

int main() {
  ll K;
  string S;
  cin >> K >>S;
  if(S.length()<=K){
    cout << S << endl;
    return 0;
  }

  for(int i=0; i<K; i++)
    cout << S.at(i);

  cout << "..." << endl;

}

Measured memory_bytes: 3628
# ラスト三文字を状態として保持してDPする
n = int(input())

# dp[len][i][j][k] := 長さ len 文字で, 末尾が i, 末尾-1 が j,
#                   末尾-2 が k, となる文字列の総数
dp = [[[[0]*4 for k in range(4)] for j in range(4)] for i in range(n+1)]

# 長さ 0 の文字列は 1通りしかない!
dp[0][3][3][3] = 1
mod = 1000000007

# 文字列の長さ 
for lens in range(n):
    # 最後から1文字目の文字
    for c1 in range(4):
        # 最後から2文字目の文字
        for c2 in range(4):
            # 最後から3文字目の文字
            for c3 in range(4):
                # 条件に当てはまるものがない場合は continue
                if dp[lens][c1][c2][c3] == 0:
                    continue
                # 新しく追加する文字
                for a in range(4):
                    if a == 2 and c1 == 1 and c2 == 0:
                        continue
                    if a == 2 and c1 == 0 and c2 == 1:
                        continue
                    if a == 1 and c1 == 2 and c2 == 0:
                        continue
                    if a == 2 and c1 == 1 and c3 == 0:
                        continue
                    if a == 2 and c2 == 1 and c3 == 0:
                        continue

                    # だめな条件を抜けたら, a を足した文字列を作れる.
                    dp[lens+1][a][c1][c2] += dp[lens][c1][c2][c3]
                    dp[lens+1][a][c1][c2] %= mod
 
ans = 0
for c1 in range(4):
    for c2 in range(4):
        for c3 in range(4):
            ans += dp[n][c1][c2][c3]
            ans %= mod
 
print(ans)


Measured memory_bytes: 3316
// finish date: 2018/02/24

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define bigmod 1000000007
#define INF 1050000000
#define pii pair<int,int>


int main() {
    int N, M;
    cin >> N >> M;
    vb redPossibility(N, false);
    redPossibility[0] = true;
    vi ballNum(N, 1);
    int x, y;
    rep(i, M) {
        cin >> x >> y;
        x--;
        y--;
        ballNum[x]--;
        ballNum[y]++;
        if (redPossibility[x]) redPossibility[y] = true;
        if (ballNum[x] == 0) redPossibility[x] = false;
    }
    int c = 0;
    rep(i, N) if (redPossibility[i]) c++;
    cout << c << endl;

    return 0;
}





Measured memory_bytes: 640
from operator import itemgetter

class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

n = int(input())
LR = [tuple(int(x) for x in input().split()) for _ in range(n)]
LR.sort(key=itemgetter(0))
L = []
R = []
for l, r in LR:
    L.append(l)
    R.append(r)
seg = SegTree(R, fx=min, ex=10**18)
ans = 0
for i in range(1, n):
    contest1 = seg.query(0, i) - L[i - 1] + 1
    contest2 = seg.query(i, n) - L[n - 1] + 1
    ans = max(ans, contest1 + contest2)

LR.sort(key=lambda item: item[1] - item[0], reverse=True)
lmax = max(l for l, _ in LR[1:])
rmin = min(r for _, r in LR[1:])
ans = max(ans, LR[0][1] - LR[0][0] + 1 + max(rmin - lmax + 1, 0))
print(ans)


Measured memory_bytes: 107304
// #define _CRT_SECURE_NO_WARNINGS
// #define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
#include <iomanip>	// 10桁出力 cout << setprecision(10) << double;
#include <queue>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
typedef multimap<int, char, greater<int> > MuMAPIC;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMIS;
typedef pair<int, int> P;
typedef pair<int, pair<P, P> > PP;

#define MP make_pair
#define FAST_IO  cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//for gcc (未test)
// #define FOREACH_IT(it,c) for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(),c_end=c.end();it!=c_end;++it)
// for Debug.
#define DUMP_VVI(b) FOR(i,0,b.size()){FOR(j,0,b[i].size())printf("%d ",b[i][j]);puts("");}
#define D_OUT(str,value) if(dbgF){cout<<str<<" : "<<value<<endl;}
// 入力をpush_back(d)やarray[d]に使う時に1行で書ける
// int INPUT_INT() {int d;cin>>d;return d;}
template<class T>T IN() { T d; cin >> d; return d; }
// 最大公約数（Greatest Common Divisor）
LL gcd(LL a, LL b) { return (b > 0) ? gcd(b, a%b) : a; }
// 最小公倍数（Least Common Multiple）
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
// Y年はうるう年か否か
bool uruu(LL Y) { return (((Y % 4 == 0 && Y % 100 != 0) || Y % 400 == 0) ? true : false); }

// vector注意
// vec[i][j]の形に入力を入れるとき、vecは初期化してある必要がある.

// ------------------- include, typedef, define END. -------------------

int main() {
	FAST_IO;
	// for D_OUT(str, value)  ... cout<< str <<" : "<< value <<endl;
	bool dbgF = true;

	//コードはここから書く.
	string a, b, c;
	cin >> a >> b >> c;
	cout << a[0] << b[0] << c[0] << endl;


	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
int main()
{	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,k;
	cin>>n>>k;
	vector<char> a(n);
	for (int i=0;i<n;i++)
	{	cin>>a[i];
	}
	int cnt=0;
	for (int i=1;i<n;i++)
	{	cnt+=(a[i]!=a[i-1]);
	}
	cout<<min(n-1,n-1-cnt+2*k)<<'\n';
	return 0;
}

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

#define for(i, a, b) for(ll (i)=a;(i)<(b);++(i))
#define rep(i, n)    for(i, 0, n)
#define sz(x)        ((ll)(x).size())
#define inf          1<<25

int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};

int main() {
    int n;
    cin >> n;
    
    string v[n];
    rep(i, n) cin >> v[i];
    
    ll num[n][26] = {};
    rep(i, n) rep(j, sz(v[i])) num[i][(char)v[i][j] - 'a']++;
    
    string ans = "";
    rep(j, 26) { 
        ll k = inf;
        rep(i, n) k = min(k, num[i][j]);
        rep(i, k) ans += 'a' + j;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000001;

int main()
{
	int N, T, minA = INF, maxW = -1, res = 0;
	cin >> N >> T;
	for (int i = 0, A; i < N;i++) {
		cin >> A;
		if (A < minA) {
			minA = A;
		}
		else if (A - minA > maxW) {
			maxW = A - minA;
			res = 1;
		}
		else if (A - minA == maxW) {
			res++;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256