akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define INF (1<<29)

int N,M;

int bfs(int s,int g){
  queue<int> Q;
  Q.push(s);
  int d[1<<N];
  fill(d,d+(1<<N),INF);
  d[s] = 0;

  while(!Q.empty()){
    int S = Q.front(); Q.pop();
    if(S == g){ return d[S]; }
    for(int i = 0 ; i < N-1 ; i++){
      int nS = S;
      if(((S >> i) & 1) ^ ((S >> (i+1)) & 1)){
        nS ^= 1<<i; nS ^= 1<<(i+1);
        if(d[S] + 1 < d[nS]){
          d[nS] = d[S] + 1;
          Q.push(nS);
        }
      }
    }
  }
  return INF;
}

int main(){
  int in,s,g1,g2,sum;
  s = g1 = g2 = sum = 0;
  cin >> N >> M;
  for(int i = 0 ; i < N ; i++){
    cin >> in;
    s += (in ? (1<<i) : 0);
  }
  for(int i = 0 ; i < M ; i++){
    cin >> in;
    for(int j = 0 ; j < in ; j++){
      g1 += (i % 2 ? 1<<(sum+j) : 0);
    }
    for(int j = 0 ; j < in ; j++){
      g2 += (i % 2 ? 0 : 1<<(sum+j)); 
    }
    sum += in;
  }
  cout << min(bfs(s,g1),bfs(s,g2)) << endl;
  return 0;
}

Measured memory_bytes: 1348
import scala.io.StdIn
object Main extends App {
  val A = StdIn.readLine().toInt
  val B = StdIn.readLine().toInt
  val C = StdIn.readLine().toInt
  val X = StdIn.readLine().toInt

  val answer = for {
    a <- 0 to A
    b <- 0 to B
    c <- 0 to C
    if (500 * a + 100 * b + 50 * c == X)
  } yield (a, b, c)
  println(answer.length)
}


Measured memory_bytes: 27612
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		 StringTokenizer st = new StringTokenizer(br.readLine());
		 int n = Integer.parseInt(st.nextToken());
		 int x = Integer.parseInt(st.nextToken());
		 int t = Integer.parseInt(st.nextToken());
	        
	        int ans=0;
	        while(n>0) {
	        	ans+=t;
	        	n=n>=x?n-x:0;
	        }
	        System.out.println(ans);
	        
	}

}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define rep(i,N) for(int i=0;i<N;i++)

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

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

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

  ll N,M;
  cin>>N>>M;
  vector<ll>a(N);
  for(int i=0;i<N;i++)cin>>a[i];
  for(int i=0;i<N;i++)a[i]/=2;
  while(true){
    bool ok=true;
    for(int i=0;i<N;i++)if(a[i]%2==1)ok=false;
    if(ok){
      for(int i=0;i<N;i++)a[i]/=2;
      M/=2;
    }
    else break;
  }
  for(auto it:a){
    if(it%2==0){
      cout<<0<<endl;
      return 0;
    }
  }
  ll LCM=1;
  for(int i=0;i<N;i++){
    LCM=lcm(LCM,a[i]);
    if(LCM>M){
      cout<<0<<endl;
      return 0;
    }
  }
  cout<<(M/LCM+1)/2<<endl;
  return 0;
}


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

int main() {
  string s; cin >> s;
  if(s=="Sunny"){
    cout << "Cloudy" << endl;
  }
  else if(s=="Cloudy"){
    cout << "Rainy" << endl;
  }
  else{
    cout << "Sunny" << endl;
  }
}

Measured memory_bytes: 256
import glob



# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\AGC\\C'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'


class Common:
    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index - 1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class C(Common):

    def resolve(self):

        ring_len = int(self.input_data())
        first_ring = [int(i) for i in self.input_data().split()]
        now_ring = [int(i) for i in self.input_data().split()]

        count = 0
        result = True
        loop = True


        while loop:

            result = True
            loop = False
            i = 0

            while i < ring_len:
                if first_ring[i] == now_ring[i]:
                    i += 1
                    continue

                result = False

                if first_ring[i] > now_ring[i]:
                    break
                if i != 0:
                    prv = i - 1
                else:
                    prv = ring_len - 1

                if i != ring_len - 1:
                    nxt = i + 1
                else:
                    nxt = 0

                if now_ring[i] > now_ring[prv] + now_ring[nxt]:
                    loop = True
                    tmp = int((now_ring[i] - first_ring[i]) / (now_ring[prv] + now_ring[nxt]))
                    if tmp == 0:
                        loop = False
                        break
                    loop = True
                    now_ring[i] -= (now_ring[prv] + now_ring[nxt])*tmp
                    count += tmp
                    i = i - 2
                    if i < -1 :
                        i += ring_len

                i += 1

            if result:
                loop = False

        if result:
            print(str(count))
        else:
            print("-1")


solver = C(REL_PATH)
solver.exec_resolve()

Measured memory_bytes: 34644
from itertools import combinations
n,m,x = map(int,input().split())
t = [list(map(int,input().split())) for i in range(n)]

ans = -1
for i in range(n+1):
    for comb in combinations(range(n),i):
        a = [0 for _ in [0]*m]
        c = 0
        for j in comb:
            temp = t[j]
            c += temp[0]
            for k in range(m):
                a[k] += temp[k+1]
        flag = True
        for j in a:
            if j<x:
                flag = False
                break
        if flag:
            if ans==-1:
                ans = c 
            else:
                ans = min(ans,c)

