akhauriyash/Code-Regression huggingface dataset:
from itertools import combinations, permutations
from bisect import bisect_right, bisect_left

def solve(N, S):
    left = [-1]*10
    right = [-1]*10
    place = [[] for i in range(10)]
    for i in range(N):
        c = int(S[i])
        if left[c] == -1:
            left[c] = i
        right[c] = i
        place[c].append(i)

    def ok(s, dbg=False):
        l, m, r = [int(c) for c in s]
        if left[l] == -1 or right[r] == -1:
            return False
        if not left[l] < right[r]:
            return False
        j = bisect_right(place[m], left[l])
        if j == len(place[m]):
            return False
        mid = place[m][j]
        if mid < right[r]:
            #print(left[l], place[m], right[r])
            #print(left[l], mid, right[r])
            return True
        return False

    count = 0
    for i in range(0, 1000):
        s = "%03d" % i
        if ok(s):
            count += 1
    #print(ok("224", True))

    return count

def check(N, S):
    c = set()
    for s in combinations(range(N), 3):
        s = tuple(S[i] for i in s)
        #s = S[:i] + S[i+1:j] + S[j+1:k] + S[k+1:]
        if s not in c:
            pass
        c.add(s)
        
    return len(c)

def main():
    N = int(input())
    S = input()
    #print(check(N, S))
    print(solve(N, S))

def test(S):
    print(S,check(len(S), S), "==", solve(len(S), S))

#test("0224")
#test("123123")
#test("3141592653589793238")
main()


Measured memory_bytes: 4456
#include <time.h>

#include <stdlib.h>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <cstdint>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <bitset>
#include <iterator>
#include <deque>
#include <string>
#include <queue>
#include <omp.h>
#include <fstream>   // ifstream, ofstream
typedef int64_t ll;
using namespace std;
const ll INF=1e10;
struct Light{
	vector<ll> switches;
};
vector<Light> light_list;
vector<ll> p_list;

bool calc_isok(ll sw_list){
	for(ll i1=0;i1<light_list.size();i1++){
		int64_t cnt = 0;
		for(auto i2=light_list[i1].switches.begin();i2!=light_list[i1].switches.end();i2++){
			if(sw_list&(1<<(*i2))){//switch on
				cnt++;
			}
		}
		if(cnt%2!=p_list[i1]){
			return false;
		}
	}
	return true;
}

int main(){
	ll n,m;
	cin>>n>>m;
	for(ll i1=0;i1<m;i1++){
		ll k;
		cin>>k;
		vector<ll> temp;
		for(ll i2=0;i2<k;i2++){
			ll t2;
			cin>>t2;
			temp.push_back(t2-1);
		}
		light_list.push_back(Light{temp});
	}
	for(ll i1=0;i1<m;i1++){
		ll t2;
		cin>>t2;
		p_list.push_back(t2);
	}
	ll ans=0;
	for(ll i1=0;i1<(1<<n);i1++){
		if(calc_isok(i1)){
			ans++;
		}
	}
	cout<<ans<<endl;

}


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

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	b = a;
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] != b[i]) ans++;
	}
	if (ans <= 2) {
		cout << "YES\n";
	} else {
		cout << "NO\n";
	}
}


Measured memory_bytes: 3436
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define for(i,n,val) for(ll i=val;i<n;i++)
using namespace std;
bitset<65>b;
vector<ll>v[15];
int main()
{
    ll n,s,q,typ,m;
    cin>>n;
    for(i,n,0)
    {
        cin>>s;
        v[i].pb(s);
        for(j,s,0)
        {
            cin>>m;
            v[i].pb(m);
        }
    }
    cin>>q;
    while(q--)
    {
        cin>>typ;
        if(typ==0)
        {
            cin>>s;
            cout<<b[s]<<endl;
        }
        else if(typ==1)
        {
            cin>>m;
            for(i,v[m][0]+1,1)
            {
                b[v[m][i]]=1;
            }

        }
        else if(typ==2)
        {
            cin>>m;
            for(i,v[m][0]+1,1)
            {
                b[v[m][i]]=0;
            }

        }
        else if(typ==3)
        {
            cin>>m;
            for(i,v[m][0]+1,1)
            {
                b.flip(v[m][i]);
            }

        }
        else if(typ==4)
        {
            cin>>m;
            bool flag=0;
            for(i,v[m][0]+1,1)
            {
                if(b[v[m][i]]!=1)
                {
                    flag=1;
                }
            }
            if(flag==0)
            {
                cout<<"1"<<endl;
            }
            else
            {
                cout<<"0"<<endl;
            }

        }
        else if(typ==5)
        {
            cin>>m;
            bool flag=0;
            for(i,v[m][0]+1,1)
            {
                if(b[v[m][i]]==1)
                {
                    flag=1;
                }
            }
            if(flag==0)
            {
                cout<<"0"<<endl;
            }
            else
            {
                cout<<"1"<<endl;
            }

        }
        else if(typ==6)
        {
            cin>>m;
            bool flag=0;
            for(i,v[m][0]+1,1)
            {
                if(b[v[m][i]]==1)
                {
                    flag=1;
                }
            }
            if(flag==0)
            {
                cout<<"1"<<endl;
            }
            else
            {
                cout<<"0"<<endl;
            }

        }
        else if(typ==7)
        {
            cin>>m;
            ll cnt=0;
            for(i,v[m][0]+1,1)
            {
                if(b[v[m][i]]==1)
                {
                    cnt++;
                }
            }
            cout<<cnt<<endl;

        }
        else if(typ==8)
        {
            cin>>m;
            ull cnt=0;
            ull val;
            for(i,v[m][0]+1,1)
            {
                if(b[v[m][i]]==1)
                {
                    val=pow(2,v[m][i]);
                    cnt+=val;
                }
            }
            cout<<cnt<<endl;

        }

    }

}



