akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100000 + 100;
int N, a, b, tot = 0, head[maxn], q[maxn], A[maxn], dis[maxn], pre[maxn];
int Q1[maxn], Q2[maxn], d[maxn], son[maxn]; bool used[maxn];
struct Edge { int last, to; } e[maxn<<1];

void build(int from, int to)
{
	e[++tot] = (Edge) {head[from], to};
	head[from] = tot;
}

int bfs(int S)
{
	memset(used, 0, sizeof(used));
	int h = 0, t = 1, ret = 1;
	q[1] = S, used[S] = true, dis[S] = pre[S] = 0;
	while(h <= t)
	{
		int u = q[++h];
		for(int i = head[u]; i ; i = e[i].last)
		{
			int v = e[i].to;
			if(!used[v])
			{
				used[v] = true, dis[v] = dis[u] + 1;
				q[++t] = v, pre[v] = u;
			}
		}
	}
	for(int i = 2; i <= N; ++i)
		if(dis[i] > dis[ret]) ret = i;
	int pos = ret; A[A[0]=1] = ret;
	while(pre[pos]) pos = pre[pos], A[++A[0]] = pos;
	return ret;
}

bool dfs(int u, int dep)
{
	if(dep > 1) return false;
	d[u] = dep, son[u] = 0;
	for(int i = head[u]; i ; i = e[i].last)
	{
		int v = e[i].to; if(used[v]) continue;
		used[v] = true, son[u]++;
		if(!dfs(v, dep+1)) return false;
	}
	return true;
}

bool pre_work()
{
	memset(used, 0, sizeof(used));
	for(int i = 1; i <= A[0]; ++i) used[A[i]] = true;
	for(int i = 1; i <= A[0]; ++i) if(!dfs(A[i], 0)) return false;
	return true;
}

void Generate(int *K)
{
	int tot = 0;
	for(int i = 1; i <= N; ++i) K[i] = i;
	for(int i = 1; i <= A[0]; ++i)
	{
		int k = son[A[i]], nxt = tot + son[A[i]] + 1;
		for(int j = tot+1; j < nxt; ++j) K[j] = j + 1;
		K[nxt] = tot + 1, tot = nxt;
	}
}

void reverse()
{
	for(int i = 1; i <= (A[0]>>1); ++i)
		swap(A[i], A[A[0]-i+1]);
}

void check()
{
	for(int i = 1; i <= N; ++i)
	{
		if(Q1[i] < Q2[i]) break;
		if(Q1[i] > Q2[i])
		{
			memcpy(Q1, Q2, sizeof(Q1));
			break;
		}
	}
}

void Init()
{
	scanf("%d", &N);
	for(int i = 1; i <= N; ++i)
	{
		scanf("%d%d", &a, &b);
		build(a, b), build(b, a);
	}
}

void Solve()
{
	bfs(bfs(1));
	if(!pre_work()) { printf("-1\n"); return; }
	Generate(Q1), reverse(), Generate(Q2), check();
	for(int i = 1; i <= N; ++i) printf("%d ", Q1[i]);
	printf("\n");
}

int main()
{
	Init(), Solve();
}

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

int main() {
	// your code goes here
	int px,py;
	long rta=0;
	cin>>px>>py;
if(px==3) rta+=100000;
if(px==2) rta+=200000;
if(px==1) rta+= (py==1)?700000 :300000;
if(py==3) rta+=100000;	
if(py==2) rta+=200000;
if(py==1) rta+=300000;
cout<<rta<<endl;
	return 0;
}

Measured memory_bytes: 256
#define m(a,b) a=a<b?a:b
#define f(a) for(a=0;a++<n;)
d,a[101][101],b[101][101],u,v,c;main(n){scanf("%d%*d",&n);f(u)f(v)b[u][v]=1e8;for(;~scanf("%d%d%d",&u,&v,&c);a[u][v]=b[u][v]=b[v][u]=c);f(c)f(u)f(v)m(b[u][v],b[u][c]+b[c][v]);f(u)f(v)d+=a[u][v]>b[u][v];printf("%d\n",d);}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MOD 1000000007
using namespace std;


int main()
{
    string s,t;
    cin >> s >> t;
    long long a[t.size()][s.size()]={},sum[t.size()+1][s.size()+1]={};
    for(int j=0;j<(int)s.size();j++){
            if(t[0]==s[j]) a[0][j]=1;
            sum[0][j]+=a[0][j]%MOD;
        }
    for(int i=0;i<(int)t.size();i++){
        for(int j=0;j<(int)s.size();j++){
            if(t[i]==s[j]) a[i][j]=1;
            sum[i+1][j+1]=(sum[i+1][j]+sum[i][j]*a[i][j])%MOD;
        }
    }
    cout << sum[t.size()][s.size()] << endl;
    return 0;
}



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