print(ans)

Measured memory_bytes: 9224
#include <bits/stdc++.h>
   
using namespace std;
#define ll long long
#define ld long double
#define pll pair<long long,long long>
#define vll vector<long long>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define deb(x) cout << #x << "=" << x << endl
#define F(i,a,b) for(ll i=a;i<=b;i++)
#define RF(i,a,b) for(ll i=a;i>=b;i--)
#define in(a,n) F(i,0,n-1)cin>>a[i]
#define vi vector<int>
#define out(a,n) F(i,0,n-1)cout<<a[i]<<" ";cout<<endl
#define mod 1000000007
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define int long long
const int N=1e5+5;



void solve()
{
    double d,t,s;
    cin>>d>>t>>s;
    
    double c=(double)(d*1.0)/(s*1.0);
  //  cout<<fixed<<setprecision(15)<<c<<'\n';
    
    if(c<=t)
    {
        cout<<"Yes";
    }
    else cout<<"No";
}

int32_t main()
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    
	int t=1;
//	cin>>t;
	while(t--)solve();
	    
  
}




Measured memory_bytes: 3732
#include<iostream>
#include<map>
#include<algorithm>
#include<numeric>

using namespace std;

map<unsigned,int> m;

long long N,Q,A,B,C,D,E,F,G;
vector<int> rx,cx;
bool cr=false,rr=false;
bool t=false;

int ay(int y){
  if(rr){
    y=N+1-y;
  }
  return y;
}

int ax(int x){
  if(cr){
    x=N+1-x;
  }
  return x;
}

int &org(int y,int x){
  int oy=rx[ay(y)];
  int ox=cx[ax(x)];
  if(t){
    swap(oy,ox);
  }
  unsigned mx=(oy*1u<<16)+ox;
  if(!m.count(mx)){
    m[mx]=(oy*A+ox*B)%C;
  }
  return m[mx];
}

int main(){
  cin>>N>>Q>>A>>B>>C>>D>>E>>F>>G;
  rx.resize(N+1);
  cx.resize(N+1);
  iota(begin(rx),end(rx),0);
  iota(begin(cx),end(cx),0);
  while(Q--){
    char op[9];
    cin>>op;
    if(op[0]=='W'){
      int r,c,v;
      cin>>r>>c>>v;
      org(r,c)=v;
    }else if(op[0]=='C'){
      int r1,c1,r2,c2;
      cin>>r1>>c1>>r2>>c2;
      org(r2,c2)=org(r1,c1);
    }else if(op[0]=='S'){
      int rc1,rc2;
      cin>>rc1>>rc2;
      if(op[1]=='R'){
	swap(rx[ay(rc1)],rx[ay(rc2)]);
      }else{
	swap(cx[ax(rc1)],cx[ax(rc2)]);
      }
    }else{
      if(op[1]=='R'){
	swap(rx,cx);
	swap(rr,cr);
	cr^=true;
	t^=true;
      }else if(op[1]=='L'){
	swap(rx,cx);
	swap(rr,cr);
	rr^=true;
	t^=true;
      }else if(op[1]=='H'){
	rr^=true;
      }else{
	cr^=true;
      }
    }
  }
  long long h=314159265;
  for(int i=D;i<=E;i++){
    for(int j=F;j<=G;j++){
      h=(31*h+org(i,j))%1000000007;
    }
  }
  cout<<h<<endl;
}

    
    

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

typedef long long ll;