Measured memory_bytes: 3300
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> eratosthenes(1'000'000,0);
    eratosthenes[0] = eratosthenes[1] = 1;
    for(int i=2; i<1'000'000; i++){
        if(eratosthenes[i] == 0){
            for(int j=i+i; j<1'000'000; j+=i){
                eratosthenes[j] = 1;
            }
        }
    }
    int a,d,n;
    cin >> a >> d >> n;
    while(a != 0){
        int cnt = 0;
        while(1){
            if(eratosthenes[a] == 0) cnt++;
            if(cnt == n){
                cout << a << endl;
                break;
            }
            a += d;
        }
        cin >> a >> d >> n;
    }
    return 0;
}


Measured memory_bytes: 6616
s=input()
if s.count('01')>s.count('10') or (s.count('01')==s.count('10') and s[0]=='0'):
    cvf='0'
    cvb='1'
else:
    cvf='1'
    cvb='0'
c=0
for i in range(0,len(s),2):
    if s[i] != cvf:
        c+=1
    try:
        if s[i+1] != cvb:
            c+=1
    except IndexError:
        break
print(c)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e5;
const int inf=1e9;
long modpow(long x,int n,long p){
	int i = 0;long res = 1;
	while(n >= (1<<i)){
		if(n & (1<<i)) (res *= x) %= p;
		i++;
		x = (x * x) % p;
	}return res;
}
int main(){
	int N,K; cin>>N>>K;
	long f[K+1],g[K+1]; long ans = 0;
	rep(i,1,K+1) f[i] = modpow(K / i, N, mod);
	for(int i = K; i > 0; i--){
		g[i] = f[i];
		for(int j = 2 * i; j <= K; j += i) (g[i] += mod - g[j]) %= mod;
		(ans += g[i] * i % mod) %= mod;
	}cout<<ans<<endl;
}

Measured memory_bytes: 5148
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
    ll H=0,W=0;
    cin >> H >> W;
    if(H == 1 || W == 1){
        cout << 1 << endl;
    }else{
        cout << H*W/2+H*W%2 << endl;
    }
    return 0;    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
long long x, ans, ini[maxn];
int n;

