akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h> 
#define FASTIO
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
 
#ifdef FASTIO
#define scanf abacaba
#define printf abacaba
#endif
 
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
 
using namespace std;
 
const int MX = 307;
 
ld f[MX + 5][MX + 5][MX + 5];
 
int main() {
    int n;
    cin >> n;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x == 1) {
            c1++;
        } else if (x == 2) {
            c2++;
        } else {
            c3++;
        }
    }
 
    for (int k = 0; k < MX; k++) {
        for (int j = 0; j + k < MX; j++) {
            for (int i = 0; i + j + k < MX; i++) {
                if (i == 0 && j == 0 && k == 0) {
                    continue;
                }
                if (i + j + k > MX) {
                    continue;
                }
                ld wait = 1.0 * n / (i + j + k);
                ld pi = 1.0 * i / (i + j + k);
                ld pj = 1.0 * j / (i + j + k);
                ld pk = 1.0 * k / (i + j + k);
 
                if (i) {
                    f[i][j][k] += pi * f[i - 1][j][k];
                }
                if (j) {
                    f[i][j][k] += pj * f[i + 1][j - 1][k];
                }
                if (k) {
                    f[i][j][k] += pk * f[i][j + 1][k - 1];
                }
                f[i][j][k] += wait;
            }
        }
    }
 
    cout.precision(10);
    cout << fixed << f[c1][c2][c3] << "\n";
    return 0;
}

Measured memory_bytes: 119376
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <fstream>
#define mem(i,a) memset(i,a,sizeof(i))
#define PI acos(-1.0)
#define DMAX 100005
#define MOD 20190823
#define eps 1e-8
#define bl bool
#define INF 1e+9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
template<class T> inline void read(T &f){
	f=0;
    T x=1;
    char ch=getchar();
    while(ch<48 || ch>57) {
        if(ch=='-') {
            x=-1;
        }
        ch=getchar();
    }
    while(ch<=57 && ch>=48) {
        f=f*10+ch-'0';
        ch=getchar();
    }
    f*=x;
}
int main(){
	string s;
	cin>>s;
	for(ll i=0;i<s.size();i++){
		if((i+1)%2==0){
			if(s[i]!='L' && s[i]!='U' && s[i]!='D'){
				cout<<"No"<<endl;
				return 0;
			}
		}
		else{
			if(s[i]!='R' && s[i]!='U' && s[i]!='D'){
				cout<<"No"<<endl;
				return 0;
			}
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
struct element
{
	int v,p;
	friend inline bool operator < (const element& A,const element& B)
	{
		return A.v<B.v;
	}
}d[N<<1]; int n,a[N],b[N],p[N],q[N]; long long ans,sa,sb,ret;
int main()
{
	RI i; for (scanf("%d",&n),i=1;i<=n;++i)
	scanf("%d%d",&a[i],&b[i]),d[i].v=a[i],d[i].p=i,
	d[n+i].v=b[i],d[n+i].p=n+i,sa+=a[i],sb+=b[i];
	for (sort(d+1,d+(n<<1)+1),i=1;i<=(n<<1);++i)
	if (d[i].p<=n) p[d[i].p]=i; else q[d[i].p-n]=i;
	for (i=1;i<=n;++i) ret+=d[i].v;
	for (ans=min(sa,sb),i=1;i<=n;++i)
	if (p[i]<=n&&q[i]<=n) ans=min(ans,ret); else
	if (p[i]<=n&&q[i]>n) ans=min(ans,ret+d[q[i]].v-(p[i]!=n?d[n].v:d[n-1].v)); else
	if (p[i]>n&&q[i]<=n) ans=min(ans,ret+d[p[i]].v-(q[i]!=n?d[n].v:d[n-1].v)); else
	ans=min(ans,ret+d[p[i]].v+d[q[i]].v-d[n].v-d[n-1].v);
	return printf("%lld",ans),0;
}

Measured memory_bytes: 6892
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int h,a;
	cin >> h >> a;

	cout << ceil((float)h/(float)a) ;

}


Measured memory_bytes: 256
"""

xを小さい順に見ていく
あるY以下で-x-yが最大のものと, -x+yが最大の物を保持
Yを座圧しておく
→セグ木

"""

#0-indexed , 半開区間[a,b)
#calc変更で演算変更
class SegTree:

    def __init__(self,N,first):
        self.NO = 2**(N-1).bit_length()
        self.First = first
        self.data = [first] * (2*self.NO)

    def calc(self,l,r):
        return max(l,r)

    def update(self,ind,x):
        ind += self.NO - 1
        self.data[ind] = max( x , self.data[ind] )
        while ind >= 0:
            ind = (ind - 1)//2
            self.data[ind] = self.calc(self.data[2*ind+1],self.data[2*ind+2])

    def query(self,l,r):
        L = l + self.NO
        R = r + self.NO
        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s , self.data[R-1])
            if L & 1:
                s = self.calc(s , self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return s

from sys import stdin
N = int(stdin.readline())

xy = []
dic = {}
lis = []
for i in range(N):

    x,y = map(int,stdin.readline().split())
    xy.append((x,y))

    if y not in dic:
        dic[y] = 0
        lis.append(y)

xy.sort()
lis.sort()
for i in range(len(lis)):
    dic[lis[i]] = i

LT = SegTree(len(lis),float("-inf"))
RT = SegTree(len(lis),float("-inf"))
ans = 0

for X,Y in xy:

    ans = max(ans , X+Y+LT.query(0,dic[Y]+1))
    ans = max(ans , X-Y+RT.query(dic[Y],len(lis)))

    LT.update(dic[Y] , -X-Y )
    RT.update(dic[Y] , -X+Y )

print (ans)


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

int main(){
    string s;
    cin >> s;
    if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]){
        cout << "Bad" << endl;
    }else{
        cout << "Good" << endl;
    }
}

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

