akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;


int main(int argc, char* argv[])
{
    int n,m;
    scanf("%d%d", &n, &m);
    
    int a[10][10]={0};
    int i;
    for(i=0; i<m; i++) {
        int num;
        scanf("%d", &num);
        int j;
        for(j=0; j<num; j++) {
            int tmp;
            scanf("%d", &tmp);
            a[i][tmp-1]=1;
        }
    }
    int p[10]={0};
    for(i=0; i<m; i++) {
        scanf("%d", &p[i]); 
    }

    int ans=0;
    int j,k;
    for(i=0; i<(1<<n); i++) {
        for(j=0; j<m; j++) {
            int val=0;
            for(k=0; k<n; k++) {
                if(a[j][k] && (i & (1<<k))) {
                    val ++;
                }
            }
            if(val%2 != p[j]) {
                break;
            }
        }
        if(j==m) {
            ans++;
        }
    }
    printf("%d\n", ans);

    return 0;
}


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

int main() {
  string S, T;
  cin >> S >> T;
  
  int count = 0;
  int N = S.size();
  for (int i = 0; i < N; i++) {
    if (S[i] != T[i]) count++;
  }
  
  cout << count << endl;
}

Measured memory_bytes: 3896
H,W,K = map(int, input().split())
# HとWは道の数を決定
dp = [[0]*W for _ in range(H+1)]
dp[0][0] = 1
if W==1:
  print(1)
else:
  for i in range(H):
    for j in range(2**(W-1)):
      flag = True
      for k in range(W-1):
        if k != W-2:
          # 二桁連続で1の場合は処理を省く
          if (((j >> k) & 1)&((j >> k+1) & 1)):
            flag = False
            break
      if flag:
        #print(bin(j)[2:].zfill(W-1))
        l = 0
        while l < W:
          if ((j >> l) & 1):
            dp[i+1][l] += dp[i][l+1]
            dp[i+1][l+1] += dp[i][l]
            l += 1
          else:
            dp[i+1][l] += dp[i][l]
          l += 1
        #print('pre',dp[i])
        #print(dp[i+1])

  print(dp[-1][K-1]%(1000000007))

        
        
          

Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
struct Dice
{
    int s[6];
    void roll(char c)
    {


    int b;
    if(c=='E')
    {
        b=s[0];
        s[0]=s[3];
        s[3]=s[5];
        s[5]=s[2];
        s[2]=b;
    }
    if(c=='W')
    {
        b=s[0];
        s[0]=s[2];
        s[2]=s[5];
        s[5]=s[3];
        s[3]=b;
    }
    if(c=='N')
    {
        b=s[0];
        s[0]=s[1];
        s[1]=s[5];
        s[5]=s[4];
        s[4]=b;
    }
    if(c=='S')
    {
        b=s[0];
        s[0]=s[4];
        s[4]=s[5];
        s[5]=s[1];
        s[1]=b;
    }
    if(c=='R')//这是什么鬼东西，怎么还有往右的
    {
        b=s[1];
        s[1]=s[2];
        s[2]=s[4];
        s[4]=s[3];
        s[3]=b;
    }
    }
    int top()
    {
        return s[0];
    }
    int right()
    {
        return s[2];
    }
    int left()
    {
        return s[3];
    }
    int front ()
    {
        return s[1];
    }
};
bool same(Dice a,Dice b)
{
    for(int i=0;i<6;i++)
        if (a.s[i]!=b.s[i])
        return false;
    return true;

}
int main()
{


    Dice d[100];
    int n;cin>>n;
    for (int j=0;j<n;j++)
        for(int i=0;i<6;i++)
        cin>>d[j].s[i];
    bool ff=true;
    for(int k=0;k<n-1;k++)
    {
        for(int l=k+1;l<n;l++)
        {
            bool f=false;
            for(int i=0;i<4;i++)
            {
                d[l].roll('R');
                for(int j=0;j<4;j++)
                {
                    d[l].roll('N');
                     if(same(d[k],d[l])) f=true;
                }

            }
            d[l].roll('E');
            for(int j=0;j<4;j++)
            {
                d[l].roll('N');
                if(same(d[k],d[l])) f=true;

            }
            d[l].roll('W');
            d[l].roll('W');
            for(int j=0;j<4;j++)
            {
                d[l].roll('N');
                if(same(d[k],d[l])) f=true;
            }
            if(f) ff=false;
        }
    }
cout<<(ff?"Yes":"No")<<endl;
return 0;

}


Measured memory_bytes: 3096
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N, K;
char S[5050];
char le;

char at(int x)
{
	if (x >= N) return S[2 * N - 1 - x];
	return S[x];
}
string solve(int L, int R)
{
	//printf("%d--%d\n", L, R);
	string ret;
	if (K == 1) {
		for (int i = 0; i < N; ++i) ret.push_back(at(i + L));
		return ret;
	}
	if (R == N) {
		for (int i = 0; i < (R - L) << K; ++i) {
			if (ret.size() >= N) break;
			ret.push_back(le);
		}
		for (int i = L - 1; i >= 0; --i) {
			if (ret.size() >= N) break;
			ret.push_back(S[i]);
		}
		return ret;
	} else {
		for (int i = 0; i < (R - L) << (K - 1); ++i) {
			if (ret.size() >= N) break;
			ret.push_back(le);
		}
		for (int i = R; ; ++i) {
			if (ret.size() >= N) break;
			ret.push_back(at(i));
		}
		return ret;
	}
}

