akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>

#define MAX 2000
#define LRMAX 1999
#define ANSMAX 3999

using namespace std;

int light_1d(int (*a)[MAX], int l, int i, int j, int d){
  int s = 0;

  while(true){
    if(d==0){
      j++;
      if(j>l-1 || a[i][j] == 1) break;
      s++;
    }
    else if(d==1){
      j--;
      if(j<0 || a[i][j] == 1) break;
      s++;
    }
  }

  return s;
}

int light_4d(int (*a)[MAX], int (*a_flip)[MAX], int H, int W, int i, int j, int ans){
  int sum, center = 1;

  int up = light_1d(a_flip, H, j, i, 1);
  if(H-(i+1)<=ans-(center+LRMAX+up)) return 0;

  int down = light_1d(a_flip, H, j, i, 0);
  if(W<=ans-(center+up+down)) return 0;

  int left = light_1d(a, W, i, j, 1);
  if(W-(j+1)<=ans-(center+up+down+left)) return 0;

  int right = light_1d(a, W, i, j, 0);
  if((sum = center+up+down+left+right)<=ans) return 0;

  return sum;
}

int main(void){

  int H, W;
  string S;
  int a[MAX][MAX], a_flip[MAX][MAX];
  int result, ans = 0;

  cin >> H >> W;
  for(int i=0; i<H; i++){
    cin >> S;
    for(int j=0; j<W; j++){
      if(S[j]=='.') a[i][j] = 0;
      else if(S[j]=='#') a[i][j] = 1;
      a_flip[j][i] = a[i][j];
    }
  }

  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      if(a[i][j]==1) continue;
      if((result = light_4d(a, a_flip, H, W, i, j, ans))!=0) ans = result;
      if(ans==ANSMAX) break;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 34852
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            if(a==0 && b == 0){
                break;
            }else{
                int ans = 0;
                for(int i = 1 ; i <= a-2 ; i++){
                    for(int j = i+1 ; j <= a-1 ; j++){
                        for(int k = j+1 ; k <= a ; k++){
                            if(i+j+k == b){
                                ans++;
                            }else{
                            }
                        }
                    }
                }
                System.out.println(ans);
            }
        }
    }
}



Measured memory_bytes: 26708
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int mxm2(int a, int b, int c)
{
    if(a>=b && a>=c)
        return a;
    else if(b>=a && b>=c)
        return b;
        else return c;
}
int mxm(int a, int b)
{
    if(a>b)
        return a;
    else return b;
}
int vacation(int a[], int b[], int c[], int n)
{
    if(n==1)
        return mxm2(a[0],b[0],c[0]);
    int as[n-1],bs[n-1],cs[n-1];
    as[0]=a[1]+mxm(b[0],c[0]);
    bs[0]=b[1]+mxm(a[0],c[0]);
    cs[0]=c[1]+mxm(a[0],b[0]);
    for(int i=1;i<n-1;i++)
    {
        as[i]=a[i+1]+mxm(bs[i-1],cs[i-1]);
        bs[i]=b[i+1]+mxm(as[i-1],cs[i-1]);
        cs[i]=c[i+1]+mxm(as[i-1],bs[i-1]);
    }
    return mxm2(as[n-2],bs[n-2],cs[n-2]);
}
int main()
{
    int n;
    cin>>n;
    int a[n],b[n],c[n];
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
    cout<<vacation(a,b,c,n);
}


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

#pragma warning(disable:4996)
using namespace std;
using ld = long double;