int main()
{
	scanf("%d%lld", &n, &x);
	for(int i = 1; i <= n; ++i) scanf("%lld", &ini[i]);
	for(int i = 1; i < n; ++i){
		if(ini[i] + ini[i + 1] <= x) continue;
		long long delta = ini[i + 1] + ini[i] - x;
		if(ini[i + 1] >= delta){ini[i + 1] -= delta; ans += delta; continue;}
		ini[i] -= (delta - ini[i + 1]); ini[i + 1] = 0;  ans += delta;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1024
//============================================================================
// Name        : d.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
int main() {
	string s;cin>>s;
	ll n=s.size();
	vector<ll> a(n);
	ll def=1;
	for(int i=0;i<9;i++)def*=10;
	def+=7;
	vector<vector<ll>> dp(n,vector<ll>(13,0));
	if(s[n-1]=='?'){
		for(int i=0;i<10;i++)dp[n-1][i]=1;
	}else{
		dp[n-1][s[n-1]-'0']=1;
	}
	ll mul=1;
	for(int i=n-2;i>=0;i--){
		vector<ll> num;
		mul=(mul*10)%13;
		if(s[i]=='?'){
			for(int j=0;j<10;j++){
				num.push_back(j);
			}
		}else{
			num.push_back(s[i]-'0');
		}
		for(int j=0;j<num.size();j++){
			for(int k=0;k<13;k++){
				dp[i][(k+num[j]*mul)%13]+=dp[i+1][k];
				dp[i][(k+num[j]*mul)%13]%=def;
			}
		}
	}
//	for(int i=0;i<n;i++){
//		for(int j=0;j<13;j++){
//			cout<<dp[i][j]<<' ';
//		}cout<<endl;
//	}
	cout<<dp[0][5]<<endl;
	return 0;
}

Measured memory_bytes: 14464
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cstring>
using namespace std;
#define sci(n) scanf("%lld", &(n))
#define scd(n) scanf("%Ld", &(n))
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> pll;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	LL n;
	cin >> n;
	vector<LL> v; v.resize(n);

	for (int i = 0; i < n; i++)cin >> v[i];
	if (n == 1) {
		cout << "Yes";
		return 0;
	}
	for (int i = 1; i < n; i++) {
		if (v[i]>= v[i - 1]+1) {
			v[i]--;
		}

		if (v[i]<v[i-1]) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
		
	return 0;
}

Measured memory_bytes: 1024
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 07/11/20 19:53:47
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int t; cin>>t;
  while (t--) {
    int n; cin>>n;
    ll ans = 0;
    vector<pair<int,int>> lrs, rrs;
    for (int i = 0; i < n; i++) {
      int k,l,r; cin>>k>>l>>r;
      ans += min(l,r);
      if (l > r)
        lrs.emplace_back(k-1,l-r);
      else if (l < r)
        rrs.emplace_back(n-k-1,r-l);
    }

    auto choice = [](auto& rs) -> ll {
      priority_queue<int> ps;
      ll ret = 0;
      int i = rs.size()-1;
      for (int d = rs.size()-1; d >= 0; d--) {
        while (i >= 0 and rs[i].first >= d)
          ps.push(rs[i--].second);
        if (not ps.empty()) {
          ret += ps.top();
          ps.pop();
        }
      }
      return ret;
    };

    sort(lrs.begin(), lrs.end());
    ans += choice(lrs);
    sort(rrs.begin(), rrs.end());
    ans += choice(rrs);

    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 5680
#include <cstdio>
#include <queue>
#include <vector>
#define pb push_back
using namespace std;

const int mxsz = 1e5 + 3;
int n, m;
vector<int> adj[mxsz];
int in[mxsz], d[mxsz], p[mxsz];

int main(){
	scanf("%d %d", &n, &m);
	for (int i = 0, a, b; i < n + m - 1; i++){
		scanf("%d %d", &a, &b);
		adj[a].pb(b);
		in[b]++;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) if (!in[i]) q.push(i);
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (int nx : adj[u]){
			d[nx] = max(d[nx], d[u] + 1);
			in[nx]--;
			if (!in[nx]) q.push(nx);
		}
	}
	for (int i = 1; i <= n; i++){
		for (int nx : adj[i]){
			if (d[nx] == d[i] + 1)
				p[nx] = i;
		}
	}
	for (int i = 1; i <= n; i++) printf("%d\n", p[i]);
	return 0;
}


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

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> A(n, 0);
    for (int i = 0; i < n - 1; i++) {
        int cur; cin >> cur;
        A[cur - 1]++;
    }

    for (int i = 0; i < n; i++) 
        cout << A[i] << endl;

    return 0;
}


Measured memory_bytes: 3984
function main()
	N=parse(Int,readline())
	A=Int[]
	B=Int[]
	for _=1:N
		a,b=map(x->parse(Int,x),split(readline()))
		push!(A,a)
		push!(B,b)
	end
	sort!(A)
	sort!(B)
	if N%2==1
		println(B[div(N+1,2)]-A[div(N+1,2)]+1)
	else
		println(B[div(N,2)]+B[div(N,2)+1]-A[div(N,2)]-A[div(N,2)+1]+1)
	end
end
main()


Measured memory_bytes: 206556
s=input()
t=input()
n=len(t)
s_l=[]
for i in range(0,len(s)-n+1):
  s_l.append(s[i:i+n])
# print(s_l)

ans=100000
for si in s_l:
  tmp=sum([i!=j for i,j in zip(si,t)])
  ans=min(ans,tmp)
  
print(ans)

Measured memory_bytes: 9124
from collections import defaultdict

N, K = map(int, input().split())
sushi = [list(map(int, input().split())) for _ in range(N)]

sushi = sorted(sushi, key = lambda x: x[1], reverse = True)
types = set()
max_vals = [0]
other_vals = [0]

for typ, val in sushi:
    if typ not in types:
        max_vals.append(max_vals[-1] + val)
        types.add(typ)
    else:
        other_vals.append(other_vals[-1] + val)

max_score = 0
for k in range(1, K + 1):
    if K - k < len(other_vals) and k < len(max_vals):
        score = max_vals[k] + other_vals[K - k] + k ** 2
        max_score = max(max_score, score)

print(max_score)


Measured memory_bytes: 38484
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
// マクロ
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
// 型エイリアス
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvs = vector<vs>;

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a[i];
    sort(a.rbegin(),a.rend());
    int al=0, bo=0;
    for(int i =0; i < n; i++) {
        if((i + 1) % 2 == 1) al += a[i];
        else bo += a[i];
    }
    cout << al - bo << endl;
}

Measured memory_bytes: 3712
line = input().split()
a, b, c = int(line[0]), int(line[1]), int(line[2])

extra = []
x = 1

while True:
    e = a * x % b
    if e in extra:
        break
    else:
        extra.append(e)
    
    x += 1
    
success = False
for e in extra:
    if e == c:
        success = True
        print('YES')
        break
        
if not success:
    print('NO')

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);

int main() {
    // source
    string s;
    cin >> s;
    int l, r;

    rep(i, s.size()) {
        if (s[i] == 'A') {
            l = i;
            break;
        }
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == 'Z') {
            r = i;
            break;
        }
    }
    cout << r - l + 1 << endl;
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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


Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
int n,i,c;
int cmp(const void*a,const void*b)
{
	return *(int*)a-*(int*)b;
}
int main()
{
	for(;scanf("%d\n",&n),n;)
	{
		int p[11]={0},b=0;
		for(i=0;i<100;i++)
			switch(c=getchar())
			{
			case 83:b+=p[i%n]+1;p[i%n]=0;break;//s
			case 76:p[i%n]+=b+1;b=0;break;//l
			case 77:p[i%n]++;//m
			default:break;
			}
		qsort(p,n,4,cmp);
		for(i=0;i<n;i++)
			printf("%d ",p[i]);
		printf("%d\n",b);
	}
	return 0;
}

Measured memory_bytes: 612
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

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

int ceil(int x, int y)
{
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y)
{
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y)
{
  return x / gcd(x, y) * y;
}