int main() {
    // int a, b, c;
    int n,l;
    cin >> n >> l;
    
    int x;

    // L + \dots + L + N - 1 
    // = N * (2*L + N - 1) / 2

    if(l<0){
    	if(n+l>0){
    		x = n * (2*l + n - 1) / 2;
    	}
    	else{
    		x = (n-1) * (2*l + n - 2) / 2;
    	}
    }
    else{
    	x = (n-1) * (2*l + n) / 2;
    }

    cout << x << endl;



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
const int inf = 1e9+7;
const int INF = 1e18+7;
//26

int a[300000];
signed main(){
	int n, ans = 0;
	scanf("%lld", &n);
	rrep(i,n)scanf("%lld",&a[i]);
	rrep(i,n)a[i] = a[i]-i;
	sort(a+1, a+1+n);
	int b = a[n/2+1];
	rrep(i,n)ans += llabs(a[i]-b);
	printf("%lld\n", ans);
	return 0;
}





Measured memory_bytes: 1792
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

X = read().rstrip().decode('utf-8')

stack = ['$']
for x in X:
    if stack[-1] == 'S' and x == 'T':
        stack.pop()
        continue
    stack.append(x)

answer = len(stack) - 1
print(answer)

Measured memory_bytes: 4868
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
#define vbi vector<bool> 
#define mod 1000000007
#define INF 1000000000
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define sd second
#define ft first
#define ms(x,v)    memset(x, v, sizeof x)
#define endl '\n'
#define cnl cout<<endl;
#define fr(i,b) for(ll i=0; i<=b; i++)
#define frr(i,b) for(ll i=0;i<b;i++)
#define fb(i,b) for(ll i=b-1; i>=0; i--)
#define pi  3.141592653589793238
ll i,j,n;
vector<long int> v[2*100000+1];
vector<bool> flag(2*100000+1,false);
 vl c(2*100000+1,0);
 vector<long int >b(2*100000+1,0);
void dfs(long int a,long int z){
     flag[a]=true;
     //cout<<b[a]<<" ";
     z=z+b[a];
     c[a]=z;
     for(auto y:v[a]){
        if(flag[y]) continue;

        dfs(y,z);
        
     }
}
int main(){
    ll q; cin>>n>>q;
    for(i=0;i<n-1;i++){
    	ll x,y; cin>>x>>y;
    	v[x].pb(y);
    }
    for(i=0;i<q;i++){
       ll x,y; cin>>x>>y;
       b[x]=b[x]+y;
    }
    c[1]=b[1];
    dfs(1,0);
   for(i=1;i<=n;i++){
   	cout<<c[i]<<" ";
   }





return 0;
}

Measured memory_bytes: 25856
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

struct pair_sort{
	bool operator()(const pii& x, const pii& y) const{
		if(x.first > y.first){
			return true;
		}else if(x.first < y.first){
			return false;
		}else if(x.second > y.second){
			return false;
		}else{
			return true;
		}
	}
};

int main(){
	int n,m;
	while(true){
		cin >> n >> m;
		if(n == 0 && m == 0){
			break;
		}
		vector<pii> vpii;
		rep(i,m){
			vpii.pb(mp(0,i+1));
		}

		int buf;
		rep(i,n){
			rep(j,m){
				cin >> buf;
				vpii[j].first += buf;
			}
		}

		sort(all(vpii),pair_sort());

		rep(i,m){
			cout << vpii[i].second << (i+1 == m ? '\n' : ' ');
		}
	}
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll a[1005][3];
ll tmp[1005];
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
        {
            for(int k=0;k<3;k++)
            {
                cin>>a[i][k];
            }
        }
        ll ans=-1e18;
        //cout<<ans<<endl;
        for(int i=0;i<8;i++)
        {
            for(int j=0;j<n;j++)
            {
                ll sum=0;
                for(int k=0;k<3;k++)
                {
                    if(i&(1<<k))
                    {
                        sum+=a[j][k];
                    }
                    else
                    {
                        sum-=a[j][k];
                    }
                }
                tmp[j]=sum;
            }
            sort(tmp,tmp+n,greater<ll>());
            ll ret=0;
            for(int j=0;j<m;j++)
            {
                ret+=tmp[j];
            }
            ans=max(ans,ret);
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
cards = []
put = []

for i in range(3):
    a, b, c = map(int, input().split())
    cards.append(a)
    cards.append(b)
    cards.append(c)

num = int(input())

for s in range(num):
    tmp = int(input())
    if tmp in cards:
        put_index = cards.index(tmp)
        put.append(put_index)

Yes_flg = False

if len(put) < 3:
    pass
else:
    if 0 in put:
        if 1 in put and 2 in put:
            Yes_flg = True
        elif 3 in put and 6 in put:
            Yes_flg = True
        elif 4 in put and 8 in put:
            Yes_flg = True
    if 4 in put:
        if 3 in put and 5 in put:
            Yes_flg = True
        elif 1 in put and 7 in put:
            Yes_flg = True
        elif 2 in put and 6 in put:
            Yes_flg = True
    if 8 in put:
        if 6 in put and 7 in put:
            Yes_flg = True
        elif 2 in put and 5 in put:
            Yes_flg = True

if Yes_flg:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = (int) 2e5 + 100;
int p[N], ans[N];


int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &p[i] );
    for (int i = 0; i < n; i++)
        ans[p[i] ] = ans[p[i] - 1] + 1;
    int mx = 0;
    for (int i = 1; i <= n; i++)
        mx = max(mx, ans[i] );
    printf("%d\n", n - mx);



	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(void){
    int N; cin >> N;
    vector<int> p(N+2, 0);
    for(int i=1; i<=N; i++) cin >> p[i];

    int ans = 0, cnt = 0;
    bool flg = false;
    for(int i=1; i<=N+1; i++){
        if(flg == true){
            if(p[i] == i) cnt++;
            else{
                flg = false;
                if(cnt == 1) ans++;
                else ans += (cnt+1)/2;
                cnt = 0;
            }
        }
        else{
            if(p[i] == i){
                flg = true;
                cnt++;
            }
        }
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 640
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
char s[505][505];
vector<int>g[4005];
int m,n,ans,mat[4005],tot,tot1;
int a1[5005][5005],b1[505][505];
bool vis[4005];
struct mzls
{
	int x,y;
}a[205],b;
inline bool dfs(int x)
{
	for(int i=0;i<g[x].size();i++)
	{
		int v=g[x][i];
		if(vis[v])
			continue;
		vis[v]=1;
		if(!mat[v]||dfs(mat[v]))
		{
			mat[v]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
	for(int i=1;i<=n;i++)
	{
		for(int j=n+1;j<=2*n;j++)
			if(a[i].x<a[j].x&&a[i].y<a[j].y)
			{
				g[i].push_back(j);
				g[j].push_back(i);
			}
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		ans+=dfs(i);
	}
	printf("%d",ans);
}

Measured memory_bytes: 384
a = input().split(" ")
a =[int(i) for i in a]
N = a[0] #Nはモンスターの数
K = a[1] #Kは必殺技を使える回数

kai = 0
H = input().split(" ")
H =[int(i) for i in H]
H.sort(reverse=True)

if N<=K:
    kai = kai
else:
    H  = H[K:]
    kai = sum(H)
    
print(kai)

Measured memory_bytes: 25872
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())

facts = [0] * (N + 1)
def f(n):
    i = 2
    while i ** 2 <= N:
        if n % i == 0:
            n //= i
            facts[i] += 1
        else:
            i += 1
    if n > 1:
        facts[n] += 1

for i in range(2, N + 1):
    f(i)
        
ans = 1
for i in range(2, N + 1):
    ans *= facts[i] + 1
    ans %= MOD
print(ans % MOD)


Measured memory_bytes: 9516
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
#  = input()
n  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

print((n * 800) - (n // 15) * 200 )


Measured memory_bytes: 3316
import sys
sys.setrecursionlimit(10**7)

n = int(input())
flag = [-1 for _ in range(n)]
la=[[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    la[a-1].append(b-1)
    la[b-1].append(a-1)

def dfs(s,d):
    global flag
    global la
    flag[s] = d + 1
    for g in la[s]:
        if flag[g] == -1:
            dfs(g,flag[s])

def main():
    global n
    global flag
    dfs(0,-1)
    distf = flag[:]
    flag = [-1 for _ in range(n)]
    dfs(n-1,-1)
    dists = flag[:]
    res = 0
    for i in range(n):
        if distf[i] <= dists[i]:
            res += 1
        else:
            res -= 1
    if res > 0:
        return "Fennec"
    else:
        return "Snuke"



print(main())

Measured memory_bytes: 215348
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  int n; cin>>n;
  vector<ll> a(n),b(n);
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
  }
  ll ans=0;
  int i=n-1;
  while(i!=-1){
    if((a[i]+ans)%b[i]!=0){
      ans+=b[i]-((a[i]+ans)%b[i]);
    }
    i--;
  }
  cout<<ans<<endl;
}

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

using namespace std;

#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll modpow(ll a, ll b){

    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b=b/2;
    }
    return ans;
}

int main(){

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

    
    string s;
    cin>>s;

    for(int i = 0; i < s.size(); i++) s[i] = 'x';
    cout<<s<<endl;
    

}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int W,H,x,y,r;
  cin >> W >> H >> x >> y >> r;

  //in X
  if(0 <= x-r and x+r <= W and
     0 <= y-r and y+r <= H){
    cout<<"Yes"<<"\n";
  }else{
    cout<<"No"<<"\n";
  }
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N,M;
  cin >> N >> M;
  cout << N*M/2 << endl;
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  int minc = 0;
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;
    int cnt = 0;
    while (!(A % 2)) {
      cnt += 1;
      A /= 2;
    }
    if (i == 0) {
      minc = cnt;
    }
    else if (minc > cnt) {
      minc = cnt;
    }
  }
  cout << minc << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;
	int array[N];
	for(int i = 0; i < N; i++) cin >> array[i];

	// ソート
	int cnt = 0;
	for(int i = 0; i < N; i++)
	{
		int min = i;
		for(int j = i; j < N; j++)
			if(array[j] < array[min]) min = j;
		swap(array[i], array[min]);
		if(min != i) cnt++;
	}
	
	// 表示
	for(int i = 0; i < N-1; i++) printf("%d ", array[i]);
	printf("%d\n%d\n", array[N-1], cnt);
	
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//te[0] r
//te[1] s
//te[2] p
int n,k,p[3];
string t;
vector<int> v;

int main() {
    cin >> n >> k >> p[0] >> p[1] >> p[2] >> t;
    v.push_back(0);
    for (int i = 0; i < n; i++) {
        if (t[i] == 'r') v.push_back(2);
        if (t[i] == 's') v.push_back(0);
        if (t[i] == 'p') v.push_back(1);
    }

    ll ans = 0;
    for (int i = 1; i <= k; i++) {
        ll dp[(n+k)/k][3] = {};
        int cnt = 0;
        for (int j = i; j <= n; j += k) {
            if (j == i) {
                dp[0][v[j]] = p[v[j]];
            } else {
                for (int before = 0; before < 3; before++) {
                    for (int now = 0; now < 3; now++) {
                        if (now == v[j] && before == v[j]) continue;
                        dp[cnt][now] = max(dp[cnt][now], dp[cnt - 1][before] + (now == v[j]) * p[v[j]]);
                    }
                }
            }
            cnt++;
        }
        cnt = max(cnt-1,0);
        ans += max({dp[cnt][0], dp[cnt][1], dp[cnt][2]});
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3192
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <cassert>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
#include <bitset>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<Int, Int> PLL;
typedef pair<double, double> PDD;
typedef complex<double> base;

const int INF = 1000000000;
const int BASE = 1000000007;
const int MAX = 100007;
const int MAXX = 1000000;
const int ADD = 1000000;
const int MOD = 998244353;
const int CNT = 800;

bool U[MAX];
int A[MAX];
vector<PII> G[MAX];

bool ok = 1;

void dfs(int v)
{
    U[v] = 1;
    FOR(i,0,SZ(G[v]))
    {
        int to = G[v][i].first;
        int len = G[v][i].second;
        if (!U[to])
        {
            A[to] = A[v] + len;
            dfs(to);
        }
        else
        {
            if (A[to] != A[v] + len)
            {
                ok = 0;
            }
        }
    }
        
}


int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("distance.in",  "r", stdin);
    //freopen("distance.out", "w", stdout);
    //freopen("out.txt" , "w" , stdout);
    
    int n , m;
    cin >> n >> m;
    
    FOR(i,0,m)
    {
        int a , b , d;
        scanf("%d%d%d" , &a , &b , &d);
        --a;--b;
        G[a].push_back(MP(b , d));
        G[b].push_back(MP(a , -d));
    }
    
    FOR(i,0,n)
    {
        if (!U[i])
        {
            dfs(i);
        }
    }
    
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    
    return 0;
}













Measured memory_bytes: 12032
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int mod_pow(int64_t a, int64_t e, int64_t p){
    int64_t res = 1;
    for(;e>0;e>>=1){
        if(e&1)res=(res*a)%p;
        a=(a*a)%p;
    }
    return (int)res;
}

int main(){
    string S;
    cin>>S;
    int N=S.size();
    int64_t DP[N+1][13];
    fill(DP[0],DP[N+1],0);
    DP[0][0]=1;
    reverse(S.begin(), S.end());
    for(int i=1;i<=N;i++){
        char c=S[i-1];
        for(int k=0;k<10;k++){
            if(c=='?'||c-'0'==k){
                int b=mod_pow(10,i-1,13)*k;
                for(int j=0;j<13;j++){
                    DP[i][(j+b)%13]+=DP[i-1][j];
                    DP[i][(j+b)%13]%=1000000007;
                }
            }
        }
    }
    cout<<DP[N][5]<<endl;
    return 0;
}

Measured memory_bytes: 10688
#if 0
date +%Y.%m.%d

题解先咕着。
#endif
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;

struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read;

const int maxn = 200005;
int head[maxn], nxt[maxn << 1], to[maxn << 1], hp = 1;
char s[maxn];

inline void add(int u, int v) {
	nxt[++ hp] = head[u];
	head[u] = hp;
	to[hp] = v;
}

struct Data {
	int d, d2, bd, c;

	inline void update(Data an) {
		if(an.d + 1 > d) {
			d2 = d;
			d = an.d + 1;
		} else
			d2 = std::max(d2, an.d + 1);
		if(an.c)
			bd = std::min(bd, an.d + 1);
		c += an.c;
	}

	inline void undo(Data an) { // only need "d" and "c" to update
		if(an.d + 1 == d)
			d = d2;
		c -= an.c;
	}
};
Data f[maxn];

void dfs1(int u, int fa) {
	f[u] = {1, 1, maxn, s[u] == '1'};

	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v != fa) {
			dfs1(v, u);
			f[u].update(f[v]);
		}
	}

	/* debug("%d : %d %d %d\n", u, f[u].d, f[u].d2, f[u].bd); */
}

ll ans = 1;
void dfs2(int u, int fa, Data ff) {
	Data g = f[u];
	g.update(ff);

	int L = s[u] == '1' ? 1 : g.bd;
	int R = std::min(g.d - 1, g.d2 + 1);
	if(L <= R) ans += R - L + 1;

/* 	debug("%d : %d %d %d\n", u, g.d, g.d2, g.bd); */
/* 	debug("from %d %d\n", ff.d, ff.bd); */
/* 	debug("ans %d-%d\n", L, R); */

	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v != fa) {
			Data vff = g;
			vff.undo(f[v]);
			dfs2(v, u, vff);
		}
	}
}

int main() {
	int n = read;
	for(int i = 1; i < n; i ++) {
		int u = read, v = read;
		add(u, v);
		add(v, u);
	}
	scanf("%s", s + 1);

	dfs1(1, 0);
	dfs2(1, 0, {0, 0, maxn, 0});

	printf("%lld\n", ans);
}


Measured memory_bytes: 21632
#include<bits/stdc++.h>
#define int long long
#define rep(i,N) for(int i=0;i<(N);i++)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

__attribute__ ((constructor))
void init() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
}