int main()
{
	scanf("%d%d%s", &N, &K, S);
	K = min(K, 14);
	le = 'z';
	for (int i = 0; i < N; ++i) le = min(le, S[i]);

	string ret;
	for (int i = 0; i < N; ++i) ret.push_back('z');

	int con = 0;
	for (int i = 0; i < N; ++i) {
		if (S[i] == le) {
			++con;
			if (i == N - 1 || S[i + 1] != le) {
				ret = min(ret, solve(i + 1 - con, i + 1));
				con = 0;
			}
		}
	}

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

	return 0;
}


Measured memory_bytes: 888
#include <stdio.h>

int main () {
	int N;
	scanf("%d", &N);
	long long int ar[N], maximum =1e18, pRod = 1, flag = 0;
	long long int zero = 0;
	
	for (int i = 0 ; i < N; i++) {
		scanf("%lld", &ar[i]);
		flag = (ar[i] > maximum) ? 1 : flag;
		pRod *= ar[i];
		(ar[i]) ? maximum /= ar[i] : zero = 1;
	}
	(zero) ? puts("0") : (flag) ? puts("-1") : printf ("%lld\n", pRod);
	return 0;
}

Measured memory_bytes: 2508
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;


    void solve()
    {
        int N = cin.nextint;
        var L = new long[N + 1];
        L[0] = 2;
        L[1] = 1;
        for (int i = 2; i <= N; i++)
        {
            L[i] = L[i - 2] + L[i - 1];
        }
        WriteLine(L[N]);
    }

}

class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 11220
#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

static const int INF = 1 << 30;
static const double PI = acos(-1);

int dp[202020];

int main() {
        int sx, sy, gx, gy;
        scanf("%d%d%d%d", &sx, &sy, &gx, &gy);
        int n;
        scanf("%d", &n);
        vector<pair<int, int>> p(n), q;
        for (int i = 0; i < n; i ++) scanf("%d%d", &p[i].first, &p[i].second);
        for (int i = 0; i < n; i ++) {
                if (min(sx, gx) <= p[i].first && p[i].first <= max(sx, gx) && min(sy, gy) <= p[i].second && p[i].second <= max(sy, gy)) {
                        q.push_back(p[i]);
                }
        }
        if (sy > gy) for (int i = 0; i < q.size(); i ++) q[i].second *= -1;
        sort(all(q));
        if (sx > gx) reverse(all(q));
        for (int i = 0; i < 202020; i ++) dp[i] = INF;
        for (int i = 0; i < q.size(); i ++) {
                *lower_bound(dp, dp + 202020, q[i].second) = q[i].second; 
        }
        int len = lower_bound(dp, dp + 202020, INF) - dp;
        double ans = (long long) (abs(gy - sy) + abs(gx - sx)) * 100;
        if (len < min(abs(gy - sy), abs(gx - sx)) + 1) {
                ans -= (20.0 - 5.0 * PI) * len;
        } else {
                ans -= (20.0 - 5.0 * PI) * (len - 1);
                ans += 10.0 * PI - 20;
        }
        printf("%.15lf\n", ans);
        return 0;
}



Measured memory_bytes: 4336
#include <stdio.h>
int N;
int W;
int dp[1001][1001];
int v[1001];
int w[1001];
int max(int a,int b){
  if(a<b)return b;
  else return a;
}
int main(){
  int i,j;
  int x;
  int count=0;
  while(1){
    scanf("%d",&W);
    if(W==0)break;
    count++;
    scanf("%d",&N);
    for(i=0;i<N;i++){
      scanf("%d,%d",&v[i],&w[i]);
    }
  
    for(i=0;i<N;i++){
      for(j=0;j<=W;j++){
	dp[i][j]=0;
      }
    }
    for(i=0;i<N;i++){
      for(j=0;j<=W;j++){
	if(w[i]<=j)
	  dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j]);
	else dp[i+1][j]=dp[i][j];
      }
    }
    x=W;
    for(i=W-1;i>0;i--){
      if(dp[N][W]==dp[N][i])x=i;
    }
   
    printf("Case %d:\n",count);
    printf("%d\n",dp[N][W]);
    printf("%d\n",x);
  }
  return 0;
}

Measured memory_bytes: 4520
N = int(input())
t = N // 2
a_list = []
b_list = []
for i in range(N):
    ab = list(map(int, input().split()))
    a_list.append(ab[0])
    b_list.append(ab[1])

a_list = sorted(a_list)
b_list = sorted(b_list)

if N%2 == 1:
    a_median = a_list[t]
    b_median = b_list[t]
    print(b_median-a_median+1)
elif N%2 == 0:
    a_median = (a_list[t-1]+a_list[t])/2
    b_median = (b_list[t-1]+b_list[t])/2
    print(int(2*(b_median-a_median)+1))

Measured memory_bytes: 27148
n = int(input())
m = -1
for i in range(1, n+1):
    if i * (i - 1) < 2 * n <= i * (i + 1):
        m = i
        break
top = m * (m + 1) // 2
for i in range(0, m):
    if top - i == n:
        ng = i
        break
for i in range(1, m+1):
    if i == ng:
        continue
    print(i)

Measured memory_bytes: 9176
from itertools import product
from math import ceil