int main() {
  int N;
  double T,A;
  cin >> N >> T >> A;
  vector<int> H(N);
  for(int i=0; i<N; i++) cin >> H[i];

  vector<pair<double,int> > p;
  for(int i=0; i<N; i++){
    p.push_back(make_pair(T-0.006*H[i],i+1));
  }

  double mi=1e9;
  int point;
  for(int i=0; i<p.size(); i++){
    if(mi>abs(A-p[i].first)){
      mi = abs(A-p[i].first);
      point = p[i].second;
    }
  }

  cout << point << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <iterator>
#include <cmath>
#include <set>
#include <deque> 
#include <string>


using namespace std;

int n;
int a[200010];
int digits[200010];
std::vector<int> ans;

void doAddDigits(int num)
{
	int dd = 1;
	while ((dd * dd) <= num)
	{
		if (num % dd != 0)
		{
			dd++;
			continue;			
		}
		
		int rd = num / dd;
		digits[dd]++;
		if (rd != dd)
			digits[rd]++;
		
		dd++;
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1 ; i <= n ; i++)
		scanf("%d", &(a[i]));
		
//	for (int i = 1 ; i <= n ; i++)
//	{
//		if ((i % 2 == 0) && (a[i] % 2 != 0))
//		{
//			printf("-1\n");
//			return 0;
//		}
//	}
	
	int curNum = 0;
	ans.clear();
	
	for (int i = n ; i >= 1 ; i--)
	{
//		if (i % 2 == 0)
//			continue;
			
		if (digits[i] % 2 == a[i])
			continue;
			
		//
		ans.push_back(i);
		doAddDigits(i);
	}	
	
	printf("%d\n", ans.size());
	
	for (int i = 0 ; i < ans.size() ; i++)
		printf("%d ", ans[i]);
	printf("\n");

	return 0;
}
	

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph emplace
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n; const ll MOD=1e9+7;
ll dp[106][5][5][5][5];
ll sum=0;
// A,C,G,T
ll dpdp(ll pos, ll a, ll b, ll c, ll d){
	if(b==0&&c==1&&d==2)return 0;
	if(b==0&&c==2&&d==1)return 0;
	if(b==1&&c==0&&d==2)return 0;
	if(a==0&&c==1&&d==2)return 0;
	if(a==0&&b==1&&d==2)return 0;
	// cerr<<a<<' '<<b<<' '<<c<<' '<<++sum<<'\n';
	if(pos==n)return 1;
	if(~dp[pos][a][b][c][d])return dp[pos][a][b][c][d];
	dp[pos][a][b][c][d]=0;
	FOR(i,0,4){
		dp[pos][a][b][c][d]+=dpdp(pos+1,b,c,d,i);dp[pos][a][b][c][d]%=MOD;
	}
	return dp[pos][a][b][c][d];
}
int main()
{
	cin>>n;
	mmst(dp,-1);
	cout<<dpdp(0,4,4,4,4)<<'\n';
}


Measured memory_bytes: 768
/*
    In the name of
        "ALLAH"
    And say "AL-HAMD-U-LILLAH"
*/

#include<bits/stdc++.h>
#define ll long long
#define llu unsigned long long
#define _  printf("\n")
int take() {
    int n;
    scanf("%d",&n);
    return n;

}
double ttake() {
    double n;
    scanf("%lf",&n);
    return n;
}
ll takes() {
    ll n;
    scanf("%lld",&n);
    return n;

}

#define Int take()
#define Dnt ttake()
#define LL takes()
#define done {return 0;}
#define fr(i,x,n,a) for(int i=x;i<=n;i+=a)
#define FR(a,b,x) for(int i=(a);i<=(b);i+=(x))
#define rfr(i,x,n,a) for(int i=x;i>=n;i--)
int cas;
#define print printf("Case %d:",++cas)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define pii pair<int,int>
#define vii vector<pii>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mk  make_pair
#define fill(x,v) memset(x,v,sizeof x)

using namespace std;

bool approximatelyEqual(float a, float b, float epsilon) {
    return fabs(a - b) <= ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool essentiallyEqual(float a, float b, float epsilon) {
    return fabs(a - b) <= ( (fabs(a) > fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyGreaterThan(float a, float b, float epsilon) {
    return (a - b) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}

bool definitelyLessThan(float a, float b, float epsilon) {
    return (b - a) > ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
}
#define STR {struct info}
#define dbg(x) {cout<<"ekhane"<<x<<endl;}
#define  SS second
#define  FF first
#define PQ priority_queue
#define great greatest
#define less lesser
#define mii map<int,int>
#define mil map<int,ll>
#define mll map<ll,ll>
#define msb map<string,bool>
#define V vector
#define M 100005
#define pf printf
//////////////////////////////////////////


int main(){

   int a = Int , b = Int , k = Int ;
   set<int>s1 ;
   fr( i , a , a + k -1 , 1 ){
    s1.insert(i ) ;
   }
    rfr( i , b , b - k + 1 , 1 ){
        s1.insert(i) ;
    }
    for(auto x :s1 ){
        if( x >= a && x <= b )
        pf("%d\n",x) ;
    }
    done;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<set>
#define ll long long 
#include <string>
#define pb push_back
#define mp make_pair
using namespace std;

int main()
{
	ll int n;
	cin>>n;
	ll int d=n%10;
	if (d==2 || d==4 || d==5 ||d==7 || d==9)
	cout<<"hon"<<endl;
	else if (d==3)
	cout<<"bon"<<endl;
	else
	cout<<"pon"<<endl;

	
			
}



Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int c[3][3];
	int i, j;
	for (i = 0;i < 3;i++) {
		for (j = 0;j < 3;j++) {
			cin >> c[i][j];
		}
	}
	int a[3], b[3];
	int T = 0;
	for (i = 0;i <= c[0][0];i++) {
		a[0] = i;
		b[0] = c[0][0]-i;
		a[1] = c[1][0] - b[0];
		a[2] = c[2][0] - b[0];
		b[1] = c[0][1] - a[0];
		b[2] = c[0][2] - a[0];
		int k;
		int t = 1;
		for (j = 1;j < 3;j++) {
			int l=1;
			for (k = 1;k < 3;k++) {
				if (a[j] + b[k] != c[j][k]) break;
				else l++;
			}
			if (l < 3) break;
			else if(j==2) T = 1;
		}
		if (T == 1) break;
	}
	if (T == 1) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
//A
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	string s;
	cin >> s;
	int a = s[s.size()-1]-'0';
	if(a == 3)cout << "bon";
	else{
		if(!a or a == 1 or a == 6 or a == 8)cout << "pon";
		else cout << "hon";
	}
	return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

#define MAX 30
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

Node T[MAX];
int n, D[MAX], H[MAX];

void rec(int u, int d) {
    D[u] = d;
    if ( T[u].left != NIL ) rec(T[u].left, d + 1);
    if ( T[u].right != NIL ) rec(T[u].right, d + 1);
}

int set(int u) {
    int h1 = 0, h2 = 0;
    if ( T[u].right != NIL ) {
        h1 = set(T[u].right) + 1;
    }
    if ( T[u].left != NIL ) {
        h2 = set(T[u].left) + 1;
    }
    
    return H[u] = max(h1, h2);
}


void print(int u) {
    printf("node %d: parent = %d, sibling = ", u, T[u].parent);
    
    int p = T[u].parent;
    if ( p == NIL ) {
        printf("-1, ");
    } else if ( T[p].left != NIL && T[p].left != u ) {
        printf("%d, ", T[p].left);
    } else if ( T[p].right != NIL && T[p].right != u ) {
        printf("%d, ", T[p].right);
    } else {
        printf("-1, ");
    }

    printf("degree = ");
    if ( T[u].left != NIL && T[u].right != NIL ) {
        printf("2, ");
    } else if ( T[u].left == NIL && T[u].right == NIL ) {
        printf("0, ");
    } else {
        printf("1, ");
    }
    
    printf("depth = %d, height = %d, ", D[u], H[u]);
    
    if ( p == NIL ) {
        printf("root\n");
    } else if ( T[u].left != NIL || T[u].right != NIL ) {
        printf("internal node\n");
    } else {
        printf("leaf\n");
    }
}

int main() {
    cin >> n;
    
    for ( int i = 0; i < n; i++ ) {
        T[i].parent = T[i].left = T[i].right = NIL;
    }
    
    for ( int i = 0; i < n; i++ ) {
        int id, l, r;
        cin >> id >> l >> r;
        T[id].left = l;
        T[id].right = r;
        if ( l != NIL ) T[l].parent = id;
        if ( r != NIL ) T[r].parent = id;
    }
    
    int root = 0;
    for ( int i = 0; i < n; i++ ) {
        if ( T[i].parent == NIL ) root = i;
    }
    
    set(root);
    rec(root, 0);
    
    for ( int i = 0; i < n; i++ ) {
        print(i);
    }
    
    return 0;
}

Measured memory_bytes: 3208
# https://atcoder.jp/contests/abc088/tasks/abc088_c

matrix = []

for _ in range(3):
    row = [int(i) for i in input().split()]
    matrix.append(row)

a1 = matrix[1][0] - matrix[0][0]
a2 = matrix[2][0] - matrix[0][0]
b1 = matrix[0][1] - matrix[0][0]
b2 = matrix[0][2] - matrix[0][0]

if a1 + b1 == matrix[1][1] - matrix[0][0] and a2 + b2 == matrix[2][2] - matrix[0][0] and a1 + b2 == matrix[1][2] - matrix[0][0] and a2 + b1 == matrix[2][1] - matrix[0][0]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38256
# coding: utf-8

"""
20191120
93分
test:
6 8
2 3
1 2
3 6
2 1
1 3
5 85
"""


def main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())
    V = sum(vs)

    # initialize
    dp = [[None for _ in range(V+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    dp[0][vs[0]] = ws[0]
    existance[0].add(vs[0])

    for n in range(N-1):
        for v in existance[n]:
            # not-use-update
            if dp[n+1][v] is None:
                dp[n+1][v] = dp[n][v]
            else:
                dp[n+1][v] = min(dp[n][v], dp[n+1][v])
            existance[n+1].add(v)

            # use-update
            if dp[n+1][v+vs[n+1]] is None:
                if dp[n][v] + ws[n+1] <= W:
                    dp[n+1][v+vs[n+1]] = dp[n][v] + ws[n+1]
                    existance[n+1].add(v+vs[n+1])
            else:
                dp[n+1][v+vs[n+1]] = min(dp[n][v] + ws[n+1], dp[n+1][v+vs[n+1]])
                # existance[n+1].add(v+vs[n+1])

    ans = 0
    for v in range(V, 0, -1):
        if dp[-1][v] is not None:
            ans = v
            break

    return ans


def miss_main():
    N, W = map(int, input().split())
    ws = [None for _ in range(N)]
    vs = [None for _ in range(N)]
    for i in range(N):
        ws[i], vs[i] = map(int, input().split())

    # initialize
    dp = [[None for _ in range(W+1)] for _ in range(N)]
    dp[0][0] = 0
    existance = [set([]) for _ in range(N)]
    existance[0].add(0)
    if W >= ws[0]:
        dp[0][ws[0]] = vs[0]
        existance[0].add(ws[0])

    for n in range(N-1):
        for w in existance[n]:
            # not-use-update
            if dp[n+1][w] is None:
                dp[n+1][w] = dp[n][w]
            else:
                dp[n+1][w] = max(dp[n][w], dp[n+1][w])
            existance[n+1].add(w)

            # use-update
            if w + ws[n+1] <= W:
                if dp[n+1][w+ws[n+1]] is None:
                    dp[n+1][w+ws[n+1]] = dp[n][w] + vs[n+1]
                else:
                    dp[n+1][w+ws[n+1]] = max(dp[n][w] + vs[n+1], dp[n+1][w+ws[n+1]])
                existance[n+1].add(w+ws[n+1])
    # print(np.array(dp))

    ans = 0
    for w in range(1, W+1):
        if dp[-1][w] is not None and dp[-1][w] > ans:
            ans = dp[-1][w]

    return ans


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 270088
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}





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


  ll N ; cin >> N;

  ll up = N ;
  ll down = 0;
  while(N!=0){
    down += (N%10);
    N/=10;
  }
  if(up%down == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  //cout << fixed << setprecision(16) << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
arr = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(arr[k-1])

Measured memory_bytes: 61816
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(1,n-1):
    if (p[i-1]<p[i] and p[i]<=p[i+1]) or (p[i-1]>=p[i] and p[i]>p[i+1]):
        ans+=1
print(ans)

Measured memory_bytes: 3060
A, B, C, X, Y = map(int, input().split())
all = X*A + Y*B
all_ab = 2 * C * max(X, Y)
m = min(X, Y)
almost_ab = 2 * C * m + A * (X - m) + B * (Y - m)
print(min(all, all_ab, almost_ab))

Measured memory_bytes: 3060
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  ll d,n=26;
  cin >> d;
  vector<ll> c(n),contest(d);
  vector<vector<ll>> s(d,vector<ll>(n));
  for(int i=0;i<n;i++){
    cin >> c[i];
  }
  for(int i=0;i<d;i++){
    for(int j=0;j<n;j++){
      cin >> s[i][j];
    }
  }
  for(int i=0;i<d;i++){
    ll b_score = -1e9,b_c=0;
    for(int j=0;j<n;j++){
      ll tmp = s[i][j];
      for(int k=0;k<n;k++){
        if(j==k) continue;
        ll last = 0;
        for(int l=i-1;l>=0;l--){
          if(contest[l]==k){
            last = l+1;
            break;
          }
        }
        tmp -= c[k]*(i+1-last);
      }
      if(tmp>b_score){
        b_score = tmp;
        b_c = j;
      }
    }
    contest[i] = b_c;
  }
  for(int i=0;i<d;i++){
    cout << contest[i]+1 << endl;
  }
}


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

using namespace std;

int main(){
	string s; cin >> s;
	vector<char> buf;
	for(int i = 0; i < s.size(); ++i){
		if(s[i] == '0') buf.push_back('0');
		else if(s[i] == '1') buf.push_back('1');
		else if(buf.size()) buf.pop_back();
	}
	for(int i = 0; i < buf.size(); ++i) cout << buf[i];
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,cnt,ans;
    int a[100010];
    cin>>n;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);ans=cnt=0;
    for(i=1;i<=n;i++)
    {
        cnt++;
        if (i==n || a[i]!=a[i+1])
        {
            if (cnt & 1) ans++;
            cnt=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop, heapify
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M = MI()
    A = LI()
    for i,a in enumerate( A):
        A[i] = - a

    heapify(A)
    for _ in range(M):
        a = heappop(A)
        heappush(A,a/2)
    
    ans = 0
    for h in A:
        ans += int(-h)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 93036
#![allow(unused_imports)]
#![allow(dead_code)]

macro_rules! input_byline {
    ($($r:tt)* ) => {
        let stdin = std::io::stdin();
        let mut q = std::collections::VecDeque::new();
        let mut next = || {
            if q.is_empty() {
                let mut s = String::new();
                let _ = stdin.read_line(&mut s);
                for v in s.split_whitespace() {
                    q.push_back(v.to_string());
                }
            }
            q.pop_front().unwrap()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };
    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::{max, min};
use std::collections::{BinaryHeap, HashMap};
 
type Graph = Vec<Vec<usize>>;
const M: usize = 1e9 as usize + 9;

fn main() {
    input_byline! {
        n: usize,
    }
 
    let mut v = vec![vec![]; n];
    for i in 0..n {
        input_byline! {
            a: usize,
        }
        for j in 0..a {
            input_byline! {
                x: usize1,
                y: usize,
            }
            v[i].push((x, y));
        }
    }
 
    let mut ans = 0;
    for i in 0..1 << n {
        let mut ok = true;
        for j in 0..n {
            if (i >> j) & 1 == 0 {
                continue;
            }
            for k in 0..v[j].len() {
                if (i >> v[j][k].0) & 1 != v[j][k].1 {
                    ok = false
                }
            }
        }
        if ok {
            ans = max(ans, (i as u32).count_ones());
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
int main(){
	int n,k;
	for(;scanf("%d%d",&n,&k),n;){
		int r=0,i=1;
		for(;i<n;i++)r=(r+k)%i;
		printf("%d\n",(r+1+k-1)%n+1);
	}
	return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;
const int INF = 1001001001;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  ll maxv = a[0];
  ll ans = 0;

  rep(i, n) {
    if (maxv > a[i]) {
      ans += maxv - a[i];
    } else {
      maxv = a[i];
    }
  }

  cout << ans << endl;

}

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

void bubbleSort(int A[], int N){
  int flag, t, change_num = 0;

  flag = 1;
  for(; flag;){
    flag = 0;
    for(int j = N-1; j > 0; j--){
      if (A[j] < A[j-1]){
        /*/
        t = A[j];
        A[j] = A[j-1];
        A[j-1] = t;
        /*/
        swap(A[j],A[j-1]);
        flag = 1;
        change_num += 1;
      }
    }
  }
  for(int i = 0; i < N; i++){
    if(i == N-1) cout << A[i] << endl;
    else cout << A[i] << " ";
    }
  cout << change_num << endl;
}

int main(){
  int N,A[100];
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  bubbleSort(A, N);

  return 0;
}

Measured memory_bytes: 3060
#include <iostream>
#define ll long long int
using namespace std;

int main(int argc, char const* argv[])
{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int x = 0;
		if(a - b <= d && b - a <= d)x++;
		if(b - c <= d && c - b <= d)x++;
  		if(a - c <= d && c - a <= d)x = 2;
		if(x == 2)cout << "Yes" << endl;
		else cout << "No" << endl;
	
	return 0;
}



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

using namespace std;
int i,j,make[100],kati[100];
char name[100];

void change(){
  int tmp1,tmp2;
  char tmp3;
  tmp1 = kati[j+1];
  kati[j+1] = kati[j];
  kati[j] = tmp1;
  
  tmp2 = make[j+1];
  make[j+1] = make[j];
  make[j] = tmp2;
  
  tmp3 = name[j+1];
  name[j+1] = name[j];
  name[j] = tmp3;
}

int main(){
  int n,s;
  while(1){
    cin >> n;
    if( n == 0 )break;
    for( i = 0;i < 100 ; i++){
      kati[i] = 0;
      make[i] = 0;
    }
    
    for( i = 0 ; i < n ; i++ ){
	cin >> name[i];
      for( j = 0; j < n-1 ; j++ ){
	cin >> s;
	if(s == 0)kati[i]++;
	if(s == 1)make[i]++;
      }
    }

    
    
    for( i = n-1;i >0 ; i--){
      for( j = 0; j < i ; j++){
	if(make[j] > make[j+1] ){
	  change();
	}
      }
    }
    
    for( i = n-1;i >0 ; i--){
      for( j = 0; j < i ; j++){
	if(kati[j] < kati[j+1] ){
	  change();
	}
      }
    }

    for(i = 0;i < n ;i++)cout << name[i] << endl;
    
  }
  return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <queue>

using namespace std;

namespace {

struct State {
  int top;
  int bottom;
  int front;
  int back;
  int left;
  int right;

  void Init() {
    top = 1;
    bottom = 6;
    front = 2;
    back = 5;
    left = 4;
    right = 3;
  }
};

State Next(const State& s, char c) {
  State o;
  int temp = 0;
  switch (c) {
    case 'S':
      temp = s.front;
      o.front = s.top;
      o.top = s.back;
      o.back = s.bottom;
      o.bottom = temp;
      o.left = s.left;
      o.right = s.right;
      break;
    case 'N':
      temp = s.back;
      o.back = s.top;
      o.top = s.front;
      o.front = s.bottom;
      o.bottom = temp;
      o.left = s.left;
      o.right = s.right;
      break;
    case 'E':
      temp = s.right;
      o.right = s.top;
      o.top = s.left;
      o.left = s.bottom;
      o.bottom = temp;
      o.front = s.front;
      o.back = s.back;
      break;
    case 'W':
      temp = s.left;
      o.left = s.top;
      o.top = s.right;
      o.right = s.bottom;
      o.bottom = temp;
      o.front = s.front;
      o.back = s.back;
      break;
  }
  return o;
}

int BFS(const int* values, int top, int front) {
  State start;
  start.Init();
  queue<State> q;
  q.push(start);
  const char dirs[4] = {'S', 'N', 'E', 'W'};

  while (!q.empty()) {
    const State p = q.front();
    q.pop();

    if (values[p.top - 1] == top && values[p.front - 1] == front) {
      return values[p.right - 1];
    }
    for (size_t i = 0; i < 4; ++i) {
      State o = Next(p, dirs[i]);
      q.push(o);
    }
  }
  // not found
  return -1;
}

} // namespace

int main() {
  int values[6];
  for (int i = 0; i < 6; ++i) {
    cin >> values[i];
  }
  int q;
  cin >> q;
  int top, front;
  for (int i = 0; i < q; ++i) {
    cin >> top >> front;
    cout << BFS(values, top, front) << endl;
  }
  return 0;
}

Measured memory_bytes: 1224
#include<iostream>

using namespace std;

void max(int n, int a[], int b[]){
    int First, Second;
    if(a[0] >= a[1]) First = a[0], Second = a[1];
    else First = a[1], Second = a[0];
    for(int i = 2; i < n; i++){
        if(First < a[i]) First = a[i];
        else if(Second < a[i]) Second = a[i];
    }
    b[0] = First, b[1] = Second;
}

int main(){
    int n, a[200000], b[2];
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    max(n, a, b);
    for(int i = 0; i < n; i++){
        if(a[i] == b[0]) cout << b[1] << endl;
        else cout << b[0] << endl;
    }
    return 0;
}

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

lent = len(T)
ans = lent
for i in range(len(S)-lent+1):
    s = S[i:i+lent]
    lev = 0
    lev = sum(map(lambda x: x[0] != x[1], zip(s, T)))
    if lev == 0:
        ans = 0
        break
    elif lev < ans:
        ans = lev
print(ans)


Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
using pp=pair<int,int>;
using ll=long long;

int main() {
  ll N,X,M, shuuki=0, start=0, shuu=0;
  cin >> N >> X >> M;
  vector<ll> V(0);
  set<ll> ss;
  ll A=X, B;
  V.push_back(A);
  ss.insert(A);
  for (ll i=2; i<M+30; i++) {
    //cout << A << endl;
    B=A*A;
    B=B-B/M*M;
    ss.insert(B);
    if (ss.size()!=i) {
      for (ll j=0; j<V.size(); j++) {
        if (V[j]==B) {
          start=j;
          shuuki=V.size()-j;
          shuu=1;
          //cout << shuuki << endl;
        }
      }
      break;
    }
    V.push_back(B);
    A=B;
    if (V.size()==N) {
      shuu=0;
      break;
    }
  }
  if (shuu==1) {
    ll S=0, SS=0;
    for (ll i=0; i<start; i++) {
      SS+=V[i];
    }
    for (ll i=start; i<V.size(); i++) {
      S+=V[i];
    }
    N-=start;
    ll a=N/shuuki;
    ll b=N-N/shuuki*shuuki;
    ll s=0;
    for (ll i=start; i<b+start; i++) {
      s+=V[i];
    }
    cout << SS+s+S*a << endl;
    //cout << a << endl;
  }
  else {
    ll SSS=0;
    for (ll i=0; i<V.size(); i++) {
      SSS+=V[i];
    }
    cout << SSS << endl;
  }
}

Measured memory_bytes: 5940
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int[] stack = new int[100];
		int sp = 0;
		while(scan.hasNext()){
			String str = scan.next();
			if(str.equals("+")){
				int a = stack[--sp];
				int b = stack[--sp];
				stack[sp++] = a + b;
			}else if(str.equals("-")){
				int a = stack[--sp];
				int b = stack[--sp];
				stack[sp++] = b - a;
			}else if(str.equals("*")){
				int a = stack[--sp];
				int b = stack[--sp];
				stack[sp++] = a * b;
			}else{
				stack[sp++] = Integer.parseInt(str);
			}
		}
		for(int i = 0;i < sp;i++){
			System.out.println(stack[i]);
		}
	}
}

Measured memory_bytes: 18740
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main()
{
int n;
cin>>n;
vector<string> s(n);
bool ans=false;
REP(i,n)
{
    cin>>s[i];
    if(s[i]=="Y") ans=true;
}
if(ans) cout<<"Four"<<endl;
else cout<<"Three"<<endl;
}

Measured memory_bytes: 256
import itertools
S = input()
op = ['+','']
length = len(S) -1
ans = 0

for o in itertools.product(op, repeat=length):
	exp = ""
	for i in range(length):
		exp += S[i]+o[i]
	exp += S[length]
	ans += eval(exp)

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],p[N];
bool prime(int x)
{
	if(x==2)return true;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)return false;
	}
	return true;
}
int main()
{
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);

	int n;
	cin>>n;
while(!prime(n))n++;
	cout<<n;
return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

string s;
ll now = 0, dp[510000], ans;

int main() {
	REP(i, 510000)dp[i] = -1;
	cin >> s;
	ll n = s.size();
	vector<P> t;
	REP(i, n + 1) {
		t.push_back(P(now, i + 1));
		if (i != n) {
			if (s[i] == '<')now++;
			else now--;
		}
	}
	sort(ALL(t));
	REP(i, t.size()) {
		dp[t[i].second] = max(dp[t[i].second - 1], dp[t[i].second + 1]) + 1;
	}
	REPO(i, n + 1) {
		ans += dp[i];
	//	cout << dp[i] << " ";
	}
	//cout << endl;
	cout << ans << endl;
}


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

using namespace std;

#define int long long
typedef vector<int> vint;
typedef pair<int, int> pint;
const double PI = 3.14159265358979323846;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed

int pow2[110000], pow3[110000];

int mod_pow(int n, int m) {
    pow2[0] = pow3[0] = 1;
    for (int i = 1; i <= n; i++)pow2[i] = pow2[i - 1] * 2 % m, pow3[i] = pow3[i - 1] * 3 % m;
}

string L;
int mod = 1e9 + 7;

signed main() {
    cin >> L;
    mod_pow(L.length() + 10, mod);
    int ans = 0, one = 0;
    for (int i = 0; i < L.length(); i++) {
        if (L[i] == '1') {
            (ans += pow2[one] * pow3[L.length() - i - 1] % mod) %= mod;
            one++;
        }
    }

    (ans += pow2[one]) %= mod;
    cout << ans << endl;
}

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

vector<int> A,B;
map<tuple<int,int,int,int,bool,int>,int > dp;
int N,M;

//-1が連続しているときに対応できてない気がする

//aのindex, bのindex, スタックに積まれたaのsum, スタックに積まれたbのsum, Aのターンか, 何回パスしたか
int dfs(int a, int b, int a_sum, int b_sum, bool aturn, int passed){
		if( dp.count(make_tuple(a,b,a_sum,b_sum,aturn,passed)) ){
				return dp[make_tuple(a,b,a_sum,b_sum,aturn,passed)];
		}

		//passed==2になった時点でゲーム終了(連続して二人がパスする)

		//現在のターンの者はpassするか, カードをスタックに積むか選べる
		int passed_score = 0, piled_score = 0;


		if(aturn){
				if(passed == 2){
						//ゲーム終了するか取るか選べる
						passed_score = 0;

				}else{
						//パスした場合
						passed_score = dfs(a,b,0,0,false,passed+1) + (a_sum-b_sum);
				}
				//スタックに積んだ場合
				if(a<N){
						if(A[a]==-1){
								piled_score = dfs(a+1, b, a_sum, 0, false, 0);
						}else{
								piled_score = dfs(a+1, b, a_sum+A[a], b_sum, false, 0);
						}
				}else{//a==Nのとき、パスしかできねえ
						piled_score = passed_score;
				}


		}else{
				if(passed == 2){
						//ゲーム終了するか取るか選べる
						passed_score = 0;
				}else{
						//パスした場合
						passed_score = dfs(a,b,0,0,true,passed+1) + (a_sum-b_sum);
				}
				//スタックに積んだ場合
				if(b<M){
						if(B[b]==-1){
								piled_score = dfs(a, b+1, 0, b_sum, true, 0);
						}else{
								piled_score = dfs(a, b+1, a_sum, b_sum+B[b], true, 0);
						}
				}else{//b==Mのとき、パスしかできねえ
							piled_score = passed_score;
				}

		}
		//cout << passed_score << " " << piled_score << endl;
		if(aturn) return dp[make_tuple(a,b,a_sum,b_sum,aturn,passed)] = max(passed_score, piled_score);
		else return dp[make_tuple(a,b,a_sum,b_sum,aturn,passed)] = min(passed_score, piled_score);
}

signed
main(){
		cin >> N >> M;
		A = vector<int>(N);
		B = vector<int>(M);

		for(int i=0;i<N;i++)
				cin >> A[i];
		for(int i=0;i<M;i++)
				cin >> B[i];

		cout << dfs(0, 0, 0, 0, true, 0) << endl;

}


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

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    vint v(n,0);
    vint sum(n+1);
    sum[0]=0;
    REP(i,n){
        cin >> v[i];
        sum[i+1]=sum[i]+v[i];
    }
    int ans = 0;
    for(int i=0;i<=k;i++){
        for(int kl=0;kl<=i;kl++){
            for(int kr=0;kr+kl<=i;kr++){
                int ki = i-kr-kl;
                int tmp=0;
                if(kr+kl>=n){
                    priority_queue<int,vector<int>, greater<int>> me;
                    REP(t,n){
                        me.push(v[t]);
                    }
                    REP(t,ki){
                        if(me.empty())break;
                        tmp+=me.top();
                        me.pop();                        
                    }
                    ans=max(ans,sum[n]-tmp);
                }else{
                    priority_queue<int,vector<int>, greater<int>> me;
                    REP(t,kl){
                        me.push(v[t]);
                    }
                    REP(t,kr){
                        me.push(v[n-1-t]);
                    }
                    tmp = sum[n-kr]-sum[kl];
                     REP(t,ki){
                        if(me.empty())break;
                        tmp+=me.top();
                        me.pop();
                    }
                    ans=max(ans,sum[n]-tmp);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector<int> deg(n, 0);
	for(int i = 0; i < n-1; i++){
		int u, v, a;
		cin >> u >> v >> a;
		deg[u] ^= a;
		deg[v] ^= a;
	}
	int ans = 0;
	int mask = 0;
	for(int x : deg){
		if(x == 0) continue;
		if((mask >> x) & 1) ans += 1;
		mask ^= (1 << x);
	}
	const int B = 4;
	const int F = 1 << B;
	vector<int> dp(1 << F, -1e6);
	vector<bool> ok(1 << F, false);
	for(int i = 0; i < (1 << F); i++){
		int val = 0;
		for(int j = 0; j < F; j++){
			if((i >> j) & 1) val ^= j;
		}
		if(val == 0) ok[i] = true;
	}
	dp[0] = 0;
	for(int j = 0; j < (1 << F); j++){
		int k = j;
		while(k > 0){
			if(ok[k]){
				dp[j] = max(dp[j], dp[j ^ k] + 1);
			}
			k = (k-1) & j;
		}
	}
	cout << (ans + __builtin_popcount(mask) - dp[mask]) << '\n';
}

Measured memory_bytes: 896
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<cstdlib>
#include<list>
#include<set>
#include<numeric>

#define MOD 1000000007

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

char s[1000010];

int main()
{
    cin >> s;

	ll leng = strlen(s);
	ll i = 0;
	ll level = 0;
	while (i < leng) {
		if (s[i] != 'J') {
			i++;
			continue;
		}
		int J = 0, O = 0, I = 0;
		while (i < leng && s[i] == 'J') {
			J++;
			i++;
		}
		while (i < leng && s[i] == 'O') {
			O++;
			i++;
		}
		while (i < leng && s[i] == 'I') {
			I++;
			i++;
		}
		if (O <= J && O <= I)
			level = (level < O ? O : level);
	}
	cout << level << endl;
	return 0;
}

Measured memory_bytes: 4064
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))
#define BUF_SIZE 100
#define DIVISOR 1000000007

int get_int(void) {
  int num;
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return 0;
  sscanf(line, "%d", &num);
#else
#error
#endif
  return num;
}

// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(int *arr, int size) {
#ifdef BUF_SIZE
    char line[BUF_SIZE];
    int i;
    if(!fgets(line, BUF_SIZE, stdin)) return -1;
    char *tmp = strtok(line, " ");
    int k = strtol(tmp, NULL, 10);
    for(i = 0; i < k; i++) {
        char *tmp = strtok(NULL, " ");
        arr[i] = strtol(tmp, NULL, 10);
    }
#else
#error
#endif
    return k;
}

#define NUM_MAX 28
#define K_MAX 18

int main(void) {
    int arr[NUM_MAX+1];
    int num = get_int();
    int k = fget_array(arr, K_MAX+1);
    int i;
    int match = 0;
    for(i = 0; i < k; i++) {
        match |= (1<<arr[i]);
    }
    int pat;
    // see https://kimiyuki.net/blog/2017/07/16/enumerate-sets-with-bit-manipulation/
    for(pat = 0;; pat = (pat-match)&match) {
        printf("%d:", pat);
        for(i = 0; i < num; i++) {
            if(!(pat & (1<<i))) continue;
            printf(" %d", i);
        }
        putchar('\n');
        if(pat == match) break;
    }
    return 0;
}


Measured memory_bytes: 2104