ll n;

vector<pair<int,int>> solve(){
    vector<pair<int, int>> v;
    for (int i = 1; i*i <= n;i++){
        if(n%i==0){
            v.push_back({i, n / i});
        }
    }
    return v;
}

signed main(){
    cin >> n;
    ll ans = 0;
    set<ll> sll;
    for(auto u : solve()){
        // cout << "Yes" << endl;
        rep(i,2){
            ll b = u.second - 1;
            if(b==0)
                continue;
            if((n/b)*(1+b)==n){
                sll.insert(b);
            }
            swap(u.second, u.first);
        }
    }
    for(auto u : sll){
        ans += u;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3696
#include <stdio.h>
#define Max 100000

int A[Max];



int partition(int p ,int r){
	int x,i,j,t;
	x=A[r];
	i=p-1;
	
	for(j=p;j<r;j++){
		if(A[j]<=x){
			i++;
		t=A[j];A[j]=A[i];A[i]=t;
	
		}
	}
	t=A[r];A[r]=A[i+1];A[i+1]=t;
	return i+1;
}

int main(){
	int i,n,x;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
	}
	x = partition(0,n-1);
	
	for(i=0;i<n;i++){
		if(i) printf(" ");
		if(i==x) printf("[");
		printf("%d",A[i]);
		if(i==x) printf("]");
	}
	printf("\n");

	return 0;
}

Measured memory_bytes: 992
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N = INT()
    S = [INPUT() for _ in range(N)]

    c = Counter(S)
    print("AC x " + str(c['AC']))
    print("WA x " + str(c['WA']))
    print("TLE x " + str(c['TLE']))
    print("RE x " + str(c['RE']))


if __name__ == '__main__':
    main()


Measured memory_bytes: 17256
import math

A, B, H, M = input().split()
# print(type(A), A, B, H, M)

A = int(A)
B = int(B)
H = int(H)
M = int(M)

Mdeg = M / 60 * 360
Hdeg = M / 60 * (360 / 12) + H / 12 * 360
angle = math.radians(abs(Hdeg - Mdeg))

L = (A ** 2 + B ** 2 - 2 * A * B * math.cos(angle))
L = L ** 0.5
# print(Mdeg,Hdeg,angle,L)
print(L)

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

int main (){
  int n;    cin >> n ;
  int b;
  priority_queue<int>p;
  vector<int>a(n); 
  rep(i,n) {
      cin >>b;
      p.push(b);
      a.at(i) = b;

      }
      int max,secmax;
      max = p.top();
      p.pop();
      secmax = p.top();

      for(int i=0;i<n;i++){
          if(a.at(i) == max){
              cout << secmax << endl;
          }else cout << max << endl;
      }

      



  
}

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rrep(i,n) for(int i=1; i<=(int)(n); i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<char> vc;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    int N,M;
    scanf("%d%d",&N,&M);
    vii a(N,vi(2)),c(M,vi(2));
    rep(i,N) {
        rep(j,2) {
            cin>>a[i][j];
        }
    }
    rep(i,M) {
        rep(j,2) {
            cin>>c[i][j];
        }
    }
    ll counter=800000000;
    rep(i,N)  {
        ll distance;
        int ans;
        rep(j,M) {
            distance=abs(a[i][0]-c[j][0])+abs(a[i][1]-c[j][1]);
            if(counter>distance) {
                ans=j+1;
                counter=distance;
            }
            distance=0;
        }
        printf("%d\n",ans);
        counter=800000000;
    }
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    a,b,c=map(int,input().split())
    cunt=0
    if a==b and b==c and a%2==0:
        print(-1)
        sys.exit()
    while True:
        if a%2 or b%2 or c%2:
            print(cunt)
            break
        cunt+=1
        a1,b1,c1=a,b,c
        a=(b1+c1)//2
        b=(a1+c1)//2
        c=(a1+b1)//2

if __name__=='__main__':
    main()


Measured memory_bytes: 38256
from itertools import permutations as per
n=int(input())
ans=[]
l=list(per(list(range(1,n+1))))
xy=[[] for i in range(n+1)]
for i in range(n):
    x,y=map(int,input().split())
    xy[i+1].append(x)
    xy[i+1].append(y)
def f(x):
    m=1
    while x>0:
        m*=x
        x=x-1
    return m
for i in range(f(n)):
    dis=0
    for j in range(n-1):
        dis+=((xy[l[i][j]][0]-xy[l[i][j+1]][0])**2+(xy[l[i][j]][1]-xy[l[i][j+1]][1])**2)**(0.5)
    ans.append(dis)
print(sum(ans)/f(n))
    




Measured memory_bytes: 15716
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int d, t, s;
    cin >> d >> t >> s;

    cout << (d <= t * s ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 3632
def enq(a,x)
  f =->(x){x.is_a?(Array) ? x[0] : x}
  a = [a]  if a[i=-1]
  while a[i].is_a? Array
    return a.unshift x  if x <= (a=a[i])[0]
    return a << x  if x >= a[-1]
    i = a.bsearch_index {|y| x <= f[y]}
    i -= 1  if x < f[a[i]]
  end
  return a.insert(i+1, x)  if a.size-i <9
  i > 9 ? a[i] = [a[i],x] : a.unshift(*a.shift(i+1),x)
end
def deq(a)
  return a.shift  if !a[1]
  l,a = a,n  while (n=a[0]).is_a? Array
  if (r=a[1]).is_a? Array; a[0] = deq r; a[1] = r[0] if !r[1]; n
  else (l||[])[0] = r if !a[2]; a.shift end
end
N,M,*A = $<.read.split.map{|x| -x.to_i}
A.sort!
(-M).times { break if A[0]==0; enq A, -(-(deq A)/2) }
p A.flatten.inject(0,:-)

Measured memory_bytes: 17516
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> DP(3);
    for (int i = 0; i < n; i++){
        vector<int> new_dp(3), I(3);
        for (int &v : I) cin >> v;
        for (int j = 0; j < 3; j++){
            for (int k = 0; k < 3; k++){
                if (j != k){
                    new_dp[j] = max(new_dp[j], DP[k]);
                }
            }
            new_dp[j] += I[j];
        }
        DP = new_dp;
    }
    int mx = 0;
    for (int &x : DP){
        mx = max(x, mx);
    }
    cout << mx;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin >> a >> b >> c;
	if(a<=b&&b<=c){cout << a << " " << b << " " << c << endl;}
	else if(a<=c&&c<=b){cout << a << " " << c << " " << b << endl;}
	else if(b<=a&&a<=c){cout << b << " " << a << " " << c << endl;}
	else if(b<=c&&c<=a){cout << b << " " << c << " " << a << endl;}
	else if(c<=a&&a<=b){cout << c << " " << a << " " << b << endl;}
	else if(c<=b&&b<=a){cout << c << " " << b << " " << a << endl;}
}



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

#define rep(i, a, b) for ( int i = (a); i < (b); i++ )
#define per(i, a, b) for ( int i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()


using namespace std;

typedef long long ll;

static const long long MOD = 1000000007;

ll ans;
ll R[4005], G[4005], B[4005];
map<char, ll> m;

int main(void) {
    int n;
    string s = "x", t;
    cin >> n >> t;
    s += t;
    
    for (int i=1; i<=n; i++) {
        m[s[i]]++;
    }

    /*解説&他者回答参考*/
    ans = m['R']*m['G']*m['B'];

    for (int i=1; i<=n-2; i++) for (int j=i+1; j<=n-1; j++) {
        int d = j - i;
        int k = j + d;
        if (k>n) continue;
        if (s[i]!=s[j] && s[i]!=s[k] && s[j]!=s[k]) ans--;
    }

    /*
    Original code

    for (int i=1; i<=n; i++) {
        if (s[i]=='R') R[i]++;
        else if (s[i]=='G') G[i]++;
        else B[i]++;
    }

    for (int i=1; i<=n; i++) {
        R[i] += R[i-1];
        G[i] += G[i-1];
        B[i] += B[i-1];
    }

    for (int i=1; i<=n-2; i++) {
        for (int j=i+1; j<=n-1; j++) {
            if (s[i]==s[j]) continue;
            int d = j-i;

            if (s[i]=='R') {
                if (s[j]=='G') {
                    ans += B[n] - B[j];
                    if (j+d<=n && s[j+d] == 'B') ans--;
                }
                if (s[j]=='B') {
                    ans += G[n] - G[j];
                    if (j+d<=n&&s[j+d] == 'G') ans--;
                }

            } else if (s[i]=='G'){
                if (s[j]=='R') {
                    ans += B[n] - B[j];
                    if (j+d<=n&&s[j+d] == 'B') ans--;
                }
                if (s[j]=='B') {
                    ans += R[n] - R[j];
                    if (j+d<=n&&s[j+d] == 'R') ans--;
                }

            } else if (s[i]=='B') {
                 if (s[j]=='G') {
                     ans += R[n] - R[j];
                     if (j+d<=n&&s[j+d] == 'R') ans--;
                }
                if (s[j]=='R') {
                    ans += G[n] - G[j];
                    if (j+d<=n&&s[j+d] == 'G') ans--;
                }

            }
        }
    }
    */
    
    cout << ans << endl;

	return 0;
}


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

using namespace std;

int main() {
    int n;
    cin >> n;
    map <int, int> mp;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[x]++;
    }
    int res = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (it->second >= it->first) {
            res += it->second - it->first;
        } else {
            res += it->second;
        }
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 7992
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int x3 = x2 - (y2 - y1);
    int y3 = y2 + (x2 - x1);
    int x4 = x3 - (y3 - y2);
    int y4 = y3 + (x3 - x2);

    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;

    return 0;
}

Measured memory_bytes: 3544
#include <stdio.h>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

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

    N = N % 500;

    if (N > A) {
        printf("No\n");
    } else {
        printf("Yes\n");
    }

    return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <iostream>

using namespace std;

const int mod = 1e9 + 7;

int n, t[26];

char s[100010];

int main () {
	scanf ("%d", &n);
	scanf ("%s", s + 1);
	
	for (int i = 1; i <= n; ++i) ++t[s[i] - 'a'];
	
	int ans = 1;
	for (int i = 0; i < 26; ++i) ans = 1ll * ans * (t[i] + 1) % mod;
	
	printf ("%d\n", ans - 1);
	
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>

using namespace std;

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

int main() {
  int n, k;
  cin >> n >> k;
  int p[n];
  rep(i,n) cin >> p[i], p[i]++;
  
  int s = 0, m = 0;
  rep(i,n) {
    s = s + p[i] - (i >= k ? p[i-k] : 0);
    m = max(m, s);
  }
  
  cout << fixed << setprecision(1) << (double)m / 2 << endl;
  return 0;
}

Measured memory_bytes: 4524
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;

    int x = abs(b-a);
    int y = abs(c-a);

    if(x<y) cout<<'A'<<endl;
    else cout<<'B'<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <algorithm>
#include <string>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli> > mat;
typedef vector<vector<bool> > matb;
typedef vector<string> vst;
typedef pair<lli,lli> pll;
typedef pair<double,double> pdd;

const lli MOD = 1000000007;


lli n,m;
vll x,y;
lli x_x,y_x;
lli area;
int main(){
    cin >> n >> m;
    x = vll(n);y = vll(m);
    for(lli i = 0;i < n;i++) cin >> x[i];
    for(lli i = 0;i < m;i++) cin >> y[i];
    x_x = y_x = 0;
    for(lli i = 0;i < n-1;i++){
        x_x += (x[i+1] - x[i]) * ((i+1) * (n-i-1));
        x_x %= MOD;
    }
    for(lli i = 0;i < m-1;i++){
        y_x += (y[i+1] - y[i]) * ((i+1) * (m-i-1));
        y_x %= MOD;
    }
    cout << (x_x*y_x) % MOD << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

vector<int> get_prime(int n){
    if(n <= 1) return vector<int>();
    vector<bool> is_prime(n+1, true);
    vector<int> prime;
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if(is_prime[i]) prime.emplace_back(i);
        for (auto &&j : prime){
            if(i*j > n) break;
            is_prime[i*j] = false;
            if(i % j == 0) break;
        }
    }
    return prime;
}

int main() {
    int M = 1000000;
    vector<bool> is_prime(M+1, true);
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= M; ++i) {
        if(!is_prime[i]) continue;
        for (int j = i*2; j <= M; j += i) {
            is_prime[j] = false;
        }
    }
    int n, x;
    while(cin >> n >> x, n){
        vector<char> dp(x+1);
        dp[0] = 1;
        for (int i = 0; i < n; ++i) {
            int a; cin >> a;
            for (int j = 0; j+a <= x; ++j) {
                dp[j+a] |= dp[j];
            }
        }
        int ok = 0;
        for (int i = x; i >= 2; --i) {
            if(is_prime[i] && dp[i]){
                cout << i << "\n";
                ok = 1;
                break;
            }
        }
        if(!ok) puts("NA");

    }
    return 0;
}


Measured memory_bytes: 4852
#include <stdio.h>

int fibonacci(int);

int F[46];

int main()
{
  int n,i;

  scanf("%d",&n);

  /* 初期化 */
  for(i = 0;i < 46;i++){
    F[i] = -1;
  }

  /* 出力 */
  printf("%d\n",fibonacci(n));

  return 0;
}

int fibonacci(int n)
{
  if(n ==0 || n == 1) return F[n] = 1; // F[n]に1をメモしてそれを返す

  if(F[n] != -1) return F[n]; // F[n]が計算済なら

  return F[n] = fibonacci(n - 2) + fibonacci(n - 1);
}

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

int n,a[105][5];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i][1],&a[i][2]);
	for (int i=1;i<=n-2;i++) {
		if (a[i][1]==a[i][2]&&a[i+1][1]==a[i+1][2]&&a[i+2][1]==a[i+2][2]) {
			puts("Yes");return 0;
		}
	}
	puts("No");
	return 0;
}

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