int main() {
    int n, m;
    cin >> n >> m;

    int b[1000] = {}, a[1000][1000] = {};

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

    for (int j = 0; j < m; j++) {
        cin >> b[j];
    }

    for (int i = 0; i < n; i++) {
        int c = 0;
        for (int j = 0; j < m; j++) {
            c += a[i][j] * b[j];
        }

        cout << c << endl;
    }
 
}

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



int main() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    
    int ans = 0;
    rep(i,n-1) {
        if(s[i] == s[i+1]) {
            ans++;
        }
    }
    
    ans = min(ans+2*k, n-1);
    
    cout << ans << endl;
    
    
    return 0;
}




Measured memory_bytes: 3728
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cstddef>
#include<queue>
#include <math.h>
using namespace std;

int main()
{
    int A, B;
    cin >> A >> B;
    cout << max(0,A - 2*B) <<endl;
    return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

ll c[51][51];

ll com(ll n, ll k){
    if(k == 0) return 1;
    if(k == n) return 1;
    if(k > n) return 0;
    if(c[n][k]) return c[n][k];
    return c[n][k] = com(n - 1, k) + com(n - 1, k - 1);
}

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    ll v[51];
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    sort(v, v + n, greater<ll>());
    for(int i = 0; i <= 50; i++){
        for(int j = 0; j <= 50; j++){
            c[i][j] = 0;
        }
    }
    ll lim = v[a - 1];
    ll sum = 0;
    for(int i = 0; i < a; i++){
        sum += v[i];
    }
    printf("%.15f\n", sum * 1.0 / a);
    int lsum = 0;
    int lbf = 0;
    for(int i = 0; i < n; i++){
        if(v[i] == lim){
            lsum++;
            if(i < a) lbf++;
        }
    }
    if(v[0] != lim) cout << com(lsum, lbf) << endl;
    else{
        ll ans = 0;
        for(int i = a; i <= b; i++){
            ans += com(lsum, i);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const int INF = 1e9;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

int main() {
    int A,B;
    cin >> A >> B;
    if(A > B) {
        for(int i = 0;i < A;i++) {
            cout << B;
        }
        cout << endl;
    }
    else {
        for(int i = 0;i < B;i++) {
            cout << A;
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////


int main() {

	ll Q, H, S, D, N;
	cin >> Q >> H >> S >> D >> N;

	ll L = min(4 * Q, min(2 * H, S));

	cout << min(2 * L, D)*(N / 2) + L * (N % 2);

	
	
	system("PAUSE");

}





Measured memory_bytes: 504
#include<stdio.h>
#include <string.h>
int main(){
  char wed[10];
  scanf("%s",wed);
  char Rainy[10]={"Rainy"};
  char Cloudy[10]={"Cloudy"};
  char Sunny[10]={"Sunny"};
if(strcmp(wed,Cloudy)==0){
  printf("%s",Rainy);
}
if(strcmp(wed,Rainy)==0){
  printf("%s",Sunny);
}
if(strcmp(wed,Sunny)==0){
  printf("%s",Cloudy);
}
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
 
using namespace std;
using Int = long long int;
using UInt = unsigned long long int;
using VI = vector<long long int>;

int main(void) {
    Int H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << (H - h) * (W - w) << endl;
    return 0;
}



Measured memory_bytes: 3520
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string ans = string.Empty;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '0') ans = ans + "0";
                else if (s[i] == '1') ans = ans + "1";
                else if (s[i] == 'B' && ans.Length > 0) ans = ans.Substring(0, ans.Length - 1);
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

struct coord {
    double x;
    double y;
};

void kock(int n, coord p1, coord p2){
    coord s,u,t;
    if (n == 0){
        return;
    }
    s.x = (2 * p1.x + p2.x)/3.0;
    s.y = (2 * p1.y + p2.y)/3.0;
    t.x = (p1.x + 2 * p2.x)/3.0;
    t.y = (p1.y + 2 * p2.y)/3.0;
    
    double ang = M_PI*60/180.0;
    u.x = (t.x - s.x) * cos(ang) - (t.y - s.y) * sin(ang) + s.x;
    u.y = (t.x - s.x) * sin(ang) + (t.y - s.y) * cos(ang) + s.y; 
    kock(n-1, p1, s);
    cout << setprecision(8) << s.x << " " << s.y << endl;
    kock(n-1, s, u);
    cout << setprecision(8) << u.x << " " << u.y << endl;
    kock(n-1, u, t);
    cout << setprecision(8) << t.x << " " << t.y << endl;
    kock(n-1, t, p2);
}

int main(void){
    int n;
    coord p1, p2;
    p1.x = 0;
    p1.y = 0;
    p2.x = 100;
    p2.y = 0;
    cin >> n;
    cout << setprecision(8) << p1.x << " " << p1.y << endl;
    kock(n, p1, p2);
    cout << setprecision(8) << p2.x << " " << p2.y << endl;
}



Measured memory_bytes: 3244
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>

using namespace std;

int main() {
    long long N, K;
    
    cin >> N >> K;
    if (K % 2)
        cout << (N / K) * (N / K) * (N / K) << endl;
    else {
        K /= 2;
        long long ans= ((N / K + 1) / 2) * ((N / K + 1) / 2) * ((N / K + 1) / 2);
        ans += ((N / K) / 2) * ((N / K) / 2) * ((N / K) / 2);
        cout << ans << endl;
    }
    
}


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

int main()
{
  int x;
  cin>>x;
  if(x>=400 and x<600) cout<<8;
  else if(x>=600 and x<800) cout<<7;
  else if(x>=400 and x<1000) cout<<6;
  else if(x>=1000 and x<1200) cout<<5;
  else if(x>=1200 and x<1400) cout<<4;
  else if(x>=1400 and x<1600) cout<<3;
  else if(x>=1600 and x<1800) cout<<2;
  else cout<<1;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;

struct UnionFind{
  vector<int> par;

  UnionFind(int N): par(N){
    for(int i=0;i<N;i++) par[i]=i;
  }

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

  void unite(int x,int y){
    int rx=root(x);
    int ry=root(y);
    if(rx!=ry) par[rx]=ry;
  }

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

//int cnt[200000][200000];

int main(){
    int N,K,L; cin>>N>>K>>L;
    
    UnionFind road(N),rail(N);
    
    int s,g;
    for (int i = 0; i < K; ++i) {
        cin>>s>>g; s--; g--;
        road.unite(s,g);
    }

    for (int i = 0; i < L ; ++i) {
        cin>>s>>g; s--; g--;
        rail.unite(s,g);
    }
    map<pair<int,int>,int> mp;
    for (int i = 0; i < N; ++i) {
        pair<int,int> pairs={road.root(i),rail.root(i)};
        auto itr = mp.find(pairs);
        if(itr!=mp.end()) {
            mp[pairs]++;
        }else{
            mp[pairs]=1;
        }
    }

    for (int i = 0; i < N-1; ++i) {
        cout<<mp[{road.root(i),rail.root(i)}]<<" ";
    }
    cout<<mp[{road.root(N-1),rail.root(N-1)}]<<endl;
    return 0;
}

Measured memory_bytes: 13568
A, B, C = list(map(int, input().strip().split()))
K = int(input().strip())

count = 0
while not(A < B):
  B = B*2
  count+=1
while not(B < C):
  C = C*2
  count += 1
if count <= K:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=1e9;
const ll INFS=1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
 
int main() {
  int n;
  cin>>n;
  map<int,int> mp;
  rep(i,n){
    int a;
    cin>>a;
    if(mp[a]!=1){
      mp[a]=1;
    }else{
      mp[a]=0;
    }
  }
  int ans=0;
  for(auto x:mp){
    if(x.second==1){
      ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 8280
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e18;
const ll MOD=1e9+7;

struct segtree{
    vector<ll> dat;
    int size;
    segtree(int n):dat(2*n-1,(1LL<<31)-1),size(n){};
    void update(int i,ll a){
        i+=this->size-1;
        dat[i]=a;
        while(i>0){
            i=(i-1)/2;
            dat[i]=min(dat[i+2+1],dat[i*2+2]);
        }
    }
    ll query(int a,int b){
        return querysub(a,b,0,0,this->size);
    }
    ll querysub(int a,int b,int k,int l,int r){
        if(r<=a||b<=l) return (1LL<<31)-1;
        else if(a<=l&&r<=b) return dat[k];
        else{
            ll vl=querysub(a,b,k*2+1,l,(l+r)/2);
            ll vr=querysub(a,b,k*2+2,(l+r)/2,r);
            return min(vl,vr);
        }
    }
};
ll n,k;
vector<ll> a;
bool C(ll x){
    int cnt=0;
    for(int i=0;i<n;++i){
        if(a[i]>x) cnt+=a[i]/x;
    }
    return cnt<=k;
}
int main(){
    cin>>n>>k;
    ll h=0;
    a=vector<ll>(n);
    for(int i=0;i<n;++i){
        cin>>a[i];
        h=max(h,a[i]);
    }
    ll l=0;
    while(h-l>1){
        ll m=(h+l)/2;
        if(C(m)) h=m;
        else l=m;
    }
    cout<<h<<endl;
}

Measured memory_bytes: 4796
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;
const double INF = 1000000000.0;

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

    int n;
    cin >> n;

    double u1 = -INF, u2 = -INF, u3 = -INF;
    double d1 =  INF, d2 =  INF, d3 =  INF;
    double l1 =  INF, l2 =  INF, l3 =  INF;
    double r1 = -INF, r2 = -INF, r3 = -INF;

    for (int i = 0; i < n; i++) {
        double x, y;
        char d;
        cin >> x >> y >> d;

        if (d == 'D') {
            u1 = max(u1, y);
            d3 = min(d3, y);
            l2 = min(l2, x);
            r2 = max(r2, x);
        } else if (d == 'U') {
            u3 = max(u3, y);
            d1 = min(d1, y);
            l2 = min(l2, x);
            r2 = max(r2, x);
        } else if (d == 'R') {
            u2 = max(u2, y);
            d2 = min(d2, y);
            l1 = min(l1, x);
            r3 = max(r3, x);
        } else if (d == 'L') {
            u2 = max(u2, y);
            d2 = min(d2, y);
            l3 = min(l3, x);
            r1 = max(r1, x);
        }
    }

    // ぶつかる時間のvector
    vector <double> vec;
    vec.push_back(0);

    // Up
    vec.push_back(u1 - u2);
    vec.push_back(u2 - u3);
    vec.push_back((u1 - u3) / 2);

    // Down
    vec.push_back(d2 - d1);
    vec.push_back(d3 - d2);
    vec.push_back((d3 - d1) / 2);

    // Left
    vec.push_back(l2 - l1);
    vec.push_back(l3 - l2);
    vec.push_back((l3 - l1) / 2);

    // Right
    vec.push_back(r1 - r2);
    vec.push_back(r2 - r3);
    vec.push_back((r1 - r3) / 2);

    double ans = 40000000000000000;
    for (double d : vec) {
        if (d < 0) continue;
        double u = max({u2, u1 - d, u3 + d});
        double f = min({d2, d1 + d, d3 - d});
        double l = min({l2, l1 + d, l3 - d});
        double r = max({r2, r1 - d, r3 + d});

        ans = min(ans, (u - f) * (r - l));
    }

    cout << fixed << setprecision(12) << ans << "\n";
    return 0;
}

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

int main() {
  int N, count = 0;
  bool flag = true;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  while (true) {
    for (int i = 0; i < N; i++) {
      if (A.at(i) % 2 != 0) {
        flag = false;
        break;
      }
      else A.at(i) /= 2;
    }
    if (flag == false) break;
    count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <locale>
using namespace std;
#define MS0(I) memset(I, 0, sizeof(I));
#define MS1(I) memset(I, -1, sizeof(I));
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, s, n) for(int i = (s); i < (n); ++i)
#define per1(i, a, b) for(int i = a; i >= b; --i)
#define DRI(A) int A; scanf("%d", &A);
#define DRII(A, B) int A, B; scanf("%d %d", &A, &B);
#define DRIII(A, B, C) int A, B, C; scanf("%d %d %d", &A, &B, &C);
#define MP make_pair 
#define pb push_back
#define F first
#define S second
#define ALL(I) (I).begin(), (I).end()
typedef const void CV;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int INF = (int)1e9;
const int mod = (int)1e9+7;
const int MAX = (int)3e2+5;
char store[MAX][MAX];
int main(void){
	DRI(n);
	rep(i, n) scanf("%s", store[i]);
	LL ans = 0;
	rep(i, n){
		bool flag = 1;
		rep(j, n){
			if(!flag) break;
			rep(k, n){
				if(store[j][k] != store[(k+n-i)%n][(i+j)%n]){
					flag = 0; break;
				}
			}
		}
		if(flag) ans++;
	}


	printf("%lld", ans*n);
	return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<double> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    vector<double> dp(N+1, 0);
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = N; j >= 1; j--) {
            dp[j] = dp[j]*(1-p[i])+dp[j-1]*p[i];
        }
        dp[0] *= 1-p[i];
    }
    double ans = 0;
    for (int i = (N+1)/2; i <= N; i++) ans += dp[i];
    cout << setprecision(15) << ans << endl;
    return 0;
}

Measured memory_bytes: 3864
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 0
#define LIM 1000000007
#define UP 1
#define DOWN 2


int main(){

	lli n;
	map<lli,lli> m;
	cin>>n;
	REP(i,n){
		lli tmp;
		cin>>tmp;
		m[tmp]++;
	}

	lli flag=0;
	for(auto e:m){
		if(n%2==0){
			if(e.first == 0 && e.second==2){
			}
			else if(e.second==2){
			}
			else{
				flag=1;
				break;
			}
		}
		if(n%2==1){
			if(e.first == 0 && e.second==1){
			}
			else if(e.second==2){
			}
			else{
				flag=1;
				break;
			}
		}
	}
	if(flag==1)cout<<0<<endl;
	else{
		lli ans=1;
		REP(i,n/2){
			ans*=2;
			ans%=LIM;
		}
		cout<<ans<<endl;
	}

	return 0;
}

Measured memory_bytes: 4224
#include <stdio.h>

int main(void){
    int n;
    scanf("%d",&n);
    switch(n%4){
        case 1:printf("Christmas");break;
        case 2:printf("Christmas Eve Eve Eve");break;
        case 3:printf("Christmas Eve Eve");break;
        case 0:printf("Christmas Eve");break;
    }  
    return 0;
}

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

inline int parent(int i){
  return i / 2;
}

inline int left(int i){
  return 2 * i;
}

inline int right(int i){
  return 2 * i + 1;
}

int A[2000001], n = 0;

void maxHeapify(int i){
  int largest;
  int l = left(i);
  int r = right(i);
  if(l <= n && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= n && A[r] > A[largest]) largest = r;
  if(largest != i){
    int tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    maxHeapify(largest);
  }
}

void insert(int x){
  n++;
  int i = n;
  A[i] = x;
  while(i > 1 && A[parent(i)] < A[i]){
    int tmp = A[parent(i)];
    A[parent(i)] = A[i];
    A[i] = tmp;
    i = parent(i);
  }
}

int extract(){
  int ret = A[1];
  A[1] = A[n];
  n--;
  maxHeapify(1);
  return ret;
}

int main(){
  string cmd;
  int x;
  while(true){
    cin >> cmd;
    if(cmd == "insert"){
      cin >> x;
      insert(x);
    }
    else if(cmd == "extract") cout << extract() << endl;
    else break;
  }
  return 0;
}



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

int main() {
	int a, b;
	cin >> a;
	for (b = 1;b < 10; b++){
		if (a % b == 0 && a / b < 10) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No";
	cout<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] h = new int[n];
		TreeMap<Integer, Integer> yoi = new TreeMap<>();
		int total = 0;

		for (int i = 0; i < n; i++) {
			h[i] = sc.nextInt();
			yoi.put(i + 1, 1);
		}

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			if (h[a - 1] > h[b - 1]) {
				yoi.put(b, 0);
			} else if (h[a - 1] == h[b - 1]) {
				yoi.put(a, 0);
				yoi.put(b, 0);
			} else {
				yoi.put(a, 0);
			}
		}

		for (Integer key : yoi.keySet()) {
			total += yoi.get(key);
		}

		System.out.println(total);
	}
}


Measured memory_bytes: 69356
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <queue>
using namespace std;
typedef long long ll;

ll xorfrom1(ll n){
    if(n%4==1)return 1;
     if(n%4==2)return n+1;
     if(n%4==3)return 0;
     if(n%4==0)return n;
     return 0;
}

int main(){
  ll a,b;cin>>a>>b;
  cout<<(xorfrom1(b)^xorfrom1(a-1));
}

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

int main() {
	// 코틀린 ,문자열 알고리즘 보기, 앳코더, (시간되면 코드포스까지)
	ios_base::sync_with_stdio(false); cin.tie(NULL); //9 90 900 
	int n; cin >> n;
	vector<ll> a(n + 1);
	vector<ll> b(n);
	for (int i = 0; i < n + 1; i++)cin >> a[i];
	for (int i = 0; i < n; i++)cin >> b[i];
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (b[i] == 0)continue; 
		ll cnt = min(a[i], b[i]); 
		ans += cnt;
		a[i] -= cnt; b[i] -= cnt; 
		if (b[i] > 0) {
			cnt = min(a[i + 1], b[i]);
			a[i + 1] -= cnt; b[i] -= cnt;
			ans += cnt;
		}
	}
	cout << ans << '\n';


	
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <atcoder/mincostflow>
using namespace std;
using ll = long long;
const int INF = 1 << 30;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    auto A = vector<vector<int>>(N, vector<int>(N));
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> A[i][j];
        }
    }

    // A[i][j] : graph[i * N + j]
    // Line i : graph[N * N + i]
    // Row j : graph[N * N + N + j]
    atcoder::mcf_graph<int, ll> graph(N * N + 2 * N + 2);
    const int start = N * N + 2 * N;
    const int goal = N * N + 2 * N + 1;
    graph.add_edge(start, goal, N * K, INF);
    for(int i=0; i<N; i++)
    {
        graph.add_edge(start, N * N + i, K, 0);
        graph.add_edge(N * N + N + i, goal, K, 0);
    }
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            graph.add_edge(N * N + i, i * N + j, 1, INF - A[i][j]);
            graph.add_edge(i * N + j, N * N + N + j, 1, 0);
        }
    }

    vector<string> mp(N, string(N, '.'));
    auto update_mp = [&]{
        auto edges = graph.edges();
        for(auto edge : edges)
        {
            if(edge.flow == 0) continue;
            if(N * N <= edge.from && edge.from < N * N + N)
            {
                int i = edge.to / N;
                int j = edge.to % N;
                mp[i][j] = 'X';
            }
            else if(N * N + N <= edge.to && edge.to < N * N + 2 * N)
            {
                int i = edge.from / N;
                int j = edge.from % N;
                mp[i][j] = 'X';
            }
        }
    };
    auto f = graph.flow(start, goal, N * K);
    cout << 1LL * f.first * INF - f.second << '\n';

    update_mp();
    for(auto s : mp) cout << s << '\n';


    return 0;
}


Measured memory_bytes: 4288
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long  
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define prec(y,x) fixed<<setprecision(y)<<x
#define inf 1e18
#define pi 3.1415926535
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    set<string> s;
    cin>>n;
    string p;
    for(int i=1;i<=n;i++)
    {
        cin>>p;s.insert(p);
    }
    cout<<s.size();
    return 0;
}
//make all values ll

Measured memory_bytes: 19276
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    # sys.stdin = open("sample.txt")
    a, b, x = Scanner.map_int()

    def func(n, x):
        if n == -1:
            return 0
        else:
            return n // x + 1
    print(func(b, x) - func(a - 1, x))


if __name__ == "__main__":
    main()


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

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

    string S;
    cin >> S;

    int L[Q];
    int R[Q];

    for(int i = 0; i < Q; i++) cin >> L[i] >> R[i];

    int cnt_array[N] = {0};
    int cnt = 0;
    for(int i = 1; i < N; i++)
    {
        if(S[i-1] == 'A' and S[i] == 'C') cnt++;
        cnt_array[i] = cnt;
    }

    for(int i = 0; i < Q; i++)
    {
        int ans = cnt_array[R[i]-1] - cnt_array[L[i]-1];
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 2176
#include "bits/stdc++.h"
 
using namespace std;
typedef int64_t ll;
typedef vector<int64_t> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<vd> vvd;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())
int num[3][3];
int main(){
  ll n,k,ans=0;bool ok=true;
  cin>>n>>k;
  
  vll a(n), b(40);
  
  REP(i,n){
    cin>>a[i];
    bitset<40> bit(a[i]);
    REP(j,40){
      if(bit.test(j)){b[j]++;}
    }
  }
  REP(j,40){
    if((k>>j)&1){ans+=(1LL<<j)*(n-b[j]);}
    else{ans+=(1LL<<j)*b[j];}
  }
  bitset<40> K(k);
  REP(i,40){
    ll f=0;
    if(!((k>>i)&1)){continue;}
    REP(j,i){
      f+=(1LL<<j)*max(b[j],n-b[j]);
    }
    f+=(1LL<<i)*b[i];
    FOR(j,i+1,40){
      if((k>>j)&1){f+=(1LL<<j)*(n-b[j]);}
      else{f+=(1LL<<j)*b[j];}
    }
    ans=max(ans,f);
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 1024
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

n, x = na()
l = na()
d = [0 for _ in range(n + 1)]

d[0] = 0
res = 1
for i in range(1, n + 1):
    d[i] = d[i - 1] + l[i - 1]
    if d[i] <= x:
        res += 1

print(res)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstring>
#include <cmath>
 
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MP make_pair
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()

using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> P;

const int INF = 1<<29;

int gcd(int m, int n){
	return (n==0?m:gcd(n, m%n));
}

int main(){
	int n, a, b;
	cin >> n >> a;
	rep(i, n-1){
		cin >> b;
		a = gcd(a, b);
	}

	vector<int> ans;
	for(int i = 1; i*i <= a; i++){
		if(a%i == 0){
			ans.push_back(i);
			ans.push_back(a/i);
		}
	}
	sort(all(ans));
	ans.erase(unique(all(ans)), ans.end());
	rep(i, ans.size()){
		cout << ans[i] << endl;
	}

    return 0;
}

Measured memory_bytes: 1220
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1ll<<60;

ll field[210][210];
ll dp[10][10];

int main(int argc, char **argv)
{
	ll h, w; cin >> h >> w;
	for (ll i = 0; i < 10; ++i)
		for (ll j = 0;j < 10; ++j)
			cin >> dp[i][j];

	for (ll i = 0; i < h; ++i)
		for (ll j = 0; j < w; ++j)
			cin >> field[i][j];

	for (ll k = 0; k < 10; ++k)
		for (ll i = 0; i < 10; ++i)
			for (ll j = 0; j < 10; ++j)
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);


	ll res{0};
	for (ll i = 0; i < h; ++i)
		for (ll j = 0; j < w; ++j)
		{
			if (field[i][j] == -1) continue;
			res += dp[field[i][j]][1];
		}
	std::cout << res << std::endl;
}



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

using System.Collections;

class Program
{
    static void Main()
    {
        string S = Console.ReadLine();

        if (canBeMMYY(S) && canBeYYMM(S))
        {
            Console.WriteLine("AMBIGUOUS");
        }
        else if (canBeMMYY(S))
        {
            Console.WriteLine("MMYY");
        }
        else if (canBeYYMM(S))
        {
            Console.WriteLine("YYMM");
        }
        else
        {
            Console.WriteLine("NA");
        }
        
    }

    static bool canBeYYMM(string s)
    {
        int left = int.Parse(s.Substring(0, 2));
        int right = int.Parse(s.Substring(2, 2));

        if (1 <= right && right <= 12)
        {
            return true;
        }
        else return false;
    }

    static bool canBeMMYY(string s)
    {
        int left = int.Parse(s.Substring(0, 2));
        int right = int.Parse(s.Substring(2, 2));

        if (1 <= left && left <= 12)
        {
            return true;
        }
        else return false;
    }
}


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

int main() {
  int n;
  while (true) {
    cin >> n;
    if (n == 0) break;

    vector<int> taro(n); for (int i = 0; i < n; i++) cin >> taro[i];
    vector<int> card(2 * n); for (int i = 0; i < n; i++) card[taro[i] - 1]++;
    vector<int> hanako(n); int j = 0;
    for (int i = 0; i < 2 * n; i++) if (card[i] == 0) hanako[j] = i + 1, j++;
    sort(taro.begin(), taro.end());

    int turn = 0, place = 0;
    while (!taro.empty() && !hanako.empty()) {
      if (turn % 2 == 0) {
        for (int i = 0; i < taro.size(); i++) {
          if (taro[i] > place) {
            place = taro[i], taro.erase(taro.begin() + i);
            break;
          } else if (i == taro.size() - 1) place = 0;
        }
      } else {
        for (int i = 0; i < hanako.size(); i++) {
          if (hanako[i] > place) {
            place = hanako[i], hanako.erase(hanako.begin() + i);
            break;
          } else if (i == hanako.size() - 1) place = 0;
        }
      }

      turn++;
    }

    cout << hanako.size() << endl << taro.size() << endl;
  }

  return 0;
}


Measured memory_bytes: 3028
// https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b
#include <bits/stdc++.h>

using namespace std;

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

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

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

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

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

	ll ans=1e12;
	rep(bit, (1<<n)){
		if(__builtin_popcount(bit)<k)continue;
		vector<int> pos, tmp=a;
		rep(i,n){
			if(bit&(1<<i))pos.push_back(i);
		}
		ll res=0;
		int h=0;
		for(auto p:pos){
			if(tmp[p]<=h){
				res+=h+1-tmp[p];
				tmp[p]=h+1;
			}
			h=tmp[p];
		}
		bool is_valid=true;
		h=0;
		rep(i,n){
			if(tmp[i]<=h&&(bit&(1<<i)))is_valid=false;
			h=max(tmp[i],h);
		}
		if(is_valid)ans=min(ans,res);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3600
#coding:utf-8
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a_new = list(map(lambda x: x - 1, a))
s = 0

for i in range(0, n):
    s += b[a_new[i]]
    if i != 0 and a_new[i] == a_new[i-1] + 1:
        s += c[a_new[i-1]]

print(s)

Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

int n, m;
map <int, long long> mp;

int main() { 

  scanf("%d %d", &n, &m);

  for (int i = 0; i < n; i++) {
    int cost, cnt;
    scanf("%d %d", &cost, &cnt);
    mp[cost] += cnt;
  }

  long long ans = 0;
  for (auto x : mp) {
    int cost = x.first;
    long long cnt = x.second;
    long long buy = min(1ll * m, cnt);
    ans += 1ll * buy * cost;
    m -= buy;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
int n;
char s[20];
int psum, ans;
int main() {
	scanf("%s", s+1);
	n = strlen(s+1);
	for (int i = 1; i <= n; i ++) {
		int x = s[i] - '0';
		if (x) ans = max(ans, psum + x-1 + 9 * (n-i));
		psum += x;
	}
	cout << max(ans, psum) << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int A = sc.nextInt();
		sc.close();

		if (H % A == 0) {
			System.out.println(H / A);
		} else {
			System.out.println(H / A + 1);
		}
	}
}


Measured memory_bytes: 22996
using System;
using System.Collections.Generic;
using System.Linq;

class ShiftOnly
{
    static void Main(string[] args)
    {
        int m = 0; // 2で割った回数
        int n = int.Parse(Console.ReadLine()); // 扱うデータの個数
        List<int> blackBoardNum = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();

        while(blackBoardNum.All(x => (x % 2) == 0))
        {
            blackBoardNum = blackBoardNum.ConvertAll(x => x / 2);
            m++;
        }

        Console.WriteLine($"{m}");

        return;
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

using namespace std;
map<long long, long long> lpath[100001];
long long dist[100001] = {};
int visited[100001] = {};
long long n;



int dfs(long long s, long long cost){
  map<long long, long long> mp_dist = lpath[s];
  visited[s] = 1;
  for (auto it = mp_dist.begin();it != mp_dist.end();it++) {
    if (visited[it->first] == 0) {
      //      cout << s << "\t" << it->first << "\t" << it->second << endl;
      dist[it->first] = cost + it->second;
      //      visited[it->first] = 1;
      dfs(it->first, dist[it->first]);
    }
  }
  return(0);
}

int main(){
  long long q, k;
  cin >> n;
  for (int i=0;i<n-1;i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    lpath[a][b] = c;
    lpath[b][a] = c;
  }
  cin >> q >> k;
  dfs(k, 0);


  for (int i=0;i<q;i++) {
    long long x, y;
    cin >> x >> y;
    cout << dist[x] + dist[y] << endl;
  }
  return(0);
}


Measured memory_bytes: 41984
#include<iostream>
#include<vector>
using namespace std;
void reduce_surface_area(int x,int y,int a,int w,int h,vector<vector<bool>>(&b)) {
	if (a == 1) {
		for (int i(0); i < h; i++) {
			for (int j(0); j < x; j++) {
				b[i][j] = false;
			}
		}
	}
	if (a == 2) {
		for (int i(0); i < h; i++) {
			for (int j(x); j < w; j++) {
				b[i][j] = false;
			}
		}
	}
	if (a == 3) {
		for (int i(0); i < y; i++) {
			for (int j(0); j < w; j++) {
				b[i][j] = false;
			}
		}
	}
	if (a == 4) {
		for (int i(y); i < h; i++) {
			for (int j(0); j < w; j++) {
				b[i][j] = false;
			}
		}
	}
}
int return_surface_area(int w,int h,vector<vector<bool>>b) {
	int surface_area(0);
	for (int i(0); i < h; i++) {
		for (int j(0); j < w;j++) {
			if (b[i][j] == true)surface_area++;
		}
	}
	return surface_area;
}
int main(void) {
	//入力
	int w, h, n;
	cin >> w >> h >> n;
	vector<int>x;
	vector<int>y;
	vector<int>a;
	for (int i(0); i < n; i++) {
		int xtmp, ytmp, atmp;
		cin >> xtmp >> ytmp >> atmp;
		x.push_back(xtmp);
		y.push_back(ytmp);
		a.push_back(atmp);
	}
	//初期化
	vector<vector<bool>>b;
	for (int i(0); i < h; i++) {
		vector<bool>tmp;
		for (int j(0); j < w; j++) {
			tmp.push_back(true);
		}
		b.push_back(tmp);
	}
	for (int i(0); i < n; i++) {
		reduce_surface_area(x[i],y[i],a[i],w,h,b);
	}
	cout << return_surface_area(w,h,b) << endl;
	return 0;
}

Measured memory_bytes: 256
N, L = map(int, input().split())
total = 0

if L>=0:
    for i in range(1,N,1):
        total = total + L  + i
else:
    if -L<N:
        for i in range(N):
            total = total + L + i
    else:
        for i in range(N-1):
            total = total + L + i

print(total)

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

using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int dp[100001];
int main() {
	int N;
	cin >> N;
	fill(dp, dp + (N + 1), 1 << 30);
	dp[0] = 0;
	for (int i = 0; i < N; i++) {
		dp[i + 1] = min(dp[i + 1], dp[i] + 1);
		for (int j = 6; i + j <= N; j *= 6) dp[i + j] = min(dp[i + j], dp[i] + 1);
		for (int j = 9; i + j <= N; j *= 9) dp[i + j] = min(dp[i + j], dp[i] + 1);
	}
	cout << dp[N] << endl;
}

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

namespace B_YYMM_MMYY
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            int a = int.Parse(s.Substring(0, 2));
            int b = int.Parse(s.Substring(2, 2));
            string result;

            if (1 <= a && a <= 12)
            {
                if (1 <= b && b <= 12)
                {
                    result = "AMBIGUOUS";
                }
                else
                {
                    result = "MMYY";
                }
            }
            else
            {
                if (1 <= b && b <= 12)
                {
                    result = "YYMM";
                }
                else
                {
                    result = "NA";

                }
            }

            Console.Write(result);
            //Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
typedef long long ll;
#define INF 1000000000
#define MOD 1000000007
int dx[4]={1,0,-1,0},dy[4]={0,-1,0,1};
using namespace std;
int main(void){
    string s;
    cin>>s;
    string t="keyence";
    int m=s.size()-1,n=t.size()-1;
    int diff=m-n;
    bool first=true;
    bool ans=true;
    while(n>=0 and m>=0){
        if(s[m]!=t[n]){
            if(first==false){
                ans=false;
                break;
            }
            m-=diff;
            first=false;
        }else{
            m--;
            n--;
        }
    }
    if(ans and n<0){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
 return 0;   
}

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-c<=d&&a-c>=(-d)) cout<<"Yes"<<endl;
  else if(((a<=b&&b<=c)||(c<=b&&b<=a))&&a-c<=2*d&&a-c>=(-d*2)){
    if((a-b<=d&&a-b>=(-d))&&(c-b<=d&&c-b>=(-d))) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  else cout<<"No"<<endl;
  return 0 ;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int N;
vector<pair<int, int> > x;
int main() {
  cin >> N;
  x = vector<pair<int,int>>(N);
  for(int i = 0; i < N;i++) {
    cin >> x[i].first;
    x[i].first--;
    x[i].second = i;
  }
  vector<int> answer[2];
  for(int k = 0; k < 2; k++) {
    std::sort(x.begin(), x.end());
    for(int i = 0; i < N; i++) {
      if(x[i].first - ((int)answer[k].size() + i) < x[i].second) {
        cout << "No" << endl;
        return 0;
      }
      for(int j = 0; j < x[i].second; j++) {
        answer[k].push_back(x[i].second + 1);
      }
    }
    for(int i = 0; i < N; i++) {
      x[i].first = N * N - 1 - x[i].first;
      x[i].second = N - 1 - x[i].second;
    }
    std::sort(x.begin(), x.end());
  }
  cout << "Yes" << endl;
  reverse(answer[1].begin(), answer[1].end());
  for(int i = 0; i < answer[1].size(); i++) {
    answer[1][i] = N + 1 - answer[1][i];
  }
  int cur = 0;
  int last = 0;
  bool first = true;
  for(int i = 0; i < N; i++) {
    for(int j = last; j < x[i].first; j++) {
      if(!first)cout << " ";
      first = false;
      cout << answer[cur >= answer[0].size() ? 1 : 0][cur >= answer[0].size() ? cur - answer[0].size() : cur];
      cur++;
    }
      if(!first)cout << " ";
      first = false;
    cout << x[i].second + 1;
    last = x[i].first + 1;
  }
  for(int j = last; j < N * N; j++) {
      if(!first)cout << " ";
      first = false;
    cout << answer[cur >= answer[0].size() ? 1 : 0][cur >= answer[0].size() ? cur - answer[0].size() : cur];
    cur++;
  }
  cout << endl;

}

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

char s;
void input() { cin >> s; }
void solve() { cout << ((isupper(s)) ? "A" : "a") << endl; }

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

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

using I = long long;
struct Edge {int from, to; I weight;};
using Graph = vector<vector<Edge>>;
using P = pair<I, int>;

const I M = 1e9 + 7;

vector<I> Dijkstra(auto& G, auto S) {
  vector<I> d(G.size(), -1);
  priority_queue<P, vector<P>, greater<P>> q;
  q.emplace(0, S);
  while(!q.empty()) {
    auto w = q.top().first;
    auto v = q.top().second;
    q.pop();
    if(d[v] != -1) continue;
    d[v] = w;
    for(auto e: G[v]) if(d[e.to] == -1) q.emplace(w + e.weight, e.to);
  }
  return d;
}

vector<I> path(auto& G, auto& d, auto& S, auto q, auto shortest) {
  vector<I> dp(G.size());
  for(auto v=0; v<G.size(); ++v) q.emplace(d[v], v);
  dp[S] = 1;
  while(!q.empty()) {
    auto w = q.top().first;
    auto v = q.top().second;
    q.pop();
    for(auto e: G[v]) if(shortest(d[e.from], e.weight, d[e.to])) (dp[e.to] += dp[e.from]) %= M;
  }
  return dp;
}

int main() {
  int N, m;
  int S, T;
  cin >> N >> m >> S >> T;
  --S; --T;
  Graph G(N);
  for(auto i=0; i<m; ++i) {
    int u, v, d;
    cin >> u >> v >> d;
    --u; --v;
    G[u].push_back({u, v, d});
    G[v].push_back({v, u, d});
  }

  auto d = Dijkstra(G, S);
  auto dp1 = path(G, d, S, priority_queue<P, vector<P>, greater<P>>(), [](auto u, auto w, auto v) {return u+w==v;});
  auto dp2 = path(G, d, T, priority_queue<P>(), [](auto v, auto w, auto u) {return v==w+u;});

  auto ans = dp1[T] * dp1[T] % M;
  for(auto v=0; v<N; ++v) if(2*d[v] == d[T]) (ans -= (dp1[v]*dp1[v]%M)*(dp2[v]*dp2[v]%M)) %= M;
  for(auto E: G) for(auto e: E) if(d[e.from]+e.weight == d[e.to]) {
    if(2*d[e.from]<d[T] && d[T]<2*d[e.to]) (ans -= (dp1[e.from]*dp1[e.from]%M)*(dp2[e.to]*dp2[e.to]%M)) %= M;
  }
  cout << (ans + M) % M << endl;
}


Measured memory_bytes: 19528