akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define nes ios_base :: sync_with_stdio(0); cin.tie(0);
using namespace std;
bool x=false;
set<int>se;
void ch(int n){
	if(x) return ;
	for(int i=1;i<=(int)sqrt(n);++i){
		if(n%i==0){
			if(i==1){
				if(se.count(n/i)) x=true;
				se.insert(n/i);
			}
			else{
				if(se.count(n/i)) x=true;
				if(se.count(i)) x=true;
				se.insert(i);
				se.insert(n/i);
			}
		}
	}
}
int main(){
	nes;
	int n;
	cin>>n;
	vector<int>v1(n);
	for(int i=0;i<n;++i) cin>>v1[i];
	int p=v1[0];
	for(int i=0;i<n;++i){
		p=__gcd(p,v1[i]);
		if(v1[i]!=1)
		ch(v1[i]);
	}
	if(!x) cout<<"pairwise coprime";
	else if(p==1) cout<<"setwise coprime";
	else cout<<"not coprime";
	return 0;
}

Measured memory_bytes: 7312
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
const int MOD=998244353;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin >> n;
    vector<ll> a(3*n);
    priority_queue<ll,vector<ll>,greater<ll>> p;
    priority_queue<ll> q;
    for(int i=0;i<3*n;i++){
        cin >> a[i];
    }
    vector<ll> b(3*n),c(3*n);
    ll sum=0;
    for(int i=0;i<2*n;i++){
        if(i<n){
            p.push(a[i]);
            sum+=a[i];
        }
        else{
            ll t=p.top();
            if(t<a[i]){
                p.pop();
                sum+=a[i];
                sum-=t;
                p.push(a[i]);
            }
        }
        b[i]=sum;
    }
    sum=0;
    for(int i=3*n-1;i>=n;i--){
        if(i>=2*n){
            q.push(a[i]);
            sum+=a[i];
        }
        else{
            ll t=q.top();
            if(t>a[i]){
                q.pop();
                sum+=a[i];
                sum-=t;
                q.push(a[i]);
            }
        }
        c[i]=sum;
    }
    ll ans=-INF;
    for(int i=n-1;i<2*n;i++){
        chmax(ans,b[i]-c[i+1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 9588
#include <bits/stdc++.h>//復習必須
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
int main () {
    ll A , B , M;
    cin >> A >> B >> M ;
    vector<int> a(A);
    vector<int> b(B);
    rep(i ,A ){
      cin >> a[i] ;
    }

    rep(j ,B ){
      cin >> b[j] ;
    }

    int minA = *min_element(a.begin(), a.end());
    int minB = *min_element(b.begin(), b.end());
    ll ans = minA + minB ;
    
    ll kari , x , y , c;
    rep(k ,M){
        cin >> x >> y >> c ;
        kari= a[x-1] + b[y-1] -c ;
        ans = min(ans, a[x-1] + b[y-1] - c);

    }

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

 


Measured memory_bytes: 1024
n = int(input())
x, y = [int(i) for i in input().split()]

for i in range(n-1):
  t, a = [int(i) for i in input().split()]
 
  c = max(-(-x//t), -(-y//a))

  x = t * c
  y = a * c
    
print(x+y)

Measured memory_bytes: 3060
{-# LANGUAGE TypeApplications #-}

import           Control.Monad
import           Control.Applicative
import           Data.List
import           Data.Char
import           Control.Arrow

main = do
  [n, k] <- map (read @Int) . words <$> getLine
  print =<< sum . take k . sort . map (read @Int) . words <$> getLine



Measured memory_bytes: 5188
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;

int main()
{
    int n;cin >> n;
    map<string,long long int> m;
    string set[5]={"M","A","R","C","H"};
    for(int i=0;i<5;i++){
        m[set[i]]=0;
    }

    for(int i=0;i<n;i++){
        string s;cin>> s;
        m[s.substr(0,1)]++;
    }

    long long int res=0;
    for(int i=0;i<5;i++){
        for(int j=i+1;j<5;j++){
            for(int k=j+1;k<5;k++){
                res += m[set[i]]*m[set[j]]*m[set[k]];
            }
        }
    }
    p(res);
} 

Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int h = sc.nextInt();
		int w = sc.nextInt();
		System.out.print((H-h)*(W-w));
	}
}


Measured memory_bytes: 21844
def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)

    ans = 10**9

    for i in range(ls-lt+1):
        tmp = 0
        for j in range(lt):
            if s[i+j] != t[j]:
                tmp += 1
        ans = min(ans, tmp)
    print(ans)


main()


Measured memory_bytes: 9112
N=int(input())
num=[i for i in range(1,N+1)]
X=[]

for i in range(N):
    S,P=map(str,input().split())
    X.append([num[i],S,int(P)])

X = sorted(X,key=lambda d:d[2],reverse=True)
X = sorted(X,key=lambda d:d[1])

for i in X:
    print(i[0])

Measured memory_bytes: 9000
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int X = sc.nextInt();
    int[][] books = new int[N][M+1];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M+1; j++) books[i][j] = sc.nextInt();
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < 1 << N; i++) {
      int[] total = new int[M+1];
      for (int j = 0; j < N; j++) {
        if ((1&i>>j) == 1) {
          for (int k = 0; k < M+1; k++) total[k] += books[j][k];
        }
      }
      if (check(total, X)) ans = Math.min(ans, total[0]);
    }
    System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
  }
  static boolean check(int[] t, int x) {
    for (int i = 1; i < t.length; i++) {
      if (t[i] < x) return false;
    }
    return true;
  }
}