const int maxN = 305, mod = 998244353;

int n;
int f[maxN + 1][maxN + 1][maxN + 1], g[maxN + 1][maxN + 1][maxN + 1];
bool res[maxN + 1][maxN + 1][maxN + 1];
char s[maxN + 1];

inline void chkmx(int &x, int y) { x = x > y ? x : y; }

inline void update(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);

	f[n][0][0] = 1;
	for(int i = n; i >= 1; i--)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= n - j; k++)
			{
				if(!f[i][j][k]) continue;
				int t = f[i][j][k];
				update(f[i - 1][j][k], t);
				if(s[i] == '0') update(f[i][j][k + 1], t);
				else update(f[i][j + 1][k], t);
			}
	
	memset(g, -1, sizeof(g));
	g[0][0][0] = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= i / 2; j++)
			for(int k = 0; k <= i / 2 - j; k++)
			{
				if(g[i][j][k] == -1) continue;
				int t = g[i][j][k];
				if(s[i + 1] == '0' && t) chkmx(g[i + 1][j + 1][k], t - 1);
				if(s[i + 1] == '1' && t) chkmx(g[i + 1][j][k + 1], t - 1);
				if(i + 2 <= n)
				{
					if(s[i + 1] == '0' || s[i + 2] == '0') chkmx(g[i + 2][j + 1][k], t);
					if(s[i + 1] == '1' || s[i + 2] == '1') chkmx(g[i + 2][j][k + 1], t);
					chkmx(g[i + 2][j][k], t + 1);
				}
			}
	
	int ans = mod - 1;
	for(int i = 0; i <= n; i++)
		for(int j = n; j >= 0; j--)
			for(int k = n - j; k >= 0; k--)
			{
				res[i][j][k] = (g[i][j][k] != -1);
				if(i) res[i][j][k] |= res[i - 1][j][k];
				res[i][j][k] |= (res[i][j + 1][k] | res[i][j][k + 1]);
				if(res[i][j][k]) update(ans, f[i][j][k]);
			}
	
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 252616
n = int(input())
a = [0]*n
b = [0]*n
for i in range(n): a[i],b[i] = map(int,input().split())
a.sort()
b.sort()
if n%2 == 1:
    m = n//2
    ans = b[m] - a[m] + 1