int main() {
	int N;cin>>N;
	vector<vector<int>>vecs(N);
	for (int i = 0; i < N; ++i) {
		int a;cin>>a;a--;
		a=N-1-a;
		vecs[a].push_back(i);
	}
	list<int>li;
	vector<int>anss(N);
	auto k=li.begin();
	queue<decltype(k)>que;
	for (int i = 0; i < N; ++i) {
		li.push_back(-1-i);
		for (int j=0;j<vecs[i].size();++j){
			li.push_back(vecs[i][j]);
		}
	}

	for (auto it = li.begin(); it != li.end(); ++it) {
		auto jt=next(it);
		if (jt != li.end()) {
			int a=*it;
			int b=*jt;
			if (a < 0 && b >= 0) {
				que.push(jt);
			}
		}
	}
	while (!que.empty()) {
		auto it=que.front();
		que.pop();
		int a,b;
		if (it == li.begin()||it==li.end()) {
			a=li.back();
			b=li.front();
			anss[-a - 1] = b + 1;

			li.erase(li.begin());
			li.erase(prev(li.end()));

			if (!li.empty() && li.back() < 0 && li.front() >= 0) {
				que.push(li.begin());
			}
		}
		else {
			a=*prev(it);
			b = *it;

			anss[-a-1]=b+1;
			auto kt=li.erase(it);
			kt=li.erase(prev(kt));

			if (!li.empty()) {
				if (kt == li.end()||kt==li.begin()) {
					if (li.back() < 0 && li.front() >= 0) {
						que.push(li.begin());
					}
				}
				else {
					if (*prev(kt) < 0 && *kt >= 0) {
						que.push(kt);
					}
				}
			}
		}
	}

	for (int i = 0; i < anss.size(); ++i) {
		cout<<anss[N-1-i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 14404
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n",(x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define isYes(x) printf("%s\n",(x) ? "Yes" : "No")
#define isPossible(x) printf("%s\n",(x) ? "Possible" : "Impossible")
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
// #define INF (1<<29)

const long long INF = 1LL<<50;

#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define pie 3.14159265358979323846
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
// const int mod =(int)998244353;
const int mod =(int)1e9+7;

const int MAX =510000;
ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    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;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
ll gcd(ll a,ll b){
    if(a<0)a=-a;
    if(b<0)b=-b;
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
  if(a<0)a=-a;
  if(b<0)b=-b;
    ll g;g=gcd(a,b);
    return b/g*a;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
bool compare_by_a(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return a.second < b.second;
    }
}
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;
}
ll RS(ll N,ll P){
    if(P==0){
        return 1;
    }else{
        if(P%2==0){
            ll t=RS(N,P/2);
            return t*t;
        }else{
            return N*RS(N,P-1);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    string S;cin>>S;
    int ans=0;
    int final_ans=0;
    REP(i,3){
        if(S[i]=='R'){
            ans++;
            final_ans=max(final_ans,ans);
        }else{
            ans=0;
        }
    }
    cout<<final_ans<<endl;
    return 0;
} 


Measured memory_bytes: 3608
A,B,C = map(int,input().split(" "))
Amod = A%B

if Amod==0:
    if C!=0:
        print("NO")
    else:
        print("YES")
else:
    i=0
    while(i<=B):
        i+=1
        c = (i%B * Amod)
        if (c%B==C):
            print("YES")
            break
    if(i>B):
        print("NO")

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

using namespace std;

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

vector<string> func(string input){
	vector<string> ret;
	stringstream ss;
	ss << input;
	string s;
	vector<pair<int,string> > tmp;
	while(ss>>s){
		if(s[s.size()-1] == '.') s = s.substr(0,s.size()-1);
		//ret[s.size()].push_back(s);	
		set<char> se;
		rep(i,s.size()){
			se.insert(s[i]);
		}
		tmp.push_back(make_pair(-(int)se.size(), s));
	}
	sort(tmp.begin(), tmp.end());
	rep(i,tmp.size()){
		ret.push_back(tmp[i].second);
	}
	return ret;
}

vector<vector<int> > ans;
vector<vector<string> > vv;

bool check(string &a, string &b, vector<int> tik){
	rep(i,a.size()){
		int aa = a[i]-'A';
		int bb = b[i]-'A';
		if(tik[aa] == -1 && tik[bb] == -1){
			tik[aa] = bb;
			tik[bb] = aa;
		}
		else if(tik[aa] == bb && tik[bb] == aa){
			continue;
		}
		else{
			return false;
		}
	}
	return true;
}

void update(string &a, string &b, vector<int> &tik){
	/*cout<<a<<" "<<b<<endl;
	rep(i,26) cout<<tik[i]<<" ";
	cout<<endl;
	*/
	rep(i,a.size()){
		int aa = a[i]-'A';
		int bb = b[i]-'A';
		if(tik[aa] == -1 && tik[bb] == -1){
			tik[aa] = bb;
			tik[bb] = aa;
		}
	}
	/*
	rep(i,26) cout<<tik[i]<<" ";
	cout<<endl;
	*/
}

void saiki(int x, vector<string> &w, vector<int> tik){
	if(x == w.size()){
		ans.push_back(tik);
		return;
	}
	string &s = w[x];
	if(ans.size()>=2) return;
	rep(i,vv[s.size()].size()){
		if(check(s, vv[s.size()][i], tik)){
			vector<int> tmp = tik;
			update(s, vv[s.size()][i], tik);
			saiki(x+1, w, tik);
			tik = tmp;	
		}
	}
}

int main(){
	int n;
	while(cin>>n, n){
		//cout<<n<<endl;
		vv = vector<vector<string> >(21);
		rep(i,n){
			string s;
			cin>>s;
			vv[s.size()].push_back(s);
		}
		string input;
		getline(cin, input);
		getline(cin, input);
		//cout<<input<<endl;
		//return 0;
		/*
		vector<vector<string> > in = func(input);
		rep(i,21){
			sort(in[i].begin(), in[i].end());
			in[i].erase(unique(in[i].begin(), in[i].end()), in[i].end());
		}
		*/
		vector<string> w = func(input);
		/*
		for(int i=20; i>=1; i--){
			rep(j,in[i].size()){
				w.push_back(in[i][j]);
			}
		}
		*/
		vector<int> tik(26,-1);
		ans.clear();
		saiki(0,w,tik);
		if(ans.size()>1){
			cout<<"-."<<endl;
		}
		else{
			vector<int> tik = ans[0];
			/*cout<<"ttt "<<endl;
			rep(i,26){
				cout<<t[i]<<" ";
			}
			cout<<endl;
			*/
			rep(i,input.size()){
				if(isupper(input[i])){
					//cout<<input[i]<<" "<<tik[input[i]-'A']<<endl;;
					cout<<char(tik[input[i]-'A']+'A');	
				}
				else{
					cout<<input[i];
				}		
			}
			cout<<endl;
		}
	}
}

Measured memory_bytes: 3208
from functools import lru_cache

@lru_cache(maxsize=None)
def attack(x):
    if x == 1:
        return 1
    nxt = x // 2
    return 1 + 2 * attack(nxt)


def submit():
    h = int(input())
    print(attack(h))


if __name__ == "__main__":
    submit()

Measured memory_bytes: 3572
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < (int)(x); i++)
#define pb push_back
#define mp make_pair
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;
// SUN,MON,TUE,WED,THU,FRI,SAT

int main(){
    string s;cin >> s;
    int ans = 0;
    if(s == "SUN")ans = 7;
    else if(s == "SAT")ans = 1;
    else if(s == "FRI")ans = 2;
    else if(s == "THU")ans = 3;
    else if(s == "WED")ans = 4;
    else if(s == "TUE")ans = 5;
    else if(s == "MON")ans = 6;
    cout << ans << endl;

}

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

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

	for(int a = 0; a <= n; a++){
		for(int b = 0; b <= n-a; b++){
			int c = n-a-b;
			if(10000*a + 5000*b + 1000*c == y){
				cout << a << " " << b << " " << c << endl;
				return 0;
			}
		}
	}
	cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
#include  <bits/stdc++.h>
using namespace std;
//vector<int> vec(N,0);
int main() {
  int N;
  cin >> N;
  vector<int>vec(N);
  for(int i=0;i<N;i++){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(),vec.end());
  
  cout << vec.at(N-1)-vec.at(0)<<endl;
  
}

Measured memory_bytes: 256
cards_A = [card for card in input()]
cards_B = [card for card in input()]
cards_C = [card for card in input()]

def win(a,b,c):
  winner = ''
  can_play = True
  card = a.pop(0)
  while can_play:
    if(card == 'a'):
      if(len(a)>0):
        card = a.pop(0)
      else:
        winner = 'A'
        can_play = False
    elif(card == 'b'):
      if(len(b)>0):
        card = b.pop(0)
      else:
        winner = 'B'
        can_play = False
    elif(card == 'c'):
      if(len(c)>0):
        card = c.pop(0)
      else:
        winner = 'C'
        can_play = False
  return winner
  
print(win(cards_A,cards_B,cards_C))

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

int main() {
  int N,k = 0;
  cin >> N;
  for(int i = 0; i < N; i++){
    string s;cin >> s;
    if(s == "Y") k = 1;
  }
  if(k) cout << "Four";
  else cout << "Three";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
int n,ans;
char s[200][20];
bool ck(int a,int b) {
	int x=strlen(s[a]+1),y=strlen(s[b]+1);
	if (x!=y) return 0;
	for (int i=1;i<=x;i++)
		if (s[a][i]!=s[b][i]) return 0;
	return 1;
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n); ans=1;
	for (int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<i;j++)
			if (ck(i,j)) { ans=0; break; }
		if (!ans) break;
		if (i>1) {
			if (s[i-1][strlen(s[i-1]+1)]!=s[i][1]) {
				ans=0; break;
			}
		}
	}
	if (ans) printf("Yes\n"); else printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

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

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

    vector<int> s(n+1);
    rep(i,n) {
        s[i+1] = (s[i] + a[i])%k;
    }

    map<int, int> mp;
    queue<int> Q;

    ll ans = 0;
    rep(j, n+1) {
        ans += mp[s[j]];
        mp[s[j]]++;
        Q.push(s[j]);
        if(Q.size() == k) {
            mp[Q.front()]--;
            Q.pop();
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12032
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
int main(){
  string s;
  cin >> s;
  int h=s.size()-1;
  while(s.size()>1){
    if((s[0]=='h')&&(s[1]=='i')){
      s.erase(0,1);
      s.erase(0,1);
    }
    else{
      cout << "No" << endl;
      return  0;
    }
  }
  if(s.size()!=0)
    cout << "No" << endl;
  else if(s.size()==0)
    cout << "Yes" << endl;
    
}

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

using namespace std;

int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;

    int k=a/d;
    int l=c/b;

    if(a%d!=0)
        k++;
    if(c%b!=0)
        l++;
    
    if(k>=l){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3592
p=0
q=0
n=int(input())
for i in range(n):
    m=list(input().split())
    
    if len(m[0])<=len(m[1]):
        r=len(m[0])
    elif len(m[0])>len(m[1]):
        r=len(m[1])
    for j in range(r):
        x=ord(m[0][j:j+1])
        y=ord(m[1][j:j+1])
        if x>y:
            p+=3
            break
        elif x<y:
            q+=3
            break
    if x==y:
        if len(m[0])<len(m[1]):
            q+=3
        elif len(m[0])>len(m[1]):
            p+=3
        else:
            p+=1
            q+=1
        
print(p,end=' ')
print(q)
            


Measured memory_bytes: 5604
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#define int long long
#define ll getchar();getchar();return 0;
	using namespace std;
	signed main(){
		string s;
		cin >> s;
		for (int i = 0; i < s.size(); i+=2) {
			cout << s[i];
		}
		cout << endl;
}

Measured memory_bytes: 512
import itertools
##print(ord("A"))
#n = int(input())
#n,k = map(int,input().split())
#h = list(map(int,input().split()))	
s = input()
ok  = "Yes"
for i in range(1,len(s)+1):
    #print(i,s[i-1])
    if i%2 == 0:
        if s[i-1]=="R":
            ok = "No"
    else:
        if s[i-1] == "L":
            ok = "No"

print(ok)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int sum=0;
    sort(a,a+n);
    for(int i=0;i<n-1;i++){
        sum+=a[i];
    }
    sum+=(a[n-1]/2);
    cout << sum << endl;
}


Measured memory_bytes: 256
import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

A, B, N = map(int, input().split())

if A*N < B:
    print(0)
    exit()

if N < B:
    print((A*N)//B - A*(N//B))
    exit()

aa = N//B
x = aa*B - 1
res = (A*x)//B - A*(x//B)

print(res)


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

struct Node
{
  int key;
  Node *next, *prev;
};

Node *nil;

void init()
{
  nil = (Node *)malloc(sizeof(Node));
  nil->next = nil;
  nil->prev = nil;
}

void insert(int key)
{
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  x->prev = nil;
  nil->next = x;
}

Node *listSearch(int key)
{
  Node *x = nil->next;
  while (x != nil)
  {
    if (x->key == key)
    {
      return x;
    }
    x = x->next;
  }
}

void deleteNode(Node *x)
{
  if (x == nil)
  {
    return;
  }
  x->next->prev = x->prev;
  x->prev->next = x->next;
  free(x);
}

void deleteFirst()
{
  deleteNode(nil->next);
}

void deleteLast()
{
  deleteNode(nil->prev);
}

void deleteKey(int key)
{
  deleteNode(listSearch(key));
}

int main()
{
  init();
  int n;
  cin >> n;
  string com;
  int key;
  for (int i = 0; i < n; i++)
  {
    cin >> com;
    if (com[0] == 'i')
    {
      cin >> key;
      insert(key);
    }
    else if (com.size() == 6)
    {
      cin >> key;
      deleteKey(key);
    }
    else if (com.size() == 11)
    {
      deleteFirst();
    }
    else
    {
      deleteLast();
    }
  }

  Node *x = nil->next;
  while (x != nil)
  {
    cout << x->key;
    if (x->next != nil)
    {
      cout << " ";
    }
    x = x->next;
  }
  cout << endl;
}


Measured memory_bytes: 34368
#include <stdio.h>
#include <string.h>

int main(void)
{
	int k;
	char s[100];
	scanf("%d",&k);
	scanf("%s",s);
	if(strlen(s)<=k) printf("%s\n",s);
	else if(strlen(s)>k){
		for(int i=0;i<k;i++){
			printf("%c",s[i]);
		}
		printf("...\n");
	}
	return 0;
}



Measured memory_bytes: 1616
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const long long int inf=INT_MAX;
const int MAX =1e5+6;
long long int dis[MAX];
vector<long long int>adj[MAX];
void intit(int n){
	for(int i=0;i<n;i++){
		dis[i]=inf;
	}
}
int main(){
	long long 	int i,j,k,n,m,s;
	scanf("%lld %lld %lld" , &n , &m , &s);
	for(i=0;i<m;i++){
		long long int x,y,z;
		scanf("%lld %lld %lld" , &x , &y, &z);
		adj[i].push_back(x);
		adj[i].push_back(y);
		adj[i].push_back(z);
	}
	intit(n);
	dis[s]=0;
	for(i=0;i<n-1;i++){
		int j=0;
		while(adj[j].size()!=0){
			if((dis[adj[j][1]]>dis[adj[j][0]]+adj[j][2])&&dis[adj[j][0]]!=inf){
				dis[adj[j][1]]=dis[adj[j][0]]+adj[j][2];
				
			}
			j++;
		}
	}
	int f=0;
	for(int i=0;i<n-1;i++){
		int j=0;
		while(adj[j].size()!=0){
			if((dis[adj[j][1]]>dis[adj[j][0]]+adj[j][2])&&dis[adj[j][0]]!=inf){
				f=1;
				break;
			}
			j++;
		}
	}
	if(f){
		cout<<"NEGATIVE CYCLE"<<"\n";
	}
	else{
	for(i=0;i<n;i++){
		if(dis[i]>=inf)
			cout<<"INF"<<"\n";
		else
		printf("%lld\n", dis[i] );
	}
}
}



Measured memory_bytes: 5628
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++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 all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define VECV(a,n,m) vector<vector<int>> a(n, vector<int>(m));
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N,K;
  cin>>N>>K;
  int cnt=1;
  int A=K;
  while(A<=N){
    A=A*K;
    cnt=cnt+1;
  }
  cout<<cnt<<endl;
}


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

#一回入れ替える
for i in range(N):
    if not A_n[i] == i+1:
        #print("swap")
        j = A_n[i]-1
        A_n[i], A_n[j] = A_n[j], A_n[i]
        break

#print(A_n)
for i in range(N):
    if not A_n[i] == i+1:
        print("NO")
        exit()
print("YES")


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

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

  vector<int> s(N);
  vector<int> c(N);

  for(int i = 0; i < M; i++){
    cin >> s[i] >> c[i];
  }

  vector<bool> dup(N + 1);
  vector<int> x(N + 1);
  
  for(int i = 0; i < (N + 1); i++){
    dup[i] = false;
  }

  for(int i = 0; i < M; i++){
    if(s[i] > N || s[i] < 1 || c[i] > 9 || c[i] < 0){
      cout << -1 << endl;
      return 0;
    }else{
      if((dup[s[i]] == true) && (c[i] != x[s[i]])){
        cout << -1 << endl;
        return 0;
      }else if(N != 1 && s[i] == 1 && c[i] == 0){
        cout << -1 << endl;
        return 0;
      }else{
        dup[s[i]] = true;
        x[s[i]] = c[i];
      }
    }
  }
  for(int i = 1; i < N + 1; i++){
    if(!dup[i]){
      if(i == 1){
        if(N == 1){
          x[i] = 0;
        }else{
          x[i] = 1;
        }
      }else{
        x[i] = 0;
      }
    }
  }
  for(int i = 1; i < N + 1; i++){
    cout << x[i];
  }
  cout << endl;
}


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

#define MAX_N 10005

int compare(string a, string b) {
	if (a.size() != b.size()) {
		if (a.size() < b.size())
			return -1;
		else
			return 1;
	}
	for (int k = 0; k < a.size(); k++) {
		if (a[k] > b[k])
			return 1;
		else if (a[k] < b[k])
			return -1;
	}
	return 0;
}

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

	const int STICKS[10] = { 7, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
	int A[MAX_N];
	for (int j = 0; j < M; j++) scanf("%d", A + j);

	string dp[MAX_N];
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			if (i == STICKS[A[j]] or (i > STICKS[A[j]] and dp[i - STICKS[A[j]]].size() > 0)) {
				string s = dp[i - STICKS[A[j]]];
				s.insert(s.begin(), 1, A[j] + '0');
				if (compare(s, dp[i]) > 0) dp[i] = s;
				string t = dp[i - STICKS[A[j]]];
				t.insert(t.end(), 1, A[j] + '0');
				if (compare(t, dp[i]) > 0) dp[i] = t;
			}
		}
	}
	printf("%s\n", dp[N].c_str());
	return 0;
}

Measured memory_bytes: 53376
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
int main(void){
    int n;
    cin>>n;
    map<ll, int> mp;
    rep(i, n){
        ll a;
        cin>>a;
        mp[a]++;
    }
    int ans = 0;
    for(auto p : mp){
        if(p.second%2 == 1) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define N 100010 
using namespace std;

inline int read()
{
	int 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*10+ch-'0'; ch=getchar();}
	return x*f;
}
struct edge
{
	int v,next;
}vs[N<<1];
int n,ee,st[N],F[N],sign[N],d[N];
inline void addedge(int u,int v)
{
	vs[++ee].v=v;vs[ee].next=st[u];st[u]=ee;
}
inline void dfs(int rt,int pr)
{
	int cnt=0;
	for(int i=st[rt];i;i=vs[i].next)
	{
		if(vs[i].v==pr) continue;
		cnt++; dfs(vs[i].v,rt);
	}
	if(!cnt) sign[rt]=1,F[rt]=1;
	if(cnt==1)
	{
		for(int i=st[rt];i;i=vs[i].next)
		{
			if(vs[i].v==pr) continue;
			F[rt]=F[vs[i].v]; sign[rt]=sign[vs[i].v];
		}
	}
	if(cnt>1)
	{
		for(int i=st[rt];i;i=vs[i].next)
		{
			if(vs[i].v==pr) continue;
			F[rt]+=F[vs[i].v]; sign[rt]|=sign[vs[i].v];
		}
		if(sign[rt]) F[rt]--,sign[rt]=0;
	}
}
int main()
{
	// freopen("read.in","r",stdin);
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read()+1, v=read()+1;
		addedge(u,v); addedge(v,u);
		d[u]++; d[v]++;
	}
	int Rt=1; for(;Rt<=n;Rt++) if(d[Rt]>=3) break;
	if(Rt>n) {puts("1"); return 0;}
	dfs(Rt,0); cout << F[Rt] << endl; return 0;
}

Measured memory_bytes: 4864
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        double sum =0;
        for(int a=0;a<N;a++){
            double x = sc.nextDouble();
            String u = sc.next();
            if(u.equals("JPY")==true) sum+=x;
            else sum+=x*380000;
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 22740
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
using pll = pair<ll, ll>;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vpii = vector<pii>;
using ti3 = tuple<int, int, int>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
bool isadj(pii a, pii b) {
	return abs(a.first - b.first) + abs(a.second - b.second) == 1;
}
int main() {
	int n;
	while (cin >> n, n) {
		vector<pair<pii, char>> buf;
		map<pii, vector<pair<pii, int>>> fadj;
		map<pii, int>futon;
		set<pii> fl;
		buf.reserve(n);
		rep(i, n) {
			int x, y;
			char d;
			cin >> x >> y >> d;
			buf.push_back(make_pair(pii(x, y), d));
			fl.insert(pii(x,y));
		}
		rep(i, n)rep(j, i) {
			pii p1 = buf[i].first, p2 = p1, q1 = buf[j].first, q2 = q1;
			if (buf[i].second == 'x')p2.first += 1;
			else p2.second += 1;
			if (buf[j].second == 'x')q2.first += 1;
			else q2.second += 1;
			int x = -1;
			if (isadj(p1, q1) || isadj(p2, q2))x = 0;
			else if (isadj(p1, q2) || isadj(p2, q1))x = 3;
			if (x != -1)fadj[p1].push_back({ q1,x }), fadj[q1].push_back({ p1,x });
		}
		bool ok = 1;
		while (!fl.empty()) {
			queue<pii> que;
			que.push(*fl.begin());
			futon[*fl.begin()] = 6;
			int ave = 3;
			fl.erase(*fl.begin());
			while (!que.empty()) {
				pii pos = que.front();
				int x = futon[que.front()];
				que.pop();
				for (auto b : fadj[pos]) {
					if (!futon[b.first]) {
						futon[b.first] = x^b.second;
						que.push(b.first);
						fl.erase(b.first);
					}
					else ave&=3&~(futon[b.first] ^ x^b.second);
				}
			}
			if (!ave) {
				ok = 0;
				break;
			}
		}
		cout << (ok ? "Yes" : "No") << endl;
	}
}

Measured memory_bytes: 6508
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner in = new Scanner(System.in);

		int u = in.nextInt();
		int[][] mat = new int[u][u];
		for (int i = 0; i < u; i++) {
			Arrays.fill(mat[i], -1);
		}
		for (int i = 0; i < u; i++) {
			int fromNode = in.nextInt();
			int toNodeCount = in.nextInt();
			for (int j = 0; j < toNodeCount; j++) {
				int toNode = in.nextInt();
				int edgeWeight = in.nextInt();
				mat[fromNode][toNode] = edgeWeight;
			}
		}

		// solve
		Set<Integer> x = new HashSet<>();
		Set<Integer> y = new HashSet<>();
		boolean[] visit = new boolean[u];
		for (int i = 1; i < u; i++) {
			y.add(i);
		}
		int[] nodeCost = new int[u];
		Arrays.fill(nodeCost, Integer.MAX_VALUE);
		x.add(0);
		nodeCost[0] = 0;
		visit[0] = true;

		while (!y.isEmpty()) {
			int min = Integer.MAX_VALUE;
			int v = -1;
			for (int from : x) {
				for (int to = 0; to < u; to++) {
					int visitCost = mat[from][to] + nodeCost[from];
					// toのノードが最小コストで訪問済でない場合
					if (mat[from][to] != -1 && !visit[to] && visitCost <= nodeCost[to]) {
						nodeCost[to] = visitCost;
						if (nodeCost[to] < min) {
							min = nodeCost[to];
							v = to;
						}
					}
				}
			}
			x.add(v);
			y.remove(v);
			visit[v] = true;
		}

		for (int i = 0; i < u; i++) {
			System.out.println(i + " " + nodeCost[i]);
		}
	}

}



Measured memory_bytes: 41612
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;



int main() {
	int w, h;
	cin >> w >> h;

	vector<int> p(w), q(h);

	FOR(i, 0, w) {
		cin >> p[i];
	}
	FOR(i, 0, h) {
		cin >> q[i];
	}
	sort(p.begin(), p.end());
	sort(q.begin(), q.end());

	long long cnt = 0;
	FOR(i, 0, w) {
		long long t = p[i];
		int pos = distance(q.begin(), lower_bound(q.begin(), q.end(), t));
		cnt += (h+1 - pos) * t;
	}
	FOR(i, 0, h) {
		long long t = q[i];
		int pos = distance(p.begin(), upper_bound(p.begin(), p.end(), t));
		cnt += (w+1 - pos) * t;
	}
	cout << cnt << endl;



	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <numeric>
#include <bitset>

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

template < typename T > void coutVector(vector<T> v){for(int i=0;i<int(v.size());++i){if(i>0)cout<<" "<<v[i];else cout<<v[i];}cout<<endl;}
template < typename T > void coutVectorWithEndl(vector<T> v){for(int i=0;i<int(v.size());++i){cout<<v[i]<<endl;}}
template < typename T > vector<T> cinVector(int n) {vector<T> res(n);for(int i=0;i<n;++i){cin>>res[i];}return res;}

const ll MOD = 1000000007;
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll nCk(ll n, ll k) {
    ll res = 1LL;
    if (k < 0 || n < 0) return res;
    for (ll i = n; i > n - k; --i) {
        res *= i;
        res %= MOD;
    }
    for (ll i = k; i > 0; --i) {
        res %= MOD;
        res *= modinv(i, MOD);
    }
    return res;
}
int main() {
    ll N, K; cin >> N >> K;
    if (K == N) {cout << 1 << endl;repp(i,0,K-1){cout << 0 << endl;}return 0;}
    if (K == 1) {cout << N+1 << endl;return 0;}
    
    repp(i,1,K+1) {
        ll b = nCk(K-1, i-1);
        ll r = 0;
        // RBRBR
        if (N - K >= 2 + i -1) r += nCk(N-K-1, 2 + i - 1 - 1);
        // BRBR or RBRB
        if (N - K >= 1 + i - 1) r += 2 * nCk(N-K-1, 1 + i - 1 - 1);
        // BRB
        if (i > 1 && N - K >= i - 1) r += nCk(N-K-1, i - 1 - 1);
        ll res = b * r % MOD;
        cout << res << endl;
    }
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    m = 0
    for c in a:
        m += c - 1
    return m


print(main())


Measured memory_bytes: 5716
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int omain(void){
	string s;
	cin >> s;
	int count = 0;
	for(int i=0;i<s.length();i++){
		if(s.at(i)=='+'){
			count++;
		}else{
			count--;
		}
	}
	cout << count << endl;
	return 0;
}

int digit_sum(int n){
	int ret = 0;
	int dig;
	while(n){
		dig = n % 10;
		ret = ret + dig;
		n = n /10;
	}

	return ret;
}

int main(void){
	int n;
	cin >> n;
	cout << ((n % digit_sum(n) == 0) ? "Yes" : "No") << endl;
	return 0;
}

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

int main(){
    int N;
    string S;
    cin >> N >> S;
    vector<int> num_white(N);
    vector<int> num_black(N);

    num_white[0] = (S[0]=='#') ? 1 : 0;
    for(int ii=1; ii<N; ii++){
        num_white[ii] = (S[ii]=='#') ? num_white[ii-1] + 1 : num_white[ii-1];
    }

    num_black[N-1] = (S[N-1]=='.') ? 1 : 0;
    for(int ii=N-2; ii>=0; ii--){
        num_black[ii] = (S[ii]=='.') ? num_black[ii+1] + 1 : num_black[ii+1];
    }

    int min_num = min(num_black[0], num_white[N-1]);
    for(int ii=0; ii<N-1; ii++){
        min_num = min(min_num, num_black[ii+1] + num_white[ii]);
    }
    cout << min_num << endl;
    return 0;
}


Measured memory_bytes: 2180
def main():

    x, n = map(int, input().split())
    ans = 0
    if n == 0:
        ans = x
        print(f'{ans}')
        exit()
    else:
        p = [int(i) for i in input().split()]

    for i in range(n):
        if x - i not in p:
            ans = x - i
            break
        if x + i not in p:
            ans = x + i
            break
    
    print(f'{ans}')


if __name__ == '__main__':
    main()

Measured memory_bytes: 9208
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);


    const long long MOD = 1000000007;
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        if (A[i] > i) {
            cout << 0 << '\n';
            return 0;
        }
    }

    vector<vector<int>> pos(n + 1);
    pos[0] = {-1, -2, -3};

    for (int i = 0; i < n; ++i) {
        pos[A[i] + 1].push_back(i);
    }
    for (int i = 0; i <= n; ++i) {
        if (pos[i].size() > 3) {
            cout << 0 << '\n';
            return 0;
        }
        if (i - 1 >= 0 && pos[i].size() > pos[i - 1].size()) {
            cout << 0 << '\n';
            return 0;
        }
    }

    long long res = 0;
    if (pos[1].size() == 1) {
        res = 3;
    } else if (pos[1].size() >= 2) {
        res = 6;
    } 

    for (int i = 2; i <= n; ++i) {
        if (pos[i].size() == 0) {
            break;
        }

        auto ord = pos[i];
        while (ord.size() < pos[i - 1].size()) {
            ord.push_back(n);
        }

        sort(ord.begin(), ord.end());
        long long cnt = 0;
        do {
            bool ok = true;
            for (int j = 0; j < ord.size(); ++j) {
                if (ord[j] <= pos[i - 1][j]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ++cnt;
            }
        } while (next_permutation(ord.begin(), ord.end()));

        (res *= cnt) %= MOD;
    }


    cout << res << '\n';


    return 0;
}

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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

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

int A,B,C,N;
vector<ll> l;

int dfs(int cur, int a, int b, int c) {
  int ret0,ret1,ret2,ret3;
  if(cur == N) {
    if(min({a,b,c}) > 0) return abs(a-A) + abs(b-B) + abs(c-C) - 30;
    else return INF;
  }
  ret0 = dfs(cur + 1, a, b, c);
  ret1 = dfs(cur + 1, a + l[cur], b, c) + 10;
  ret2 = dfs(cur + 1, a, b + l[cur], c) + 10;
  ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10;
  int d = min({ret0,ret1,ret2,ret3});
  // cout << cur  << " : " << a << " : " << b << " : " << c << " | " << ret0  << " : " << ret1  << " : " << ret2  << " : " << ret3 << " : " << min({ret0,ret1,ret2,ret3}) << " : d = " << d << endl;

  return d;
}

int main() {
  cin >> N >> A >> B >> C;
  int temp;
  for (ll i = 0; i < N; i++) {
    cin >> temp;
    l.push_back(temp);
  }
  // sort(l.begin(), l.end(), greater<int>());
  int result = dfs(0,0,0,0);
  cout << result << endl;

}


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

int b()
{
    int n;
    std::cin >> n;
    
    long long max = pow(10, 18);
    long long ans = 1;
    for(int i = 0; i < n; i++)
    {
        long long myVal;
        std::cin >> myVal;
        
        if(ans == -1 && myVal != 0)
        {
            continue;
        }
        
        if(myVal == 0)
        {
            ans = 0;
            break;
        }
        
        if((max / ans) < myVal)
        {
            ans = -1;
            continue;
        }
        
        ans *= myVal;
    }
    
    std::cout << ans << std::endl;
    
    return 0;
}

int main(int argc, const char * argv[])
{
    b();
    return 0;
}


Measured memory_bytes: 3636
N,M=map(int,input().split())
Al=[list(map(int,input().split()))[1:] for _ in range(N)]
V=[[False]*M for _ in range(N)]
for row, As in enumerate(Al):
    for A in As:
        V[row][A-1]=True
print(sum([all(f) for f in zip(*V)]))

Measured memory_bytes: 3064
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

mt19937 mrand(random_device{} ()); 

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

int n;
string s;
char tmp[100];

int read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  scanf("%s", tmp);
  s = tmp;
  return true;
}