Measured memory_bytes: 28436
/**
 *    author:  tourist
 *    created: 20.11.2019 13:51:47       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long ans = 0;
  while (true) {
    bool any = false;
    for (int i = 0; i < n; i++) {
      long long steps = a[i] / n;
      any |= !!steps;
      ans += steps;
      a[i] -= steps * (n + 1);
      for (int j = 0; j < n; j++) {
        a[j] += steps;
      }
    }
    if (!any) break;
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, K = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N - K):
    print("Yes" if A[i + K] > A[i] else "No")

Measured memory_bytes: 32128
#include <iostream>
using namespace std;
#define MAX 100005
#define NIL -1

struct Node { int p, l, r;};

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

void print(int u) {
  int i,c;
  cout << "node " << u << ": ";
  cout << "parent = " << T[u].p << ", ";
  cout << "depth = " << D[u] << ", ";

  if( T[u].p == NIL ) cout << "root, ";
  else if( T[u].l == NIL ) cout << "leaf, ";
  else cout << "internal node, ";

  cout << "[";

  for(i=0, c=T[u].l; c!=NIL; i++,c=T[c].r) {
    if(i) cout <<", ";
    cout << c;
  }
  cout << "]" << endl;
}

void rec(int u, int p) {
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r,p);
  if(T[u].l != NIL) rec(T[u].l,p+1);
}

int main(void) {
  int i,j,d,v,c,l,r;
  cin >> n;
  for(i=0;i<n;i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i=0;i<n;i++) {
    cin >> v >> d;
    for(j=0;j<d;j++) {
      cin >> c;
      if(j==0) T[v].l=c;
      else T[l].r =c;
      l = c;
      T[c].p = v;
    }
  }
  for(i=0;i<n;i++) {
    if(T[i].p == NIL) r = i;
  }
  
  rec(r,0);
  
  for(i=0;i<n;i++) print(i);
  
  return 0;
}


Measured memory_bytes: 7672
n, k = map(int, raw_input().split())
left = 0; right = 10**18+1
while left+1<right:
    mid = (left + right) / 2
    c = mid
    for i in xrange(n-1):
        c -= (c+k-1)/k
    if c < 1:
        left = mid
    else:
        right = mid
print left

Measured memory_bytes: 6428
/*
 * https://atcoder.jp/contests/abc144/tasks/abc144_b
 */
#include <bits/stdc++.h>
 
using namespace std;

// ショートハンド
// #define ll intに変えればメモリ節約
#define ll long long

/* 
 * ループ系のマクロ
 * `REP(i, 10) { cout << i; }`のように、変数名,回数で動く
 */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/*
 * 正規表現
 */
#define MATCH(_str, _ptn) regex_match(_str, regex(_ptn))
#define REPLACE(_str, _ptn, _replacement) regex_replace(_str, regex(_ptn), _replacement)

# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())

# define pb push_back

# define INIT() cin.tie(0); ios::sync_with_stdio(false)

// `chmax(a, b)` aがbより小さければ、aをbに上書きする。chminは逆
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1e9 + 7;
int main() {
    INIT();

    ll a,b;
    cin >> a >> b;
    if(a == 1 || b == 1) {
        cout << 1;
        return 0;
    }
    cout << a * b / 2 + a * b % 2;
    return 0;
}

Measured memory_bytes: 256
/**
 * @author yuichirw
 *
 */
import java.util.*;

public class Main {
	static String game;
	static Scanner sc = new Scanner(System.in);
	
	static boolean read() {
		game = sc.next();
		return (game.equals("0")) ? false : true;
	}
	
	static String solve() {
		int pa, pb;
		char s, sb;
		pa = pb = 0;
		sb = game.charAt(0);
		for(int i = 1; i < game.length(); i++) {
			s = game.charAt(i);
			if(s == 'A') pa++;
			else pb++;
		}
		if(pa > pb) {
			pa++;
		} else if(pa < pb) {
			pb++;
		}
		return "" + pa + " " + pb;
	}
	
	public static void main(String[] args) {
		while(read()) {
			System.out.println(solve());
		}
	}
}

Measured memory_bytes: 11000
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <bitset>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;
// const ll mod =  998244353 ;
const ll mod =  1000000007 ;
const ll inf = 1e18;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())