else:
    ml = n//2-1
    mr = n//2
    ma = (a[ml] + a[mr])/2 
    mb = (b[ml] + b[mr])/2
    ans = int((mb - ma)*2 + 1)
print(ans) 

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

using namespace std;
typedef long long ll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int main() {
  int N;
  cin >> N;
  vector<pair<int, int> > l(N);
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >>  a >> b;
    l[i] = make_pair(a, b);
  }

  auto dist = [&](pair<int,int> f, pair<int,int> s) {
    int x = f.first - s.first;
    int y = f.second - s.second;
    return sqrt(x * x + y * y);
  };

  vector<int> p(N);
  for (int i = 0; i < N; i++) {
    p[i] = i;
  }

  double len = 0;
  int cnt = 0;
  do {
    for (int i = 0; i < N - 1; i++) {
      len += dist(l[p[i]], l[p[i + 1]]);
    }
    cnt++;
  } while(next_permutation(p.begin(), p.end()));

  cout << fixed << len/cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long  ll;

#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
ll MOD = 1000000007;

ll a[200001] = {};

int main() {
	ll N; cin >> N;
	ll sum = 0;
	rep(i, 0, N) {
		cin >> a[i];
		sum += a[i];
	}

	ll minV = 1 << 31;

	ll x = 0;
	rep(i, 0, N - 1) {
		x += a[i];
		ll y = abs(2 * x - sum);
		if (minV == 1 << 31) {
			minV = y;
		}
		if (minV > y) {
			minV = y;
		}
	}
	cout << minV << endl;
	return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long[] ab = {sc.nextLong(),sc.nextLong(),sc.nextLong()};
		if(ab[2] > ab[1] && ab[1] > ab[0]){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}


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

int n;

void solve(){
    cin>>n;
    int ans=0;
    for(int i=1; i<=n; i++){
        int cur=i;
        int cnt=0;
        while(cur!=0){
            cur/=10;
            cnt+=1;
        }
        if(cnt%2==1){
            //cout<<"i="<<i<<endl;
            ans+=1;
        }
    }
    cout<<ans<<endl;
}

signed main(){
    //while(1)
    solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if(a+b>c+d){
    cout<<"Left"<<endl;
  }else if(a+b<c+d){
    cout<<"Right"<<endl;
  }else{
    cout<<"Balanced"<<endl;
  }
}


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

#define int long long

using namespace std;

const int N = 3005;

int n;

int a[N], k, dp[N][N], p[N];

int sum (int l, int r) {
    return p[r] - p[l - 1];
}

main () {
    ios_base::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >> n;
    for (int i = 1;i <= n;i ++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
        dp[i][i] = a[i];
    }
    for (int i = 2;i <= n;i ++) {
        for (int l = 1,r = i;r <= n;l ++,r ++) {
            dp[l][r] = sum (l, r) - min (dp[l + 1][r], dp[l][r - 1]);
        }
    }
    cout << dp[1][n] - sum (1, n) + dp[1][n];
}


Measured memory_bytes: 70016
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

int main() {
  vector<int> v(12);
  for(int i=0; i<12; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());

  set<int> S[3];
  for(int i=0; i<12; i++) {
    S[i/4].insert(v[i]);
  }

  bool ok = true;
  for(int i=0; i<3; i++) {
    ok &= (S[i].size() == 1);
  }
  if(ok) cout << "yes" << endl;
  else cout << "no" << endl;
  return 0;
}



Measured memory_bytes: 3148
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n, sum;

int main() {
	read(n);
	for (int x, i = 1; i <= n; ++i) {
		read(x);
		sum ^= x;
	}
	puts(sum ? "No" : "Yes");
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define loop(n) for(int i=0; i<n; i++)
vector<vector<int>> v;
int n,m,q;
void f(vector<int> temp,int index)
{
    if(temp.size()==n)
    {
        v.pb(temp);
        return;
    }
    else
    {
        for(int i=index;i<=m;i++)
        {
            temp.pb(i);
	        f(temp,i);
	        temp.pop_back();
        }
    }
    return;
}
void solve()
{
    cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
	    vector<int> temp;
	    temp.pb(i);
	    f(temp,i);
	    temp.pop_back();
	}
	int l=v.size();
    int B[l]={0};
	int a,b,c,d;
	for(int i=0;i<q;i++)
	{
	    cin>>a>>b>>c>>d;
	    a--;b--;
	    for(int j=0;j<l;j++)
	    {
	        if((v[j][b]-v[j][a])==c)B[j]+=d;
	    }
	}
	int maxm=-1;
	loop(l)maxm=max(B[i],maxm);
	cout<<maxm;
	return;
}
int32_t main() 
{ 
	fast;
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0; 
}

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

int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  
  while(A > 0 && C > 0){
    C -= B;
    if(C <= 0){
      cout << "Yes" << endl;
      return(0);
    }
    A -= D;
    if(A <= 0){
      cout << "No" << endl;
    }
  }
  
  return(0);
}

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC165B
{
    class Program
    {
        static void Main(string[] args)
        {
            long X = long.Parse(Console.ReadLine());
            decimal kingaku = 100;
            decimal rishi = 1.01m;
            int i = 0;
            while (kingaku < X)
            {
                kingaku *= rishi;
                kingaku = Math.Truncate(kingaku);
                i += 1;
            }
            Console.WriteLine(i);
        }
    }
}


Measured memory_bytes: 27540
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) a.begin(),a.end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=2e5;
const int INF=1e9;
int main(){
	string s;cin>>s;
	char a;
	rep(i,0,s.size()){
		a=s.at(i);
		if(i%2==0){
			if(a=='R'||a=='U'||a=='D') continue;
			else{ cout<<"No"<<endl; return 0; }
		}if(i%2==1){
			if(a=='L'||a=='U'||a=='D') continue;
			else{ cout<<"No"<<endl; return 0; }
		}
	}cout<<"Yes"<<endl;
}

Measured memory_bytes: 256