map<pair<string, int>, int> mp;

void solve() {
  for (int i = 0; i < (1 << n); i++) {
    string cur;
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
        cur += s[j];
      }
    }
    for (int j = n - 1; j >= 0; j--) {
      if (!(i & (1 << j))) {
        cur += s[j];
      }
    }
    mp[make_pair(cur, __builtin_popcount(i))]++;
  }
  long long res = 0;
  for (int i = 0; i < (1 << n); i++) {
    string cur;
    for (int j = n - 1; j >= 0; j--) {
      if (!(i & (1 << j))) {
        cur += s[n + j];
      }
    }
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
        cur += s[n + j];
      }
    }
    res += mp[make_pair(cur, n - __builtin_popcount(i))];
  }
  printf("%lld\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 73984
import java.util.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;

import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static long mod=1000000007;
//    static int dx[]={-1,0,1,0};
//    static int dy[]={0,-1,0,1};

    public static void main(String[] args)   throws Exception, IOException{        
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);

//        int n = sc.nextInt();
        char c[]=sc.nextString().toCharArray();
        int r=0;
        if(c[0]==c[1])r++;
        if(c[2]==c[1])r++;
        if(c[2]==c[3])r++;
		
        out.println(r>0?"Bad":"Good");
        out.flush();
    }

    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
}