template<typename T> void print_vec(vector<T> a) {int n = a.size();REP(i, n) {cout >> a[i]; if(i!=n-1) cout << " "; else cout << endl;}}
ll power(ll base, ll exponent){ if(exponent % 2){ return power(base, exponent - 1) * base % mod; }else if(exponent){ ll root_ans = power(base, exponent / 2); return root_ans * root_ans % mod; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
template<typename T> ll sum(T begin, T end) {return accumulate(begin, end, 0ll);}
struct combination{ vector<ll> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

using Pair = pair<ll, ll>;

map<Pair, int> edge_n;
map<Pair, int> edge_c;
vector<vector<int>> g;

void dfs(int from, int current, int node_color) {
  int color = 0;
  for(const auto next :g[current]) {
    if(next == from) continue;
    if(color == node_color) color++;
    edge_c[{current, next}] = color;
    edge_c[{next, current}] = color;
    dfs(current, next, color++);
  }
}

signed main() {
  ios::sync_with_stdio(false);
  int n, t;
  cin >> n >> t;
  vector<ll> a(n), b(n);
  REP(i, n) cin >> a[i] >> b[i];
  vector<vector<ll>> dp(n+1, vector<ll>(t+3001)), rdp(n+1, vector<ll>(t+3001));
  REP(i, n) {
    REP(j, t+1) {
      dp[i+1][j] = dp[i][j];
    }
    REP(j, t) {
      dp[i+1][j+a[i]] = max(dp[i+1][j+a[i]], dp[i][j] + b[i]);
    }
  }
  REP(i, n+1) {
    REP(j, t) {
      dp[i][j+1] = max(dp[i][j], dp[i][j+1]);
    }
  }
  reverse(all(a));
  reverse(all(b));
  REP(i, n) {
    REP(j, t+1) {
      rdp[i+1][j] = rdp[i][j];
    }
    REP(j, t) {
      rdp[i+1][j+a[i]] = max(rdp[i+1][j+a[i]], rdp[i][j] + b[i]);
    }
  }
  REP(i, n+1) {
    REP(j, t) {
      rdp[i][j+1] = max(rdp[i][j], rdp[i][j+1]);
    }
  }
  reverse(all(a));
  reverse(all(b));
  ll ans = 0;
  REP(i, n) {
    REP(j, t) {
      ans = max(ans, dp[i][j] + rdp[n-i-1][t-j-1] + b[i]);
    }
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  long long N;
  long long min_path = 10e+15;
  cin >> N;
  for (int i = 0; i < 5; i++) {
    long long val;
    cin >> val;
    min_path = min(min_path, val);
  }
  cout << (N / min_path) + (N % min_path == 0 ? 0 : 1) + 4 << endl;
  return 0;
}

Measured memory_bytes: 256
object Main extends App {
    val hm = scala.collection.mutable.HashMap[(Int, Int, Int), Int]().withDefaultValue(0)
    val in = io.Source.stdin.getLines.map(_.split(" ").map(_.toInt))
    in.next
    for (Array(b, f, r, v) <- in) hm(b, f, r) += v
    for (b <- (1 to 4)) {
        for (f <- (1 to 3))
            println(" " + (1 to 10).map(hm(b, f, _)).mkString(" "))
        if (b != 4) println("####################")
    }
}

Measured memory_bytes: 44656
import java.util.Scanner;

class Main {
  public static void main(String args[]) {
	  	Scanner scanner = new Scanner(System.in);
	  	String str;
	  	String con[] =  new String[1000];
	  	int sumbox[] = new int[1000];
	  	int num = 0;
	  	int sum;
	  	int dig;
		boolean end = false;
		int count = 0;
		
		//初期化
		for(int i = 0; i < 1000 ;i ++) {
	  		con[i] = "";
		}
		
		while( !end  ){
			str = scanner.nextLine();
			count = str.length();		//文字数取得
			sum = 0;
			for(int i = 0; i < 1000 ;i ++) {
		  		sumbox[i] = 0;
			}
			
			//文字列を1文字ずつの数字に
			for(int i = 0; i < count ;i ++) {
		  			con[i] = str.substring(i,i + 1);
		  			sumbox[i] = Short.parseShort(con[i]);
			}
			
			//終了判定したい場所
			if( sumbox[0] == 0 ){
				end = true;
				break;
			}
			//各桁を足す処理
			for(int i = 0; i < count ;i ++) {
		  			sum += sumbox[i];
			}
			//出力
			System.out.println(sum);
		}
		scanner.close();
  }
}


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

int main() {
   long long n;
   cin>>n;
   
   long long total =1;
   for(int i=1;i<=n;i++){
       total*=i;
       total%=1000000007;
   }
   cout << total << endl;
   return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <vector>
using namespace std;
#define FOR(__I,__N) for (int __I = 0; __I < __N; ++__I)

typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64, int64> pll;

const int MOD = 998244353;

const int MAX_N = 3000;
const int MAX_S = 3000;

int A[MAX_N];
int dp[MAX_N+1][MAX_S+1];
int p2[MAX_N+1];
int main(){
	int N, S;	scanf("%d%d",&N,&S);
	FOR(i,N)	scanf("%d",A+i);

	dp[0][0] = 1;

	FOR(i,N){
		FOR(x,S+1){
			//dp[i+1][x] = dp[i][x]*2+dp[i][x-A[i-1]];
			dp[i+1][x] = dp[i][x]*2%MOD;
			if(x-A[i] >= 0){
				dp[i+1][x] += dp[i][x-A[i]];
				while(dp[i+1][x] >= MOD) dp[i+1][x] -= MOD;
			}
		}
	}
	//p2[0] = 1;
	//FOR(i,N)	p2[i+1] = p2[i]*2%MOD;
	int ans = 1;
	ans = dp[N][S];

	//FOR(k,N){
		//int t = (int64)dp[k+1][S]*p2[N-k-1]%MOD;
		//ans = (ans+t)%MOD;
	//}
	printf("%d\n",ans);
}




Measured memory_bytes: 39016
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1000000000000000000

using namespace std;

int main(void){
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  
  ll ans = 0;
  for (int i = 0; i < n; i++){
    if (i % 2 == 0 && a[i] % 2 == 1)
      ans++;
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
	int a[100];
	int i = 0;
	while (cin >> a[i]){
		if (a[i] == 0){
			int j = i;
			while (1){
				j--;
				if (a[j] != 0){
					cout << a[j] << endl;
					a[j] = 0;
					break;
				}
			}
		}
		i++;
	}
	
	return 0;
}


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

#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define MAXX 100005

#define PI 3.14159265358979323846264338327950

#define ll signed long long int

ll a[MAXX];
multiset<ll> ms;
multiset<ll>::iterator it;
signed main()
{
    FAST;
    string s;
    ll k;
    cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4] >> k;
    for(ll i = 0; i <= 3; i++){
    	for(ll j = i+1; j <= 4; j++){
    		if(a[j] - a[i] > k){
    			cout << ":(";
    			return 0;
			}
		}
	}
	cout << "Yay!";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F(i,s,e) for(int i=s;i<e;++i)

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    int cnt=0;
    F(i,0,c){
        if(b-a<0) break;
        b-=a;
        ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

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

int w, h;

int dp[2][2][110][110];

int dfs(bool f, bool p=true, int x=1, int y=1)
{
  if (x > w || y > h) return 0;
  if (x == w && y == h){
    return 1;
  }

  int &ret = dp[f][p][x][y];
  if (ret != -1) return ret;

  ret = 0;
  if (p){
    ret += dfs(true, f == true, x + 1, y) % 100000;
    ret += dfs(false, f == false, x , y + 1) % 100000;
  } else {
    ret = dfs(f, true, x + f, y + !f) % 100000;
  }

  return ret %= 100000;
}

int solve()
{
  return (dfs(true, true, 2, 1) % 100000 + dfs(false, true, 1, 2) % 100000) % 100000;
}

int main()
{
  while (cin >> w >> h, w){
    memset(dp, -1, sizeof(dp));
    cout << solve() << endl;
  }
}

Measured memory_bytes: 3288
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<pair<int, int> > > vvp;
typedef vector<pair<int, int> > vp;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<vector<ll> > vvl;
typedef vector<ll> vl;
typedef vector<vector<bool> > vvb;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef pair<string, int> psi;
typedef pair<int, int> pii;
#define rep(i,s,n) for(int i = (s); i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define yn(f) (f?"yes":"no")
#define YN(f) (f?"YES":"NO")
#define Yn(f) (f?"Yes":"No")
#define mod (1e9+7)
#define inf (1e9+7)
#define nil -1
struct p {
	int x, y;
};
int n = 8;
vvb A(n, vb(n, false));
vi row(n,0);
vb col(n,false);
vb dpos(n * 2 - 1,false);
vb dneg(n*2-1,false);
void print() {
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (A[i][j] && j != row[i])return;
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << (row[i]==j?"Q":".") ;
		}
		cout << endl;
	}
}
void recursive(int i) {
	if (i == n) {
		print();
		return;
	}
	for (int j = 0; j < n; j++)
	{
		if (col[j] || dpos[i + j] || dneg[(n - 1) - j + i])continue;
		col[j] = dpos[i + j] =dneg[(n - 1) - j + i] = true;
		row[i] = j;
		recursive(i+1);
		row[i] = 0;
		col[j] = dpos[i + j] = dneg[(n - 1) - j + i] = false;
	}
}
int main() {
	int k;
	cin >> k;
	
	rep(i, 0, k) {
		int x, y;
		cin >> y >> x;
		A[y][x] = true;
	}
	recursive(0);
}



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

using namespace std;

int main() {
	long n, q;
	cin >> n >> q;
	string s;
	cin >> s;
	vector<long> l(q), r(q);
	for (long i=0; i<q; ++i) {
		cin >> l[i] >> r[i];
	}
	vector<long> a(n, 0);

	for (long i=0; i<n-1; ++i) {
		if (s[i] == 'A' and s[i+1] == 'C') {
			a[i+1] = a[i]+1;
		} else {
			a[i+1] = a[i];
		}
	}

	//cout << "-------------\n";

	//for (long i = 0; i < a.size(); ++i) {
	//	cout << a[i] << endl;
	//}

	//cout << "-------------\n";

	for (long i=0; i<q; ++i) {
		cout << a[r[i]-1] - a[l[i]-1] << endl;
	}

	return 0;
}

Measured memory_bytes: 3456
n = gets.to_i
sum = Array.new(n+1){ Array.new(n+1,0) }
n.times do |i|
  l = gets.split.map(&:to_i)
  n.times do |j|
    sum[i+1][j+1] += sum[i+1][j] + l[j]
  end
end
n.times do |i|
  n.times do |j|
    sum[j+1][i+1] += sum[j][i+1]
  end
end
ret = - 1 << 31
n.downto(1).each do |i|
  n.downto(1).each do |j|
    i.times do |k|
      j.times do |l|
        x = sum[i][j] - sum[i][l] - sum[k][j] + sum[k][l]
        ret = x if x > ret
      end
    end
  end
end
p ret

Measured memory_bytes: 8932
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string in;
    cin>>in;
    if(in=="ABC")cout<<"ARC"<<endl;
    else cout<<"ABC"<<endl;
    return 0;
}

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

int main() {
  int s, res=0, h, t, o;
  cin >> s;
  h = s/100;
  t = (s - h*100)/10;
  o = (s - h*100 - t*10);
  
  if (h==1) res += 1;
  if (t==1) res += 1;
  if (o==1) res += 1;

  cout << res << endl;
}


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

using namespace std;

//#define MD 100010

int main(){
    string s;
    cin>>s;
    int ans=700;
    for(int i=0;i<3;i++){
        if(s[i]!='x'){
            ans+=100;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <utility>
#include<math.h>
#include <iomanip>
#include<vector>
#define ll long long
#define ull unsigned long long
#include<numeric>
#include <map>
using namespace std;

int tim[101];

int main()
{
    std::ios::sync_with_stdio(false);
    int n,t,m,p,x;
    long long su=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>tim[i],su+=tim[i];
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>p>>x;
        cout<<su-(tim[p-1]-x)<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
using namespace std;
#define Rep(i, n) for (int i = 0; i < (n); ++i)
#define InitRep(i, begin, n) for (int i = (begin); i < (n); ++i)
#define RepItr(it, begin, end) for (auto it = (begin); it != (end); ++it)
using int64 = long long;
using vint = vector<int>;
using vint64 = vector<int64>;
const static double PI = ::acos(-1);

constexpr int64 MOD = 1000000007;


int main()
{
    unordered_set<int> choices{ 1,2,3 };
    int a, b;
    cin >> a >> b;
    choices.erase(a);
    choices.erase(b);

    cout << (*choices.begin()) << endl;

    return 0;
}


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

using namespace std;

struct Node {
	ll x, y;
}info[100];
int n;
bool vis[100];

int main () {
	#ifdef wll
//	freopen ("testdata.in", "r", stdin);
	#endif
	scanf ("%d", &n);
	if (n == 1) {
		printf ("1\n");
		return 0;
	}
	for (int i = 1; i <= n; ++i) {
		scanf ("%lld%lld", &info[i].x, &info[i].y);
	}
	sort (info + 1, info + n + 1, [](Node m, Node n) {
		return m.x == n.x ? m.y < n.y : m.x < n.x;
	});
	int ans = n - 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			int p = info[j].x - info[i].x;
			int q = info[j].y - info[i].y;
			memset (vis, 0, sizeof (vis));
			for (int k = 1; k <= n; ++k) {
				for (int l = k + 1; l <= n; ++l) {
					if (info[l].x == info[k].x + p && info[l].y == info[k].y + q) {
						vis[l] = 1;
					}
				}
			}
			int nowans = 0;
			for (int i = 1; i <= n; ++i) {
				if (!vis[i]) {
					nowans ++;
				}
			}
			ans = min (ans, nowans);
		}
	}
	printf ("%d\n", ans);
	return 0;
}
















Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>

int A, B, C, D, E2, F;
int r1, r2;
double d;
double E;

void solve()
{
	int i, j, k, l;
	r1 = -1;
	int v1, v2;
	double vd;
	for(i=0; i<=30; i++){
		for(j=0; j<=30; j++){
			for(k=0; k<=3000; k++){
				if((i*100*A+j*100*B +k*C) == 0)
					continue;
				if(i*100*A + j*100*B + k*C > F)
					continue;
				if(100.0*(k*C)/(i*100*A+j*100*B +k*C) > E)
					continue;
				l = (F - i*100*A - j*100*B - k*C)/D;
				if(100.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D) > E){
					int ld = ((i*100*A+j*100*B+k*C)*E - 100*k*C)/((100-E)*D) + 1e-6;
					l = ld;
					if( r1==-1 || 1.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D) > d){
						d = 1.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D);
						r1 = i*100*A+j*100*B +k*C+l*D;
						r2 = k*C+l*D;
					}
				}
				else{
					if( r1==-1 || 1.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D) > d){
						d = 1.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D);
						r1 = i*100*A+j*100*B +k*C+l*D;
						r2 = k*C+l*D;
					}
				}
				/*if( 100.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D) > E)
					continue;
				if( r1==-1 || 1.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D) > d){
					d = 1.0*(k*C+l*D)/(i*100*A+j*100*B +k*C+l*D);
					r1 = i*100*A+j*100*B +k*C+l*D;
					r2 = k+l;
				}*/
			}
		}
	}
	if(r1 == -1)
		printf("0 0\n");
	else
		printf("%d %d\n", r1, r2);
}

int main()
{
	//test();
	//A=25, B=6, C=11, D=26, E=88, F=1919;
	//solve2();
	//int oo = 1;
	//freopen("in.txt", "r", stdin);
	scanf("%d%d%d%d%d%d", &A, &B, &C, &D, &E2, &F);
	E = 1.0*E2/(100+E2)*100;
	solve();
	//solve2();
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define sc second
#define takeline cin.ignore();
#define iactive cout.flush();
#define N 300005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
ll r,s,p,n,k; string t; ll dp[N][4];
ll maxval(ll i,ll pre){
	if(i>=n) return 0;
	if(dp[i][pre]!=-1){
		return dp[i][pre];
	}
	ll a=0,b=0,c=0;
	if(t[i]=='r'){
		if(pre!=0) a=maxval(i+k,0);
		if(pre!=1) b=maxval(i+k,1)+p;
		if(pre!=2) c=maxval(i+k,2);
	}
	else if(t[i]=='p'){
		if(pre!=0) a=maxval(i+k,0);
		if(pre!=1) b=maxval(i+k,1);
		if(pre!=2) c=maxval(i+k,2)+s;
	}
	else{
		if(pre!=0) a=maxval(i+k,0)+r;
		if(pre!=1) b=maxval(i+k,1);
		if(pre!=2) c=maxval(i+k,2);
	}
	return dp[i][pre]=max(a,max(b,c));
}
int main(){

	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,l;
	cin>>n>>k;
	cin>>r>>s>>p;
	cin>>t;
	memset(dp,-1,sizeof(dp));
	ll an=0;
	for(i=0;i<k;i++){
		an+=maxval(i,3);
	}
	cout<<an;
	return 0;
}

Measured memory_bytes: 16080
#include<bits/stdc++.h>
using namespace std;
#define int long long int

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t,n,m,i,j,k,sum=0;
    cin>>n;
    for(i=1;i<=n;i++){
        string s = to_string(i);
        if(s.size()%2==1)
            sum++;
    }
    cout<<sum<<'\n';


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef long double ld;

#define rc(s) return cout << s, 0
#define fi first
#define se second
#define L (nod << 1)
#define R (L | 1)
#define smax(X, Y) ((X) > (Y) ? (X) : (Y))
#define smin(X, Y) ((X) < (Y) ? (X) : (Y))

const ll inf = (1LL<<62);
const int iinf = (1<<30);
//CLOCKS_PER_SEC

const int N = 100100;
int n, m, pr[N];
vector <int> v[N];

int main(){
    //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //ifstream cin ("test.in");
    //ofstream cout ("test.out");
    cin >> n >> m;
    for (int i=0; i < m; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    queue <int> Q;
    Q.push(1);
    pr[1] = -1;
    
    while (!Q.empty()){
        int nod = Q.front();
        Q.pop();
        for (int it: v[nod]){
            if (!pr[it]){
                pr[it] = nod;
                Q.push(it);
            }
        }
    }
    for (int i=2; i<=n;  i++)
        if (!pr[i])
            rc("No");
    
    cout << "Yes\n";
    for (int i=2; i<=n; i++)
        cout << pr[i] << '\n';
    
    return 0;
}


Measured memory_bytes: 10360
#include<cstdio>
#include<cstring>
const int md=1e9+7,N=20;
inline void upd(int&a){a+=a>>31&md;}
int C,n,m,k,_0[N],_1[N],f[N+1][1<<N];
inline bool check(int id,int S){return(S&_0[id])==0&&(S&_1[id])==_1[id];}
inline int get(int S,int i){
	int T=S&((1<<i)-1);
	if(!T)return(1<<i)|S;
	return(S^(1<<(31-__builtin_clz(T))))|(1<<i);
}
int main(){
	scanf("%d%d%d",&n,&m,&k),--n;
	C=1<<n;
	while(k--){
		int A,B,C;
		scanf("%d%d%d",&A,&B,&C);
		B=n-B;
		(C?_1:_0)[A-1]|=1<<B;
	}
	for(int i=0;i<C;++i)f[n][i]=check(0,i);
	for(int t=1;t<m;++t){
		for(int i=n-1;~i;--i)
		for(int S=0;S<C;++S)if(int d=f[i+1][S]){
			//0
			if(!(_1[t]>>i&1)&&!(S>>i&1))upd(f[i][S]+=d-md);
			//1
			if(!(_0[t]>>i&1)){
				if(S>>i&1)upd(f[i][S]+=d-md);else{
					int T=get(S,i);
					upd(f[i][T]+=d-md);
				}
			}
		}
		memcpy(f[n],*f,sizeof*f);
		for(int i=0;i<n;++i)memset(f[i],0,sizeof*f);
	}
	int ans=0;
	for(int i=0;i<C;++i)upd(ans+=f[n][i]-md);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 84096
#include <iostream>

int main() {
    int price = 0;
    int numOfOneYen = 0;
    std::cin >> price >> numOfOneYen;
    static const int INFINITE_COIN_YEN = 500; 
    
    int lastPrice = price % INFINITE_COIN_YEN;
    if (numOfOneYen - lastPrice >= 0) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
}


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

int main() {
  int n;
  string s;
  cin >> n >> s;
  int r = 0, b = 0;
  rep(i, n) {
    if (s[i] == 'R') ++r;
    if (s[i] == 'B') ++b;
  }
  if (r > b) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <limits>

using namespace std;

const int MAX = 50;

int min_change(int c[], int n, int m)
{
	int dp[m+1];

	for (int i = 1; i < m+1; i++)
		dp[i] = numeric_limits<int>::max();

	dp[0] = 0;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j < n; j++) {
			if (c[j] <= i) {
				int t = dp[i-c[j]];

				if (t != numeric_limits<int>::max() && 1+t < dp[i])
					dp[i] = 1+t;
			}
		}
	}

	return dp[m];
}

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

	int m, n;
	int c[MAX];

	cin >> m >> n;
	for (int i = 0; i < n; i++)
		cin >> c[i];

	cout << min_change(c, n, m) << endl;

	return 0;
}

Measured memory_bytes: 3340
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
int fa[200005],a1[200005],fb[200005];
map<int,map<int,int> >mp;
inline int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
inline int fd(int x)
{
	if(fb[x]==x)
		return x;
	return fb[x]=fd(fb[x]);
}
inline void U(int x,int y)
{
	fa[find(x)]=find(y);
}
inline void U1(int x,int y)
{
	fb[fd(x)]=fd(y);
}
int main()
{
	int n,k,l;
	scanf("%d%d%d",&n,&k,&l);
	for(int i=1;i<=n;i++)
		fa[i]=fb[i]=i;
	for(int i=1;i<=k;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		U(x,y);
	}
	for(int i=1;i<=l;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		U1(x,y);
	}
	for(int i=1;i<=n;i++)
		mp[find(i)][fd(i)]++;
	for(int i=1;i<n;i++)
		printf("%d ",mp[find(i)][fd(i)]);
	printf("%d\n",mp[find(n)][fd(n)]);
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define sumvec(v) accumulate(all(v),0LL)
#define mapmin(v) v.rbegin()->first
#define mapmax(v) v.begin()->first
#define pb push_back
#define pf push_front
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK cerr<<"OK\n"
#define OK1 cerr<<"OK1\n"
#define OK2 cerr<<"OK2\n"
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n
#define endl '\n'

typedef long long ll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);
const ll mod=1000000007;
const ll mod2=998244353;

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

template<class T>
inline bool chmax(T& a, T b){if(a<b){a=b;return true;} return false;}

template<class T>
inline bool chmin(T& a, T b){if(a>b){a=b;return true;} return false;}

void YES(bool b) {cout << ((b)?"YES\n":"NO\n");}
void Yes(bool b) {cout << ((b)?"Yes\n":"No\n");}
void yes(bool b) {cout << ((b)?"yes\n":"no\n");}
void Yay(bool b) {cout << ((b)?"Yay!\n":":(\n");}

ll powmod(ll a,ll b){ll c=1; while(b>0){ if(b&1){ c=a*c%mod; } a=a*a%mod; b>>=1; } return c;}
ll nCrmod(ll n,ll r){ll x=1,y=1; rep(i,r){x=x*(n-i)%mod; y=y*(i+1)%mod;} return x*powmod(y,mod-2)%mod;}
ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	string s;
	cin >> s;
	ll n=s.size();
	string t="",u="";
	rep(i,n){
		t+=(i%2?'0':'1');
		u+=(i%2?'1':'0');
	}
	ll a=0,b=0;
	rep(i,n){
		if(s[i]!=t[i]) a++;
		if(s[i]!=u[i]) b++;
	}
	cout << min(a,b) << endl;
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;

int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	double w,h;
	double x,y;
	cin>>w>>h>>x>>y;

	double area=w*h;
	area/=2;
	cout<<fixed<<setprecision(9)<<area<<" ";
	if(2*x==w&&2*y==h) {
		cout<<1<<endl;
	}
	else{
		cout<<0<<endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
    int X;
    cin >> X;

    if(X < 100){
        cout << "0" << endl;
        return 0;
    }else{
        int hund = X/100;
        int ten = X%100;
        if(ten == 0){
            cout << "1" << endl;
            return 0;
        }
        for(int a = 95; a >= 0; a -= 5){
            int suma = a;
            int numa = a/5; 
            for(int b = 100; b >= 0; b -= 4){
                int sumb = suma + b;
                int numb = numa + b/4;
                if(sumb > ten) continue;
                for(int c = 99; c >= 0; c -= 3){
                    int sumc = sumb + c;
                    int numc = numb + c/3;
                    if(sumc > ten) continue;
                    for(int d = 100; d >= 0; d -= 2){
                        int sumd = sumc + d;
                        int numd = numc + d/2;
                        if(sumd > ten) continue;
                        for(int e = 100; e >= 0; e -= 1){
                            // cout << e << endl;
                            int sume = sumd + e;
                            int nume = numd + e;
                            if(sume > ten) continue;
                            if(sume == ten && nume <= hund){
                                cout << "1" << endl;
                                return 0;
                            }
                        }
                    }
                } 
            }
        }
    }
    cout << "0" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define F first
#define S second
//const ll mod=1e9+7;
void solve(){
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k>a+b){
    	cout<<a-(k-(a+b));
    }
    else{
    	cout<<min(k,a);
    }
}
int main(){
    IOS;
    /*int t;
    cin>>t;
    while(t--){
        solve();
    }*/
    solve();
    return 0;
}

Measured memory_bytes: 3612
import copy
import sys
N, K = (int(x) for x in input().split())
string = input()
ls = list(map(int, string))

if string == "1" or string == "0":
    print(1)
    sys.exit()


def cal_list(pb):
    comp = []
    k = 0
    m = 0
    if pb[1][0] == "0":
        pb[0].insert(0, 0)
        pb[1].insert(0, "1")
    if pb[1][len(pb[1][:])-1] == "0":
        pb[0].append(0)
        pb[1].append("1")
    comp.append(pb[0][0])
    for i in range(1, len(pb[0][:])):
        comp.append(comp[i-1]+pb[0][i])
    ans = 0
    j = 0
    for h in list(reversed(range(K+1))):
        while 2*h+1+2*j <= len(comp):
            if j == 0:
                ans = comp[2*h]
            else:
                ans = max(ans, comp[2*h+2*j]-comp[j*2-1])
            j += 1
    print(ans)


def split_01(lis):
    pb = [[] for i in range(2)]
    i = 0
    while i < len(lis):
        count_0, count_1 = 0, 0
        if lis[i] == 0:
            while lis[i] == 0:
                count_0 += 1
                i += 1
                if i >= len(lis):
                    break
            pb[0].append(count_0)
            pb[1].append("0")
        if i >= len(lis):
            break
        if lis[i] == 1:
            while lis[i] == 1:
                count_1 += 1
                i += 1
                if i >= len(lis):
                    break
            pb[0].append(count_1)
            pb[1].append("1")
        if i >= len(lis):
            break
    return pb


pr = split_01(copy.copy(ls))
cal_list(copy.copy(pr))


Measured memory_bytes: 11324
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl "\n"
#define ll long long
#define ld long double
#define l_b lower_bound
#define u_b upper_bound
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define pq priority_queue
#define umap unordered_map
#define sz(a) int((a).size())
#define all(c) c.begin(),c.end()
#define test() ll t;cin>>t;while(t--)
#define mset(a,x) memset(a,x,sizeof(a))
#define rep(i,a,n) for(ll i = a; i < n; ++i) 
#define debug(x) cout<<(#x)<<" is "<<(x)<<endl
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0)

const int inf = 1e9;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;


int main() {
	// fastIO;
	int l, r;
	cin >> l >> r;
	if(r-l >= 2019)
		cout << "0";
	else{
		int res = 2019;
		for(int i = l; i <= r; i++){
			for(int j = i+1; j <= r; j++){
				res = min(res, ((i%2019)*(j%2019))%2019);
			}
		}
		cout << res;
	}
    
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){

    int d;
    while(cin>>d,d){
        int n,m;
        cin>>n>>m;
        vector<int> S;
        int t;
        S.push_back(0);
        for(int i = 1;i < n;i++)cin>>t,S.push_back(t);
        S.push_back(d);
        vector<int> _S;
        for(int i = 0;i < S.size();i++){
            _S.push_back(-S[i]);
        }
        sort(S.begin(),S.end());sort(_S.begin(),_S.end());
        int ans = 0;
        for(int i = 0;i < m;i++){
            int x;
            cin>>x;
            vector<int>::iterator it = lower_bound(S.begin(),S.end(),x);
            int z = (*it) - x;
            it = lower_bound(_S.begin(),_S.end(),-x);
            z = min(z,x + (*it));
            ans += z;
        }
        cout<<ans<<endl;
    }

    return 0;
}

Measured memory_bytes: 2124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repn(i, n) for (int i = 0; i <= (int)(n); i++)
#define srep(i, l, n) for (int i = l; i < (int)(n); i++)
#define srepn(i, l, n) for (int i = l; i <= (int)(n); i++)
#define pb push_back 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const int MOD = 1000000007;
const int INF = 1e9;
#define PI 3.14159265369;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
	int n;
	cin >> n;
	vector<int> m;
	int a = 6, b = 9;
	while(a <= n){
		m.push_back(a);
		a *= 6;
	}
	while(b <= n){
		m.push_back(b);
		b *= 9;
	}
    m.push_back(1);
    int dp[n+1];
	fill(dp, dp+n+1, INF);
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		for(auto e : m){
			if(e <= i){
				chmin(dp[i], dp[i-e]+1);
			}
		}
	}
	cout << dp[n] << endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int a = 0;

        for(int i = 1; i <= n; i++ ){
            if(i % 3 == 0){
                System.out.print(" " + i);
            }else{
                a = i;

            while(a > 0){
                if (a % 10 == 3){
                    System.out.print(" " + i);
                    break;
                }else{
                    a /= 10;
                }
            }
            }
        }
        System.out.println();
    }
}