def solve(string):
    d, g, *pc = map(int, string.split())
    g //= 100
    p = [_p for _p in pc[::2]]
    c = [_c // 100 for _c in pc[1::2]]
    ans = 1000
    for f in product([True, False], repeat=d):
        sums = sum([(i + 1) * _p + _c for i, (_f, _p, _c) in enumerate(zip(f, p, c)) if _f])
        counts = sum([_p for _f, _p in zip(f, p) if _f])
        if g <= sums:
            ans = min(ans, counts)
            continue

        indices = [i + 1 for i, _f in enumerate(f) if not _f]
        tmp = ceil((g - sums) / indices[-1])
        if tmp < p[indices[-1] - 1]:
            ans = min(ans, counts + tmp)
    return str(ans)


if __name__ == '__main__':
    n, g = map(int, input().split())
    print(solve('{} {}\n'.format(n, g) + '\n'.join([input() for _ in range(n)])))


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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct p{ll x, y;};

bool isinside(p z, p s, p t){
	return    min(s.x, t.x) <= z.x
	       && z.x <= max(s.x, t.x)
	       && min(s.y, t.y) <= z.y
	       && z.y <= max(s.y, t.y);
}

ll area(p s, p t){
	return (max(s.x, t.x) - min(s.x, t.x)) * (max(s.y, t.y) - min(s.y, t.y));
}

int n;
int k;
p a[51];

ll ans = 1e18 * 9;

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

	cin >> n >> k;

	rep(i, n) cin >> a[i].x >> a[i].y;
	
	rep(i, n){
		rep(j, n){
			rep(l, n){
				rep(m, n){
					p s{(ll)1e10, (ll)1e10};
					p t{(ll)-1e10, (ll)-1e10};

					s.x = min(s.x, a[i].x);
					s.y = min(s.y, a[i].y);
					t.x = max(t.x, a[i].x);
					t.y = max(t.y, a[i].y);

					s.x = min(s.x, a[j].x);
					s.y = min(s.y, a[j].y);
					t.x = max(t.x, a[j].x);
					t.y = max(t.y, a[j].y);

					s.x = min(s.x, a[l].x);
					s.y = min(s.y, a[l].y);
					t.x = max(t.x, a[l].x);
					t.y = max(t.y, a[l].y);

					s.x = min(s.x, a[m].x);
					s.y = min(s.y, a[m].y);
					t.x = max(t.x, a[m].x);
					t.y = max(t.y, a[m].y);

					int cnt = 0;
					rep(j, n) if(isinside(a[j], s, t)) cnt++;
					if(cnt >= k) ans = min(ans, area(s, t));
				}
			}
		}
	}
	
	cout << ans << endl;
}

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

int main(){
    int a;
    int b;
    int c;
    int y = 0;
    cin >> a; 
    cin >> b;
    cin >> c;
    for (int x = a; x <= b; ++x){
        if (c % x == 0){
            ++y;
        }
    }
    cout << y << endl;
    
    return 0;
}


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