void swap(int *a, int *b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

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

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

  bool ans = false;
  for (int i = 0; i < n; i++)
  {
    for (int j = i; j < n; j++)
    {
      swap(&p[i], &p[j]);
      bool sorted = true;
      for (int k = 0; k + 1 < n; k++)
      {
        if (p[k] > p[k + 1])
        {
          sorted = false;
          break;
        }
      }
      if (sorted)
      {
        ans = true;
        break;
      }
      swap(&p[i], &p[j]);
    }
  }

  if (ans)
  {
    cout << "YES" << endl;
  }
  else
  {
    cout << "NO" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n;
    cin>>n;
    int a[n];
    forn(i,n)   cin>>a[i];
    sort(a,a+n);
    double x=((double)a[0]+a[1])/2.0;
    int i=2;
    while(i<n){
        x = (x+(double)a[i])/2.0;
        i ++;
    }
    cout<<fixed<<setprecision(5)<<x<<endl;
    return 0;
}



Measured memory_bytes: 256
N,M = map(int,input().split())

ato = []
bto = []

for _ in range(M):
    a,b = map(int,input().split())
    if a == 1:
        ato.append(b)
    if b == N:
        bto.append(a)

ato = set(ato)
bto = set(bto)

dec = ato & bto

if len(dec) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Measured memory_bytes: 21052
int zeller(int Y,int M,int D){if(++M<4)Y-=1,M+=14;int y=Y/100,z=y%100;return (21*y/4+5*z/4+13*M/5+D)%7;}
char *W[]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
main(m,d){for(;scanf("%d%d",&m,&d),m;)puts(W[zeller(2004,m,d)]);exit(0);}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int cnt1[1000100], cnt2[1000100];

int main() {
	vector< int > nums;
	
	int a = 2, c = 1, num = 1;
	
	while (num < 1000100) {
		nums.push_back(num);
		c += a;
		++a;
		num += c;
	}
	
	for_(j,0,(int)nums.size()) {
		cnt1[nums[j]] = 1;
		if (nums[j] % 2) cnt2[nums[j]] = 1;
	}
	
	for_(i,1,1000100) {
		for_(j,0,(int)nums.size()) {
			if (i - nums[j] <= 0) break;
			
			if (cnt1[i] == 0) cnt1[i] = cnt1[i - nums[j]] + 1;
			else cnt1[i] = min(cnt1[i], cnt1[i - nums[j]] + 1);
			
			if (nums[j] % 2) {
				if (cnt2[i] == 0) cnt2[i] = cnt2[i - nums[j]] + 1;
				else cnt2[i] = min(cnt2[i], cnt2[i - nums[j]] + 1);
			}
		}
	}
	
	int n;
	while (cin >> n, n) {
		cout << cnt1[n] << " " << cnt2[n] << endl;
	}
}

Measured memory_bytes: 9032
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = l, _r = r; i <= _r; ++i)
#define Ford(i, l, r) for (register int i = r, _l = l; i >= _l; --i)
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int maxn = 2e5 + 20;
const int mod = 998244353;

ll n,k;
ll le[12], ri[12], dp[maxn], pre[maxn];

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
    return x * f;
}

int main()
{
    n = read(), k = read();
    For(i, 1, k)
        le[i] = read(),
        ri[i] = read();
    dp[1] = pre[1] = 1;
    For(i, 2, n)
    {
        For(j, 1, k)
            dp[i] = (dp[i] + pre[max(i - le[j], 0LL)] - pre[max(i - ri[j] - 1, 0LL)] + mod) % mod;
        pre[i] = (pre[i - 1] + dp[i]) % mod;
    }
    printf("%lld\n", dp[n]);
    return 0;
}

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

typedef long long int ll;
typedef vector<int> vec;
typedef vector<vec> mat;

typedef priority_queue<int, vec, greater<int> > QUE;

int main() {
    int N, M;
    string str;
    QUE que;

    cin >> str;
    cout << string(str.begin(), str.begin() + 4) << " " << string(str.begin() + 4, str.end()) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<int> p(n+1); REP(i,n) cin >> p[i+1];

    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) {
            if (i < n) {
                swap(p[i], p[i+1]);
                count++;
            } else {
                swap(p[i], p[i-1]);
                count++;
            } 
        } 
    }
  
    cout << count << endl;
    return 0;
}



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