//class P {
//    int id, d;
//    P(int  id, int d) {
//        this.id=id;
//        this.d=d;
//    }
//}

//class P implements Comparable<P>{
//    int a,b;
//    double c;
//    P(int a, int b) {
//    	this.b=b;
//    	this.a=a;
//    	this.c=(double)b/a;
//    }
//
//    public int compareTo(P p){
//        return Double.compare(p.c,c);
//    }
//}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public int[] nextIntArray(int size) throws IOException{
        int r[] = new int[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextInt(); 
        }
        return r;
    }
    public long[] nextLongArray(int size) throws IOException{
        long r[] = new long[size];
        for (int i = 0; i < size; i++) {
            r[i] = this.nextLong(); 
        }
        return r;
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) (a).begin(),(a).end()
#define SORT(a) sort(all(a))

using ll = long long;
constexpr ll INF = 10000000000;
constexpr ll MOD = 1000000007;

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

	int n; cin >> n;
	vector<int>t(n);
	rep(i, n)cin >> t[i];

	int m; cin >> m;
	vector<int>p(m);
	vector<int>x(m);
	rep(i, m)cin >> p[i] >> x[i];
	rep(i, m)p[i] -= 1; //zero-indexed

	vector<int>ans(m);

	int sum = 0;
	rep(i, n)sum += t[i];

	rep(i, m) {
		ans[i] = sum - (t[p[i]] - x[i]);
	}
	rep(i, m)cout << ans[i] << endl;
}	




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int P=2019;
int L,R;
int ans;