Measured memory_bytes: 28696
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>

using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if(b<a){
        cout<<a-1<<endl;
    }else{
        cout<<a<<endl;
    }
}
   

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int p = 27;
map<ll,int>has1;
ll hh[50015]={0};
ll pow1[50015]={0};
char s[50005]={0};
ll gethashcode(int i,int m){
    return hh[i+m-1]-hh[i-1]*pow1[m];
}
int n;
ll num;
int check(int m){
    has1.clear();
    for(int i=1;i+m-2<=n;i++){
        num=gethashcode(i,m);
       // cout << num <<endl;
        if(has1[num]){
            if(has1[num]+m<=i){
                return 1;
            }
        }
        else
            has1[num]=i;
    }
    return 0;
}
int main()
{
    pow1[0]=1;
    for(int i=1;i<50005;i++){
        pow1[i]=pow1[i-1]*p;
    }
    scanf("%d",&n);
    scanf("%s",s+1);
    hh[0]=0;
    for(int i=1;i<=n;i++)
        hh[i]=hh[i-1]*p+s[i]-'a';
    int ans = 0 ;
    int l=1,r=n;
    while(l<r){
        int m=(l+r)/2;
        if(check(m)){
            ans=m;
            l=m+1;
        }
        else
            r=m;
    }
    printf("%d\n",ans);
    return 0;
}
//
//13
//orangerangeao



Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;
 