signed main() {
    int n;
    ll k;
    cin >> n >> k;
    ll ans = -LINF;
    int p[n];
    ll c[n];
    rep(i, n) {
        cin >> p[i];
        p[i]--;
    }
    rep(i, n) {
        cin >> c[i];
        ans = max(ans, c[i]);
    }
    if (k <= 10000) {
        rep(i, n) {
            ll sum = 0;
            int cur = p[i];
            for (int j = 0; j < k; j++) {
                sum += c[cur];
                ans = max(ans, sum);
                cur = p[cur];
            }
        }
        cout << ans << endl;
        return 0;
    }
    rep(i, n) {
        ll sum = 0;
        int cur = p[i];
        for (int j = 0; j < 10000; j++) {
            sum += c[cur];
            ans = max(ans, sum);
            cur = p[cur];
        }
    }
    rep(i, n) {
        ll sum = 0;
        int sz = 0;
        int cur = p[i];
        do {
            sum += c[cur];
            ans = max(ans, sum);
            cur = p[cur];
            sz++;
        } while (cur != p[i]);
        ll summ = sum * (k / sz - 1);
        ans = max(ans, sum);
        int kk = k - sz * (k / sz - 1);
        for (int j = 0; j < kk; j++) {
            summ += c[cur];
            ans = max(ans, summ);
            cur = p[cur];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	if(a[0]!=b[2]||a[1]!=b[1]||a[2]!=b[0])
	{
		cout<<"NO";
		return 0;
	}
	cout<<"YES";
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define REP(i, n, N) for(ll i=(n); i < N; i++)
#define CK(N, A, B) (A <= N && N < B)
#define p(s) cout << (s) << endl
#define p2(a, b) cout << (a) << ' ' << (b) << endl
using namespace std;
typedef long long ll;

const int NODE_SIZE=10101;
int H;
int W;
int start_y, start_x;
int island_num=2;

int field[NODE_SIZE][NODE_SIZE];

int d[NODE_SIZE][NODE_SIZE];

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

void bfs(){
    queue<pair<int,int>> q;
    bool visited[H][W];
    REP(i,0,H) REP(j,0,W) visited[i][j]=false;
    REP(i,0,H) REP(j,0,W) d[i][j]=-1;
    q.push({start_y, start_x});
    d[start_y][start_x]=0;
    while(!q.empty()){
        int cur_y = q.front().first;
        int cur_x = q.front().second;
        int curStep = d[cur_y][cur_x];
        q.pop();
        if(visited[cur_y][cur_x]) continue;
        visited[cur_y][cur_x] = true;
        field[start_y][start_x]=island_num;

        REP(k,0,8){
            int next_y = cur_y + dy[k];
            int next_x = cur_x + dx[k];

            if(!CK(next_y,0,H) || !CK(next_x,0,W))continue;
            if(field[next_y][next_x]==1){
                field[next_y][next_x]=island_num;
            }else{
                continue;
            }
            if(!visited[next_y][next_x]){
                q.push({next_y, next_x});
                d[next_y][next_x] = d[cur_y][cur_x] + 1;
            }
        }
    }
}

int main() {
    while (cin >> W >> H && W){
        island_num = 2;
        REP(i,0,H){
            REP(j,0,W){
                cin >> field[i][j];
            }
        }
        REP(i,0,H){
            REP(j,0,W){
                if(field[i][j]==1){
                    start_y=i,start_x=j;
                    bfs();
                    island_num++;
                }
            }
        }
        p(island_num-2);
    }

    return 0;
}


Measured memory_bytes: 3528
S = input()
T = input()

subs = {}
for s,t in zip(S,T):
    c = subs.get(s,t)
    if c == t:
        subs[s] = t
    else:
        print("No")
        break
else:
    if len(subs.values())-len(set(subs.values())) == 0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
#define rep(i,n) for(int i=0;i<n;++i)
typedef long long int ll;
typedef unsigned long long ull;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
typedef pair<ll,ll> P;


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


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define int long long
using namespace std;
using Graph = vector<vector<int>>;
const int MOD = 1000000007;

signed main() {
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  
  vector<int> water;
  vector<int> sugar;
  
  //水の組み合わせ
  for( int i = 0; i*A*100 <= 3000; i++ ){
    for( int j = 0; i*A*100+j*B*100 <= 3000; j++ ){
      water.push_back(i*A*100+j*B*100);
    }
  }
  
  //砂糖の組み合わせ
  for( int i = 0; i*C <= 3000; i++ ){
    for( int j = 0; i*C+j*D <= 3000; j++ ){
      sugar.push_back(i*C+j*D);
    }
  }
  sort(sugar.begin(), sugar.end());
  sugar.erase(unique(sugar.begin(), sugar.end()), sugar.end());
  
  double kitei = (100.0*E)/(double)(100+E);
  int answ = 0;
  int anss = 0;
  double noudo = 0;
  for( int i = 0; i < water.size(); i++ ){
    for( int j = 0; j < sugar.size(); j++ ){
      double now = (100.0*sugar.at(j))/(double)(water.at(i)+sugar.at(j));
      if( water.at(i)+sugar.at(j) <= F && now <= kitei && noudo < now ){
        answ = water.at(i);
        anss = sugar.at(j);
        noudo = now;
      }
    }
  }
  
  if( answ == 0 ){
    answ = 100*A;
  }
  
  cout << answ+anss << " " << anss << endl;
  
  
}


Measured memory_bytes: 34792
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        s: chars,
    }
    if s[0] != 'A' {
        println!("WA");
        return;
    }
    if !s[1].is_lowercase() {
        println!("WA");
        return;
    }
    let mut called_c = false;
    for i in 2..s.len() - 1 {
        if s[i] == 'C' {
            if called_c == false {
                called_c = true;
            } else {
                println!("WA");
                return;
            }
        } else if !s[i].is_lowercase() {
            println!("WA");
            return;
        }
    }
    if called_c == false {
        println!("WA");
        return;
    }
    if !s[s.len() - 1].is_lowercase() {
        println!("WA");
        return;
    }
    println!("AC");
}

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

using namespace std;
typedef long long ll;

long double dp[3000][3000];
ll n;
vector<long double> v(3000);

long double f(ll i, ll cpt){
    if (i==n && cpt>n/2){
        return dp[i][cpt]=1;
    }
    if (i==n) return dp[i][cpt]=0;
    if (dp[i][cpt]!=-1) return dp[i][cpt];
    return dp[i][cpt]= f(i+1,cpt+1)*v[i]+f(i+1,cpt)*(1-v[i]);
}

int main()
{
    ll i,j;
    for(i=0;i<3000;i++){
        for(j=0;j<3000;j++)
            dp[i][j]=-1.0;
    }
    cin >> n;
    for(i=0;i<n;i++) cin >> v[i];
    cout << setprecision(15) << f(0,0);
    return 0;
}


Measured memory_bytes: 141056
num = int(input())
result_a = 0
result_b = 0
for i in range(num):
    a, b = map(str, input().split())
    if a  == b:
        result_a += 1
        result_b += 1
    elif a < b:
        result_b += 3
    else:
        result_a += 3
        
print(result_a, result_b)


Measured memory_bytes: 5592
//
//  main.cpp
//  knapsack
//
//  Created by r on 7/12/17.
//  Copyright © 2017 r. All rights reserved.
//

#include <iostream>
using namespace std;

long long dp[110][100010];
long long v[1001];
long long w[1001];

long long N,C;

//long long f (long long i, long long cap) {
//    if (cap==0 || i==N) {
//        return 0;
//    }
//    if (dp[i][cap] != -1) {
//        return dp[i][cap];
//    }
//    if (cap-w[i]<C) {
//        dp[i][cap] = f(i+1, cap);
//    } else {
//        dp[i][cap] = max(f(i+1,cap), f(i+1,cap-w[i])+v[i]);
//    }
//    return dp[i][cap];
//
//}


int main() {
    cin >> N >> C;
    for (long long i = 1; i<=N; i++) {
        cin >> w[i] >> v[i];
    }
    for (long long i = 1; i<=N; i++) {
        for (long long j = 0; j<=C; j++) {
            if (w[i]>j) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    cout << dp[N][C] << endl;
    return 0;
}


Measured memory_bytes: 79360
#include <bits/stdc++.h>
#define dbg(x) cout << #x << ": " << (x) << '\n'
#define ff first
#define ss second
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
const ll inf = 2e5 + 10;

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

   ll n;
   cin >> n;
   string s;
   cin >> s;
   reverse(s.begin(), s.end());

   vector <ll> lo(inf + 10, 1), hi(inf + 10, 1);

   ll x = count(s.begin(), s.end(), '1');

   if (x == 2)
      lo[0] = 0;

   for (ll i = 1; i <= inf; i++) {
      if (x != 1)
         lo[i] = (lo[i - 1] * 2) % (x - 1);
      hi[i] = (hi[i - 1] * 2) % (x + 1);
   }


   ll up = 0, down = 0;
   for (ll i = 0; i < n; i++) {
      if (s[i] == '1')
         up = (hi[i] + up) % (x + 1);
   }

   if (x != 1)
      for (ll i = 0; i < n; i++) {
         if (s[i] == '1')
            down = (lo[i] + down) % (x - 1);
      }

   for (ll i = n - 1; i >= 0; i--) {
      ll ans = 1, y = 0;
      if (s[i] == '0') {
         y = (up + hi[i]) % (x + 1);
         while (y != 0) {
            y %= __builtin_popcount(y);
            ans++;
         }
      } else if (s[i] == '1') {
         if (x == 1) {
            cout << 0 << '\n';
            continue;
         }
         y = (down - lo[i] + (x - 1)) % (x - 1);
         while (y != 0) {
            y %= __builtin_popcount(y);
            ans++;
         }
      }
      cout << ans << '\n';
   }

   return 0;
}

Measured memory_bytes: 6772
#include<iostream>
#include<map>
using namespace std;
int main()
{
	int n , ma=-1;	cin>>n;
	map<string , int> mp;
	for(int i=1;i<=n;i++)
	{
		string s;	cin>>s;
		mp[s]++;
		ma=max(ma , mp[s]);
	}
	map<string , int>::iterator iter;
	for(iter = mp.begin();iter != mp.end();iter++){
		if(iter->second==ma)
			cout<<iter->first<<endl;
	}
}

Measured memory_bytes: 25216
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    double a,b,h,m;
    cin >> a >> b >> h >> m;
    double pai = 3.141592653589793238;
    double ad = (360*h/12+30*m/60)*pai/180;
    double bd = 2*pai*m/60;
    double d = abs(ad-bd);
    cout << fixed << setprecision(15);
    cout << sqrt(a*a+b*b-2*a*b*cos(d)) << endl;
    return 0;
}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(ll n)
{
    ll ans = 0;
    while(n%2!=1)
    {
         ans++;
         n=n/2;
    }
    return ans;
}
int main()
{
  ll n;
   cin>>n;
  ll a[n];
   for(ll i =0;i<n;i++)
   {
       cin>>a[i];
   }
ll ans = INT_MAX;
       for(int i =0;i<n;i++)
   {
       ans = min(solve(a[i]),ans);

   }

   cout<<ans;
return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	static int swap=0;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int[] A =new int[N];
		for(int i=0;i<N;i++){
			A[i]=sc.nextInt();
		}
		SelectionSort(A);
		for(int i=0;i<N;i++){
			if(i==N-1){
				System.out.println(A[i]);
			}else{
				System.out.print(A[i]+" ");
			}
		}
		System.out.println(swap);
	}
	
	static void SelectionSort(int[] a){
		for(int i=0;i<a.length;i++){
			int mini=i;
			for(int j=i;j<a.length;j++){
				if(a[j]<a[mini]){
					mini=j;
				}
			}
			if(i!=mini){
				int t=a[i];
				a[i]=a[mini];
				a[mini]=t;
				swap++;	
			}
		}
	}
}

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