const long long LL_INF = (long long) 2e18 + 5;

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

    int N;
    cin >> N;
    vector<long long> A(N);

    for (auto &a : A)
        cin >> a;

    long long best = LL_INF;

    for (int start = 0; start <= 1; start++) {
        bool positive = start;
        long long cost = 0, sum = 0;

        for (int i = 0; i < N; i++) {
            sum += A[i];

            if (positive) {
                if (sum <= 0) {
                    cost += 1 - sum;
                    sum = 1;
                }
            } else {
                if (sum >= 0) {
                    cost += sum - (-1);
                    sum = -1;
                }
            }

            positive = !positive;
        }

        best = min(best, cost);
    }

    cout << best << '\n';
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int N,M,X;
	vector<int>A(105,0);
	cin>>N>>M>>X;
	for(int i=0;i<N;i++)
	{
		int x;
		cin>>x;
		A[x]=1;
	}
	int c1=0,c2=0;
	for(int i=0;i<=X;i++)
		c1+=A[i];
	for(int i=X;i<=N;i++)
		c2+=A[i];
	printf("%d\n",min(c1,c2));
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <math.h>
using namespace std;
int main()
{
	int N;
	cin>>N;
	int A[N],i,j,k,freq=0,repeat=0;
	set <int> check;
	set <int> check1;
	for(i=0;i<N;i++)
	{
		cin>>j;
		A[i]=j;
		if(check.find(j)!=check.end())
		{
			check1.insert(j);
		}
		if(j==1)
		freq++;
		check.insert(j);
	}
	double w;
	int count=0;
	if(N==1)
	cout<<"1";
	else if(freq==1)
	{
		cout<<"1";
	}
	else if(freq>1)
	cout<<"0";
	else
	{
	for(i=0;i<N;i++)
	{
		w=A[i];
		j=(int)(sqrt(w));
		k=1;
		if((check1.find(A[i])==check1.end())&&(A[i]!=1))
		{
			if(A[i]==2)
			count++;
			else if(A[i]==3)
			count++;
			else
			{
			
			for(k=2;k<=j+1;k++)
			{
				if(A[i]%k==0)
				{
					if((check.find(k)!=check.end())||(check.find(A[i]/k)!=check.end()))
					{
					break;	
					}
				}
			}
			if(k==(j+2))
			count++;
			}
		}
	}
	cout<<count;	
	}
	return 0;
}

Measured memory_bytes: 13768
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
 

int main() {
   int a,b,c;
   cin >> a>>b>>c;
   if((a==5&&b==5&&c==7)||(a==7&b==5&&c==5)||(a==5&&b==7&& c==5)) cout << "YES" <<endl;
   else cout << "NO" <<endl;
}

Measured memory_bytes: 256
import itertools

n, m = (int(x) for x in input().split())
li = []
for i in range(m):
    li.append([int(x) for x in input().split()])
#print(li)

paths = list(itertools.permutations([int(x) for x in range(1,n+1)]))

#print(paths)

ans = 0
for path in paths:
    if path[0] != 1:
        continue
    flag = True
    for i in range(n-1):
        if path[i] < path[i+1]:
            a = path[i]
            b = path[i+1]
        else:
            b = path[i]
            a = path[i+1]
        if [a,b] not in li:
            flag = False
            break
    if flag:
        ans += 1
print(ans)


Measured memory_bytes: 8052
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
use proconio::input;
// use proconio::marker::Usize1;
//use proconio::marker::Chars;
//use std::collections::HashSet;
//use std::cmp::*;
fn main() {
    input! {
       mut n:u64
    }
    // 26^4+26^3+(26^2+26)
    // 2^50以下の数。
    // 1_000_000_000_000_001 < 26^11
    let mut ans: String = String::new();
    while n > 0 {
        n = n - 1;
        ans.push(((n % 26) as u8 + 'a' as u8) as char);
        n = n / 26;
    }
    println!("{}", ans.chars().rev().collect::<String>());
}


Measured memory_bytes: 2120
n = int(input())
d = []
for i in range(n):
    d.append(list(map(int,input().split())))
row = []
for i in range(n):
    if d[i][0]==d[i][1]:
        row.append(True)
    else:
        row.append(False)
res = False
for i in range(n-2):
    if all(row[i:i+3]):
        res = True
if res:
    print('Yes')
else:
    print('No')

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

int main() {
  int n;
  cout << fixed << setprecision(5);
  while (true) {
    cin >> n;
    if (n == 0) break;
    int sum = 0;
    vector<int> s(n);
    for (int i = 0; i < n; ++i) {
      cin >> s.at(i);
      sum += s.at(i);
    }
    double ave = (double) sum / n;
    double sum_diff = 0.0;
    for (int i = 0; i < n; ++i) {
      sum_diff += (double) (s.at(i) - ave) * (s.at(i) - ave);
    }
    double sigma = sqrt(sum_diff / n);
    cout << sigma << endl;
  }

  return 0;
}


Measured memory_bytes: 3268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int n;
char s[123];
int main(){
	scanf("%d%s", &n, s);
	int a=0, b=0;
	REP(i, n){
		if(s[i]=='R') a++;
		else b++;
	}
	if(a>b) printf("Yes\n");
	else printf("No\n");
}


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

using namespace std;

int main(){
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int x_max = -1;
    int y_min = 10000; 

    for(int i = 0; i < n; i++){
        int temp; 
        cin >> temp;
        x_max = max(x_max, temp);
    }
    for(int j = 0; j < m; j++){
        int temp;
        cin >> temp;
        y_min = min(y_min, temp);
    }

    bool flag = false;
    int z;
    if(x < y){
        for(int i = x+1; i <= y; i++){
            if(x_max < i && i <= y_min){
                flag = true;
                break;
            }
        }
    }
    
    if(flag) cout << "No War" << endl;
    else cout << "War" << endl; 
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long d = Long.parseLong(sc.next());
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            long x = Long.parseLong(sc.next());
            long y = Long.parseLong(sc.next());
            if (x * x + y * y <= d * d) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

Measured memory_bytes: 58856
n=int(input())
num=list(map(int, input().split()))

max=num[0]
min=num[0]
sum=num[0]

for c in range(1,n):
  if max < num[c]:
    max=num[c]
  if min > num[c]:
    min=num[c]
  sum+=num[c]

print("{} {} {}".format(min, max,sum))


Measured memory_bytes: 6600
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define show(x) cout<<x<<'\n'
#define showh(x) cout<<x<<' '
#define go(i,a,n) for(ll i=a;i<n;i++)
#define gor(i,a,n) for(ll i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define mod 1000000007
bool prime[100001];
bool ispoweroftwo(ll x)
{
    return x && !(x & (x-1));
}
ll xorcal(ll n)
{
    if(n%4==0)
        return n;
    if(n%4==1)
        return 1;
    if(n%4==2)
        return n+1;
    if(n%4==3)
        return 0;
}
void sieve(ll n)
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for(ll i=2;i*i<=n;i++)
    {
        if(prime[i]==true)
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                prime[j]=false;
            }
        }
    }
    show(prime[89]);
}
bool isprime(ll n)
{
    if (n<=1) return false;
    if (n<=3) return true;

    if(n%2==0 or n%3==0) return false;

    for(ll i=5;i*i<=n;i+=6)
    {
        if(n%i==0 or n%(i+2)==0) return false;
    }
    return true;
}