#define endl '\n'
#define loop(i, m, n) for (lli i = m; i < n; i++)
#define loope(i, m, n) for (lli i = m; i <= n; i++)
#define epool(i, m, n) for (lli i = m; i >= n; i--)
#define maxe *max_element
#define mine *min_element
#define mod 1000000007
#define mod2 998244353
#define vt vector<lli>
#define fi first
#define se second
#define pb push_back
#define umap unordered_map
#define mmap multimap
#define MP make_pair
#define empf emplace_front
#define empb emplace_back
#define ret(x) return cout << x, 0;
#define all(v) v.begin(),v.end()

#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;
const lli INF=1e18;

int32_t main(){
    fast_io
    lli i = 0,j = 0;
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //cout << fixed << setprecision(22);
    lli t;
    t=1;
    //cin >> t;
    lli cno=0;
    while (t--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        if(s.length()<=n) cout << s << endl;
        else{
            string p=s.substr(0,n);
            p+="...";
            cout << p << endl;
        }
            
    }

}



Measured memory_bytes: 3644
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n,m,c;
  cin >> n >> m >> c;
  int ans = 0;
  vi b(m);
  rep(i, m) cin >> b[i];
  rep(i, n){
    int tot = 0;
    rep(j, m){
      int a;
      cin >> a;
      tot += a * b[j];
    }
    if(tot + c > 0) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256