using namespace std;
using ll = long long int;
#define INF 20000000000000000;

int main(void){
  int n;
  cin >> n;
  
  vector<int> sw(n);
  vector<bool> check(n, false);
  
  for(int i = 0;i < n;i++){
    int x; cin >> x;
    sw[i] = x;
  }
  
  int cur = 0;
  int count = 0;
  for(int i = 0;i < n;i++){
    if(sw[cur] == 2){
      cout << count+1 << endl;
      return 0;
    }
    
    if(check[cur] == true){
      cout << -1 << endl;
      return 0;
    }
    check[cur] = true;
    cur = sw[cur]-1;
    count++;
  }
  
  cout << -1 << endl;
}

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

int main() {
  int n;
  cin >>n;
    vector<int64_t> veca(n+1);
//  veca.at(0) = 2;
//  veca.at(1) = 1;
  for(int i=0; i<=n ; i++){
    if(i==0){  
    veca.at(i) = 2;
    }else if(i==1){
      veca.at(i) = 1;
  }else{
    veca.at(i) = veca.at(i-1)+veca.at(i-2);
  }
  }
  cout << veca.at(n) << endl;

}



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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr int MOD = 998244353;

int modpow(int b, int e) {
    if (e == 0) return 1;
    if (e % 2 == 1) return 1LL * b * modpow(b, e - 1) % MOD;
    return modpow(1LL * b * b % MOD, e / 2);
}