ll modinverse(ll a,ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
      return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m; a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
       x += m0;

    return x;
}

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

ll power(ll A, ll B)
{
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;

    ll y;
    if (B % 2 == 0) {
        y = power(A, B / 2);
        y = (y * y) % mod;
    }

    else {
        y = A % mod;
        y = (y * power(A, B - 1) % mod) % mod;
    }

    return (ll)((y + mod) % mod);
}
int main()
{
    ios_base::sync_with_stdio(false);
    ll a,b,n;
    cin>>a>>b>>n;
    show(min(a*b,n));
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define INF 1000000
#define NIL -1
#define MAX 101
#define WHITE 0
#define BLACK 1

int main(){
  int i,j,u,v,k,n;
  int mincost,sum=0;
  int a[MAX][MAX],d[MAX],pi[MAX],color[MAX];
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      a[i][j] = INF;
      //a[i][j] = NIL;
    }
  }
  
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    //printf("u=%d k=%d\n",u,k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      scanf("%d",&a[u][v]);
    }
  }
  /*
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      printf("%d ",a[i][j]);
    }
    printf("\n");
  }      
  */ 
  for(u=0;u<n;u++){
    d[u] = INF;
    pi[u] = NIL;
    color[u] = WHITE;
  }
  d[0] = 0;

  while(1){

    mincost = INF;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<mincost){
	mincost = d[i];
	u = i;
      }
    }
    
    if(mincost==INF)break;

    color[u] = BLACK;
    
    for(v=0;v<n;v++){
      if( color[v]!=BLACK && a[u][v]+d[u] < d[v]){ // a[u][v]
	pi[v] = u;
	d[v] = a[u][v] + d[u]; // a[u][v]
      }
    }
    
  }

  for(i=0;i<n;i++){
    printf("%d %d\n",i,d[i]);
  }
  
  return 0;
}

Measured memory_bytes: 640
#include<stdio.h>

#define MAX 100005
#define N 100

typedef struct{
  char name[N];
  int t;
}P;

P Q[MAX+1];
int head, tail;

void Enqueue(P x){
  if(MAX==tail) tail=0;
  Q[tail]=x;
  tail++;
}

P Dequeue(void){
  if(head==MAX) head=0;
  return Q[head++];
}


int main(){
  int i,q,n,T=0;
  P a;
  scanf("%d %d", &n, &q);
  
  for (i=0;i<n;i++){
    scanf("%s%d",a.name,&a.t);
     Enqueue(a);
  }
  
  while(n!=0){
    a=Dequeue();
    if(a.t>q){
      a.t=a.t-q; 
      T+=q;
      Enqueue(a);
    } 
    else{
      T=T+a.t;
      printf("%s %d\n",a.name,T);
      n--;
    }
  }
  
  return 0;
}

Measured memory_bytes: 10752
#include<stdio.h>
#define N 8
#define FREE -1
#define NOTFREE 1
#define TRUE 2
#define FALSE 3

int Q[N][N];
int row[N],col[N],dpos[2*N-1],deng[2*N-1];/*縦 横 斜め*/
void set(void);
void putQ(int);
void print(void);

int main()
{
  set();
  int k,r,c,i,j;
  scanf("%d",&k);
  for(i=0;i<N;i++){
    for(j=0;j<N;j++)Q[i][j]=FALSE;
                  }
  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    Q[r][c]=TRUE; }
 
  putQ(0);
  
  return 0;
}

void set()/*初期設定*/
{
  int i;
  for(i=0;i<N;i++)
    {row[i]=FREE;
      col[i]=FREE;}
  for(i=0;i<2*N-1;i++)
    {dpos[i]=FREE;
      deng[i]=FREE;}
}

void putQ(int i)
{
  int j;
  if(i == N){
    print();
    return;
  }
  
  for(j=0;j<N;j++){
    if(NOTFREE==col[j] || NOTFREE==dpos[i+j] || NOTFREE==deng[i-j+(N-1)])
	continue;

      row[i]=j;
      col[j]=dpos[i+j]=deng[i-j+(N-1)]=NOTFREE;
      
      putQ(i+1);
      row[i]=col[j]=dpos[i+j]=deng[i-j+(N-1)]=FREE;
    }
}

void print()
{int i,j;
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(Q[i][j]==TRUE){
	if(row[i]!=j)return;}
                    }
	           }
  
  for(i=0;i<N;i++){
    for(j=0;j<N;j++){
      if(row[i]==j)printf("Q");
      else printf(".");	}
    printf("\n");
  }
}


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