int main()
{
	scanf("%d%d",&L,&R);
	if(R-L>=P)puts("0");
	else
	{
		int ans=1e9;
		FOR(i,L,R)FOR(j,i+1,R)chk_min(ans,1ll*i*j%P);
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
long long N, K;
long long f(long long n) {
	long long sum = n;
	for (int i = 1; i < N && sum > 0; ++i) {
		sum -= (sum+K-1) / K;
	}
	return sum;
}
long long f() {
	if (N == 1) return 0;
	long long l = 0, r = 1LL << 60;
	while (r - l >= 2) {
		long long m = (l + r) / 2;
		if (f(m) > 0) {
			r = m;
		} else {
			l = m;
		}
	}
	return l;
}
int main() {
	while (cin >> N >> K) cout << f() << endl;
}


Measured memory_bytes: 3112
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(char, "x", long, "y");
alias PQueue(T, alias less = "a>b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, a, b;
    scan(n, a, b);
    auto x = aryread();
    long cost;
    foreach (i; iota(n - 1))
    {
        cost += min(a * (x[i + 1] - x[i]), b);
    }
    cost.writeln();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 5928
h,w = map(int,input().split())
S = [(input()+'#') for i in range(h)]+['#'*(w+1)]
Rows = []
Columns = []
for i in range(h):
    Row = []
    row = 0
    for j in range(w+1):
        if S[i][j] == '.':
            row += 1
        else:
            if row > 0:
                Row += [row]
            row = 0
            Row += [row]
    Rows += [Row]
for j in range(w):
    Column = []
    column = 0
    for i in range(h+1):
        if S[i][j] == '.':
            column += 1
        else:
            if column > 0:
                Column += [column]
            column = 0
            Column += [column]
    Columns += [Column]
mRows = []
mColumns = []
for i in range(h):
  mRow= []
  for j in range(len(Rows[i])):
    mRow += [Rows[i][j]]*max(1,Rows[i][j])
  mRows += [mRow]
for i in range(w):
  mColumn= []
  for j in range(len(Columns[i])):
    mColumn += [Columns[i][j]]*max(1,Columns[i][j])
  mColumns += [mColumn]
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,mRows[i][j]+mColumns[j][i]-1)
print(ans)

Measured memory_bytes: 189316