inline int inv(int x) {
    return modpow(x, MOD - 2);
}

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

    int n;
    cin >> n;

    int ans = modpow(3, n);
    int cur = 0;
    int term = 1;
    int p = 2;
    // n choose k * 2^k for k in range()
    for (int k = n; k > n / 2; --k) {
        cur += 1LL * term * p % MOD;
        if (cur >= MOD)
            cur -= MOD;
        // going from n!/k!(n-k)! to n!/(k-1)!(n-k+1)!
        // multiply by k/(n-k+1)
        term = 1LL * term * inv(n - k + 1) % MOD;
        term = 1LL * term * k % MOD;
        p += p;
        if (p >= MOD)
            p -= MOD;
    }

    int res = ans - cur;
    if (res < 0) res += MOD;
    cout << res << '\n';
 
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int,int> Pii;

int main(){
    int x[4]={0,1,0,-1};
    int y[4]={1,0,-1,0};
    while(1){
        int w,h;
        cin>>w>>h;
        if(h==0&&w==0) break;
        vector<string> tile(h);
        vector<vector<bool> > checked(h,vector<bool>(w,false));
        int cnt=0,sx,sy;
        rep(i,h) cin>>tile[i];
        rep(i,h) rep(j,w) if(tile[i][j]=='@'){sx=i;sy=j;}
        stack<Pii> stk;
        stk.push(Pii(sx,sy));
        while(!stk.empty()){
            int nx=stk.top().first,ny=stk.top().second;
            stk.pop();
            if(checked[nx][ny] || tile[nx][ny]=='#') continue; 
            checked[nx][ny]=true;
            cnt++;
            rep(k,4){
                int dx=nx+x[k],dy=ny+y[k];
                if(dx>=0 && dx<h && dy>=0 && dy<w) stk.push(Pii(dx,dy));
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}


Measured memory_bytes: 3096
#include <cstdio>
using namespace std;
int w,a,b;
int main() {
	scanf("%d %d %d",&w,&a,&b);
	if (b>a+w)
		printf("%d\n",b-a-w);
	else if (a>b+w)
		printf("%d\n",a-b-w);
	else printf("0\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(void)
{
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<vector<int> > lrmap(N, vector<int>(N, 0));

	for (int i = 0; i < M; i++){
		int l, r;
		cin >> l >> r;
		lrmap[l-1][r-1]++;
	}

	vector<vector<int> > ruisekiwa(N, vector<int>(N+1, 0));
	for (int l = 0; l < N; l++){
		ruisekiwa[l][0] = 0;
		for (int r = 1; r <= N; r++){
			ruisekiwa[l][r] = ruisekiwa[l][r - 1] + lrmap[l][r-1];
		}
	}
	for (int k = 0; k < Q; k++){
		int cnt = 0;
		int q1, q2;
		cin >> q1 >> q2;
		for (int l = q1-1; l <= q2-1; l++){
			cnt += ruisekiwa[l][q2] - ruisekiwa[l][q1-1];
		}
		cout << cnt << endl;
	}
}

Measured memory_bytes: 2944
using System;

namespace _20200711_A
{
    class Program
    {
        static void Main(string[] args)
        {
            int L, R, n;
            string input;

            input = System.Console.ReadLine();
            L = int.Parse(input.Split(' ')[0]);
            R = int.Parse(input.Split(' ')[1]);
            n = int.Parse(input.Split(' ')[2]);


            Console.WriteLine(((R / n) - ((L-1)/ n)).ToString());
        }
    }
}


Measured memory_bytes: 27500
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD 1000000007
#define eps (1e-8)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");


signed main(){
    FASTER;
    int n,k;cin>>n>>k;
    vi v(n),dp(k+1,0);cin>>v;
    dp[0]=0;
    for(int i=1;i<=k;i++){
        for(int j:v){
            if(i-j>=0 && dp[i-j]==0){
                dp[i]=1;
                break;
            }
        }
    }
    if(dp[k])cout<<"First";
    else cout<<"Second";
}

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


void solve(std::string S, std::string T, long long A, long long B, std::string U){
    if(U == S){
        A--;
    }
    if(U == T)B--;
    cout<<A<<" "<<B<<endl;
}

int main(){
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    std::string U;
    std::cin >> U;
    solve(S, T, A, B, U);
    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 + B == C + D)
    cout << "Balanced" << endl;
  else if (A + B > C + D)
    cout << "Left" << endl;
  else
    cout << "Right" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <list>
#include <array>
#include <cstdlib>
#include <stack>
#include <string>
#include <queue>
#include <chrono>
#include <functional>
#include <limits>
#include <cmath>
#include <algorithm>
#include <random>
#include <regex>
#include <tuple>
#include <numeric>
#include <cassert>
#include <utility>
#include <bitset>
#include <complex>
#include <iomanip>
#include <ostream>
#include <sstream>
#include <ctime>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define index INDEX
#ifndef ONLINE_JUDGE
#define print(x) PRINT(x, #x)
template<typename T> void PRINT(T VARIABLE, const string& NAME) {
	cerr << NAME << " = " << fixed << VARIABLE << "\n";
}
#else
#define print(x) 0 
#endif
int generate_random() {
	const int MAX_RANDOM = (int)1e6;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	return uniform_int_distribution<int>(0, MAX_RANDOM)(rng);
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll INFLL = 2 * (ll)1e18 + 100;
#define int ll
#ifdef int 
const int INFINT = INFLL;
#else
const int INFINT = 2 * (int)1e9 + 100;
#endif
const double PI = atan(1) * 4;
const double EPS = 1e-6;
const int SEED = (int)1e3 + 7;
const int MOD = (int)1e9 + 7;
const int NMAX = (int)1e6 + 5;

int dp[2][NMAX];

int32_t main() {
#ifndef ONLINE_JUDGE
	double START_PROGRAM = clock();
#endif
	srand(time(NULL));
	cout << setprecision(20) << fixed;
	FASTIO;
    for0(i, 2) for0(j, NMAX) dp[i][j] = INFINT;
    dp[0][0] = 0;

    int n, w;
    cin >> n >> w;
    ll mmax = 0;
    for1(i, n)
    {
        int weight, value;
        cin >> weight >> value;
        int cur = i & 1;
        int prev = cur ^ 1;
        for(int curv = 0; curv < NMAX - (int)1e4; curv++)
        {
            dp[cur][curv + value] = min(dp[prev][curv + value], dp[prev][curv] + weight);
            dp[cur][curv] = min(dp[cur][curv], dp[prev][curv]);
            if(dp[cur][curv] <= w) mmax = max(mmax, curv);
        }
    }
    cout << mmax;
    







#ifndef ONLINE_JUDGE
	double END_PROGRAM = clock();
	double ELAPSED_TIME = (END_PROGRAM - START_PROGRAM) / CLOCKS_PER_SEC;
	cerr << "\n\nElapsed Time: " << ELAPSED_TIME * 1000 << "\n";
#endif
	return 0;
}







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

using namespace std;
typedef long long Int;

Int n, m;
Int tree[216000];
Int sum[216000];

Int solve(){
  for(int i = 0;i < m;i++){
    if(i == 0)sum[i] = tree[i];
    else sum[i] = sum[i-1] + tree[i];
  }
  Int res = 0;
  for(int i = m-1;i >= 0;i--){
    Int base = n - tree[i];
    if(i){
      base += 2 * sum[(i-1)/2] - 2 * (sum[i] - sum[(i-1)/2] - n * (i - (i-1) / 2));
      base += tree[i] - n;
      if(i % 2 == 0){
	base += tree[i / 2] - n;
      }
      else{
	base -= tree[i / 2];
      }
    }
    res = max(res, base);
  }
  return res;
}

int main(){
  cin >> n >> m;
  for(Int i = 0;i < m;i++){
    cin >> tree[i];
  }
  Int res = solve();
  for(Int i = 0;i < m;i++){
    Int a = m - 1 - i;
    if(a > i)swap(tree[a], tree[i]);
  }
  for(Int i = 0;i < m;i++)tree[i] = n - tree[i];
  res = max(res, solve());
  cout << res << endl;
  
}

Measured memory_bytes: 3328
N,D=map(int,input().split())
d=list(map(int,input().split()))

dp=[D]*N

if abs(D-d[0])<D:
    dp[0]=abs(D-d[0])

for i in range(1,N):
    dp[i]=min(dp[i-1],abs(dp[i-1]-d[i]))

ans=["NO"]*N
data=[0]*(N+1)
for i in range(N-1,0,-1):
    if d[i]//2>data[i+1]:
        data[i]=data[i+1]
    else:
        data[i]=data[i+1]+d[i]
    if dp[i-1]>data[i+1]:
        ans[i]="YES"

i=0
if d[i]//2>data[i+1]:
    data[i]=data[i+1]
else:
    data[i]=data[i+1]+d[i]

if D>data[i+1]:
    ans[i]="YES"

Q=int(input())
q=list(map(int,input().split()))
for i in range(Q):
    print(ans[q[i]-1])


#print(dp)
#print(data)
#print(ans)


Measured memory_bytes: 189452
// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES
#include<math.h>

//#include<cmath>

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>



//#include "Ants.h"
using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1000000000000000000ll)
typedef pair < int, int> P;
ll gcd(ll a, ll b) {//最大公約数を求める///最大公倍数a*b/gcd(a,b)
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcd(ll a, ll b) {//最小公倍数を求める　b=0のときaを返す
	if (b == 0) return a;
	return (a / gcd(a, b)) * b;
}
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
int digiter(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}
vector<int> convert(string s) {
	vector<int> d;
	ll n = s.size();
	rep(i, n) {
		d.push_back(s[i]-'0');
	}
	return d;
}
int K[33] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
int n;
int main()
{
	cin >> n;
	cout << K[n-1] << endl;
	
	
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
typedef struct{
  double x;
  double y;
}Point;

void koch(int , Point, Point);

int main(){
  Point p1={0,0},p2={100,0}; /*endpoint*/
  int num;

  scanf("%d",&num);

  printf("%.8f %.8f\n",p1.x,p1.y);
  koch(num,p1,p2);
  printf("%.8f %.8f\n",p2.x,p2.y);
  return 0;
}

void koch(int num, Point p1, Point p2){
  Point s,t,u;
  double theta=M_PI*60/180;  /*convert degree into radian*/
  if(num==0) return;
  s.x=(2*p1.x+p2.x)/3;
  s.y=(2*p1.y+p2.y)/3;

  t.x=(p1.x+2*p2.x)/3;
  t.y=(p1.y+2*p2.y)/3;

  u.x=(t.x-s.x)*cos(theta)-(t.y-s.y)*sin(theta)+s.x;
  u.y=(t.x-s.x)*sin(theta)+(t.y-s.y)*cos(theta)+s.y;

  koch(num-1,p1,s);
  printf("%.8f %.8f\n",s.x,s.y);

  koch(num-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);

  koch(num-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);

  koch(num-1,t,p2);
}



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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define ture ture
#define flase false
#define falg flag

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;//llの最大9*10^18
const int INF = pow(2, 30) - 1;

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

const int MAX = 1000000+100;
//const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void modcombinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long modcomb(long long n, long long k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    ll N;
    string S;
    cin >> N;

    modcombinit();

    if(N==1){
        cout << 0 << endl;
    }
    else if(N==2){
        cout << 2 << endl;
    }
    else{
        ll tmp = N - 2;

        ll tmp1 = (modpow(10, N, MOD) - modpow(8, N, MOD) + MOD) % MOD;
        ll tmp2 = 0;
        REP(i,N){
            tmp2 += (modpow(8, i, MOD) * modcomb(N, i)) % MOD;
            tmp2 %= MOD;
        }
        tmp2 *= 2;
        tmp2 %= MOD;
        tmp1 -= tmp2;
        tmp1 += MOD;
        tmp1 %= MOD;
        cout << tmp1 << endl;
    }
}


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

int n,cnt;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		cnt += (a&1);
	}
	puts((cnt&1)?"NO":"YES");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

map<ll,ll> prime_factor(ll n){
	map<ll,ll> res;
	for(ll i = 2LL; i * i  <= n; i++) {
		while(n % i == 0LL){
			res[i]++;
			n /= i;
		}
	}
	if (n != 1LL){
		res[n] = 1LL;
	}
    return res;
}

int main(){
	ll n,p;cin>>n>>p;
	map<ll,ll> a = prime_factor(p);
	ll ans = 1LL;
	for(auto i = a.begin(); i != a.end(); i++) {
		if ((i->sc) >= n){
			ans *= pow(i->fs,i->sc / n);
		} 
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 30;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int main() {
  string s;
  cin >> s;
  if (s <= "2019/04/30") {
    cout << "Heisei" << endl;
  } else {
    cout << "TBD" << endl;
  }
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int main(){
	char s[15],t[15];
	int i,j,k,l;
	cin>>s>>t;
	int fl=0;
	l=strlen(s);
	for(i=0;i<l;i++){
		if(s[i]!=t[i]){
			fl=1;break;
		}
	}
	if(!fl)cout<<"Yes";
	else cout<<"No";
} 

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

using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    long long res = 0;
    for (int i = 0; i < n; i++) {
        if ((k | a[i]) <= k) {
            res += b[i];
        }
    }

    for (int i = 0; i <= 31; i++) {
        if ((k & (1LL << i)) > 0) {
            long long r = 0, s = ((k | ((1LL << i) - 1)) ^ (1LL << i));
            for (int j = 0; j < n; j++) {
                if ((s | a[j]) <= s) {
                    r += b[j];
                }
            }
            res = max(res, r);
        }
    }

    cout << res << endl;
}


Measured memory_bytes: 4780
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

static const int N = 100;
static const int NEW = 0;
static const int VISITING = 1;
static const int OLD = 2;

int n, m[N][N] = {0}, t;
int color[N] = { 0 }, t1[N] = { 0 }, t2[N] = {0};

void getMatrix()
{
	int u, v, k;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> u >> k;
		for (int j = 0; j < k; ++j)
		{
			cin >> v;
			m[u-1][v-1] = 1;
		}
	}
}

int nxt(int idx)
{
	for (int i = 0; i < n; ++i)
	{
		if (1 == m[idx][i] && color[i] == NEW)
			return i;
	}
	return -1;
}

void dfs_visit(int idx)
{
	stack<int> s;
	s.push(idx);
	color[idx] = VISITING;
	t1[idx] = t++;


	while (!s.empty())
	{
		int u = s.top();
		int v = nxt(u);
		if (-1 != v)
		{
			if (color[v] == NEW)
			{
				color[v] = VISITING;
				t1[v] = t++;
				s.push(v);
			}
		}
		else
		{
			s.pop();
			color[u] = OLD;
			t2[u] = t++;
		}
	}
}

void dfs()
{
	t = 1;

	for (int i = 0; i < n; ++i)
		color[i] = NEW;

	for (int i = 0; i < n; ++i)
	{
		if (color[i] == NEW)
			dfs_visit(i);
	}

	for (int i = 0; i < n; ++i)
	{
		cout << i + 1 << " " << t1[i] << " " << t2[i] << endl;
	}
}

int main()
{
	getMatrix();
	dfs();
}

Measured memory_bytes: 3140
#include<cstdio>
int n,a[200010];
int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(register int i=n;i>0;i-=2)printf("%d ",a[i]);
	for(register int i=(n&1?2:1);i<=n;i+=2)printf("%d ",a[i]);
	return 0;
}

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

int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

int f(string str){
    int op[2] = {1,-1};
    string sop[2] = {"+","-"};

        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    if(7 == ctoi(str.at(0)) + op[i] * ctoi(str.at(1)) + op[j] * ctoi(str.at(2)) + op[k] * ctoi(str.at(3))){
                        cout << str.at(0) << sop[i] << str.at(1) << sop[j] << str.at(2) << sop[k] << str.at(3) << "=7";
                        return 0;
                    }
                }
            }
        }
};

int main(){
    //input
    string str;
    cin >> str;
    f(str);
    return 0;
}

Measured memory_bytes: 256