#define ll long long
#define d long double

#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define dscf(n) scanf("%Lf",&n)
#define pri(n) printf("%d ",(int)n)
#define lpri(n) printf("%lld ",n)
#define dpri(n) printf("%Lf ",n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define dprin(n) printf("%Lf\n",n)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,ini,n) for(ll i=ini;i<(int)n;i++)
#define all(x) x.begin(),x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define bitcount(n) __builtin_popcount(n)
#define tc   int tt; scf(tt); while(tt--)
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265358979323846264

const ll M =1000000007;
const int N = 1e6+7;

ll power(ll a,ll n)
{
    if(n==0)
    {
        return 1;
    }

    if(n%2==0)
    {
        return power((a*a)%M,n/2)%M;
    }

    return ((a%M)*(power((a*a)%M,n/2)%M))%M;
}

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

    ll ans=1;

   ans=power(10,n)%M;
   ans=(ans-power(9,n)%M+M)%M;
   ans=(ans-power(9,n)%M+M)%M;
   ans=(ans+power(8,n)%M)%M;
   cout<<ans;

return 0;
}

Measured memory_bytes: 3572
import copy
N = int(input())
li = list(map(int,input().split()))
ans = copy.copy(li)
ans.sort()

count = 0
judge = True

for i in range(N-1):
    if (li[i] != ans[i]):
        count = count + 1
        if(count > 2):
            judge = False
            break

if(judge):
    print('YES')
else:
    print('NO')

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var A = new Tuple<string, int>[n];
            var dict = new Dictionary<int, List<string>>();
 
            for (var i = 0; i < n; i++)
            {
                var t = Console.ReadLine().Split();
                A[i] = new Tuple<string, int>(t[0], int.Parse(t[1]));

                if (dict.ContainsKey(A[i].Item2))
                    dict[A[i].Item2].Add(A[i].Item1);
                else
                    dict[A[i].Item2] = new List<string>() { A[i].Item1 };
            }

            QuickSort(A, 0, n - 1);

            var isStable = true;
            for (var i = 0; i < n; i++)
            {
                if (A[i].Item1 != dict[A[i].Item2][0])
                {
                    isStable = false;
                    break;
                }
                dict[A[i].Item2].RemoveAt(0);
            }

            Console.WriteLine(isStable ? "Stable" : "Not stable");

            foreach (var a in A)
            {
                Console.WriteLine($"{a.Item1} {a.Item2}");
            }
        }

        static void QuickSort(Tuple<string, int>[] A, int p, int r)
        {
            if (p < r)
            {
                var q = Partition(A, p, r);
                QuickSort(A, p, q - 1);
                QuickSort(A, q + 1, r);
            }
        }

        static int Partition(Tuple<string, int>[] A, int p, int r)
        {
            var x = A[r];
            var i = p - 1;
            for (var j = p; j < r; j++)
            {
                if (A[j].Item2 <= x.Item2)
                {
                    i++;
                    Swap(ref A[i], ref A[j]);
                }
            }
            
            Swap(ref A[i + 1], ref A[r]);

            return i + 1;
        }

        public static void Swap<T>(ref T one, ref T two)
        {
            var temp = one;
            one = two;
            two = temp;
        }
    }
}



Measured memory_bytes: 32556
#include <bits/stdc++.h>
using namespace std;
const int MD=998244353;
const int N=305;
int a[N],n;
int f[N*N],g[N*N];
void add(int &x,int y) {
	x+=y;
	if(x>=MD) x-=MD;
	if(x<0) x+=MD;
}
int main() {
	scanf("%d",&n);
	int sum=0,t=1;
	for(int i=0;i<n;i++) {
		scanf("%d",&a[i]);
		sum+=a[i];
		t=1LL*t*3%MD;
	}
	f[0]=1;
	for(int i=0;i<n;i++) {
		for(int j=sum/2;j>=a[i];j--) {
			add(f[j],1LL*f[j-a[i]]*2%MD);
		}
	}
	int ans=0;
	for(int i=0;i<=sum/2;i++) add(ans,f[i]);
	if(sum%2==0) {
		g[0]=1;
		for(int i=0;i<n;i++) {
			for(int j=sum/2;j>=a[i];j--) {
				add(g[j],g[j-a[i]]);
			}
		}
		add(ans,-g[sum/2]);
	}
	add(t,1LL*ans*3%MD*(-1));
	printf("%d\n",t);
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define test int t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

typedef long long ll;
using namespace std;

int main()
{
    int n;
    cin>>n;
    string s1="AC",s2="WA",s3="TLE",s4="RE";
    int n1=0,n2=0,n3=0,n4=0;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        if(s==s1)
            n1++;
        else if(s==s2)
            n2++;
        else if(s==s3)
            n3++;
        else
            n4++;
    }
    cout<<s1<<" x "<<n1<<endl;
     cout<<s2<<" x "<<n2<<endl;
      cout<<s3<<" x "<<n3<<endl;
       cout<<s4<<" x "<<n4<<endl;


return 0;
}


Measured memory_bytes: 3616
unit = ['', 'Man', 'Oku', 'Cho', 'Kei', 'Gai', 'Jo', 'Jou', 'Ko', 'Kan', 'Sei', 'Sai', 'Gok', 'Ggs', 'Asg', 'Nyt', 'Fks', 'Mts']
while true
  a,b = gets.split()
  if a=='0' then break end
  p = a.to_i**b.to_i
  s = ''
  for i in 0..17 do
    rem = p%10000
    if rem!=0 then s = rem.to_s + unit[i] + s end
    p /= 10000
  end
  puts s
end

Measured memory_bytes: 6128
n, m = map(int, input().split())
to = [[] for i in range(n)]


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

used = [False for i in range(n)]
perm = [0 for i in range(n)]
count = 0
#print(to)
def permutation(pos, last):
    global count
    if pos == last:
        #処理
        if perm[0] == 0:
            connect = False
            count_check = True
            #print(perm)
            for i in range(1, n):
                for j in to[perm[i - 1]]:
                    if perm[i] == j:
                        connect = True
                if not connect:
                    count_check = False
                    break
                else:
                    connect = False
            if count_check:
                count += 1
        else:
            return
    for i in range(last):
        if not used[i]:
            perm[pos] = i
            used[i] = True
            permutation(pos + 1, last)
            used[i] = False
    return


permutation(0, n)
print(count)


Measured memory_bytes: 3188
#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;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

int main(){
  int N, T;
  cin >> N >> T;
  vector<int> t(N);
  REP(i,N) cin >> t[i];

  ll res = T;
  REP(i,N - 1) {
    res += min(t[i + 1] - t[i], T);
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;

const int N=100005;

int n;
ll ans;
int a[N*3];

int main(){
	int i;
	scanf("%d",&n);
	for (i=1;i<=3*n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+3*n);
	for (i=3*n-1;i>n;i-=2) ans+=1ll*a[i];
	printf("%lld\n",ans);
	return 0;
} 

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

#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;

TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM T> inline istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
TPL<TNM V, TNM H> void resize(vector<V>& _v, const H _h) { _v.resize(_h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& _v, const H& _h, const T& ... _t) { _v.resize(_h); for (auto& __v : _v) resize(__v, _t ...); }
TPL<TNM V, TNM T> TNM enable_if<!is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { std::fill(ALL(_v), _t); }
TPL<TNM V, TNM T> TNM enable_if<is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { for (auto& _e : _v) fill(_e, _t); }
TPL<TNM T> inline void UNIQUE(vector<T>& _v) { sort(ALL(_v)); _v.erase(unique(ALL(_v)), _v.end()); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

int main(void) {
	int N, D;
	cin >> N >> D;
	int X = 2 * D + 1;
	cout << (N + X - 1) / X << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define randome_generate srand(std::chrono::high_resolution_clock::now().time_since_epoch().count())
using namespace std;
string s,t;
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s>>t;
	cout<<t<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
array = list(map(int, input().split()))

swap_num = 0
for i in range(n):
    for j in reversed(range(1, n)):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
            swap_num += 1
print(' '.join([str(e) for e in array]))
print(swap_num)


Measured memory_bytes: 5608
import sys
X = int(input())

if X == 1 or X==2:
  print(2)
  sys.exit()

while(True):
  flg = True
  if X%2 == 0:
    X += 1
    continue
    
  for i in range(3,X):
    if X%i == 0:
      flg = False
      
  if flg is True:
    print(X)
    sys.exit()

  X += 2

Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int main()
{
    long long n;
    long long a[88];
    a[0] = 2; a[1] = 1;
    cin >> n;
    for(long long i = 2; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
    }
    cout << a[n];
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
res = list()
for i in range(n):
	res += [(i+1, a[i])]

res = sorted(res, key=lambda x : x[1])
for i in range(n):
	if i == n-1:
		print(res[i][0])
	else :
		print('{} '.format(res[i][0]), end='')


Measured memory_bytes: 19968
//Author: Rafael Santos
//Site: santos-rj.github.io

#include <bits/stdc++.h>

#define desync ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0)
#define endl "\n"
#define pb push_back
#define mp make_pair
#define MAXN 1005
#define MAXV 1010
#define ff first
#define ss second

typedef long long ll;
typedef long int li;

using namespace std;

void solve(){
	string num;
	ll ans = 0;
	
	cin >> num;
	
	int tamanho = num.size();
	
	for(ll i = 0; i < tamanho; i++) ans += (num[i] - 48);
		
	if(ans%9==0 || ans == 0)
		cout << "Yes" << endl;
	else	
		cout << "No" << endl;
}

int main(){

    desync;

    ll t = 1;
    //cin >> t;
	
    while (t--)
    {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3744
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
ll mod = 1000000007;

int main() {
    ll a,b,x;
    cin >> a >> b >> x;
    if(a != 0){
        cout << b/x - (a-1)/x << endl;
    }else{
        cout << b/x+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
int ball[11];
int temp[2][11];
bool dfs(int x)
{
	if(x>10)
		return 1;
	if(temp[0][0]==0||temp[0][temp[0][0]]<ball[x])
	{
		temp[0][++temp[0][0]]=ball[x];
		if(dfs(x+1))
			return 1;
		temp[0][0]--;
	}
	if(temp[1][0]==0||temp[1][temp[1][0]]<ball[x])
	{
		temp[1][++temp[1][0]]=ball[x];
		if(dfs(x+1))
			return 1;
		temp[0][0]--;
	}
	return 0;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=10;i++)
			scanf("%d",ball+i);
		memset(temp,0,sizeof temp);
		if(dfs(1))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 2516