akhauriyash/Code-Regression huggingface dataset:
// F.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long LL;

const LL MOD = 998244353;

struct modll {
	long long x;
	modll() { }
	modll(int _x) : x(_x) { }
	operator int() const { return (int)x; }
	modll operator+(int y) { return (x + y + MOD) % MOD; }
	modll operator+=(int y) { x = (x + y + MOD) % MOD; return *this; }
	modll operator-(int y) { return (x - y + MOD) % MOD; }
	modll operator-=(int y) { x = (x - y + MOD) % MOD; return *this; }
	modll operator*(int y) { return (x * y) % MOD; }
	modll operator*=(int y) { x = (x * y) % MOD; return *this; }
	modll operator/(int y) { return (x * modpow(y, MOD - 2)) % MOD; }
	modll operator/=(int y) { x = (x * modpow(y, MOD - 2)) % MOD; return *this; }
	static modll modinv(int a) { return modpow(a, MOD - 2); }
	static modll modpow(int a, int b) {
		modll x = a, r = 1;
		for (; b; b >>= 1, x *= x) if (b & 1) r *= x;
		return r;
	}
};

template<typename T, size_t SIZE, T DEF_VAL, const T& Compare(const T&, const T&)>
class SegmentTree {
	vector<T> val;
public:
	SegmentTree() : val(SIZE * 2, DEF_VAL) { }
	T get(int a, int b, int l = 0, int r = SIZE, size_t i = 1) {
		if (r <= a || b <= l) return DEF_VAL;
		if (a <= l && r <= b) return val[i];
		return Compare(get(a, b, l, (l + r) / 2, i * 2), get(a, b, (l + r) / 2, r, i * 2 + 1));
	}
	void update(size_t i, T value) {
		i += SIZE;
		val[i] = Compare(val[i], value);
		while (i > 1) i >>= 1, val[i] = Compare(val[i * 2], val[i * 2 + 1]);
	}
};
typedef SegmentTree<long long, 1 << 18, 1LL << 62, min> MinLLSegTree;
typedef SegmentTree<long long, 1 << 18,         0, max> MaxLLSegTree;

int main(int argc, char* argv[]) {
	cout.precision(20);
#ifdef _MSC_VER
	while (true)
#endif
	{
		int n = -1;
		cin >> n;
		if (n < 0) return 0;
		vector<pair<LL, LL>> xd(n);
		for (int i = 0; i < n; ++i) {
			cin >> xd[i].first >> xd[i].second;
		}
		sort(xd.begin(), xd.end());
		vector<modll> dp(n + 1, 0);
		dp[n] = 1;
		MaxLLSegTree st;
		for (int i = n - 1; i >= 0; --i) {
			int j = (int)(lower_bound(xd.begin() + i + 1, xd.end(), make_pair( xd[i].first + xd[i].second, 0LL )) - xd.begin());
			LL m = max((LL)i, st.get(i, j));
			st.update(i, m);
			dp[i] = dp[i + 1] + dp[m + 1];
		}
		cout << dp[0] << endl;
	}
	return 0;
}


Measured memory_bytes: 9088
import collections
import sys
input = sys.stdin.readline

n = int(input())
a = [0]*n
ans = 0
for i in range(n):
    a[i] = int(input())
count_a = collections.Counter(a).most_common()
for i in range(len(count_a)):
    if count_a[i][1]%2 != 0:
        ans += 1
print(ans)

Measured memory_bytes: 21356
#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#ifndef bits/stdc++.h
  #include <bits/stdc++.h>
#endif /* end of include guard */

using namespace std;


#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef pair<int, int> p;

int main(){
  int n, m;
  cin >> n >> m;
  if(n == 1)
  {
    cout << m << endl;
    return 0;
  }
  // int tmp = ceil(pow(m, 0.5));
  int tmp = ceil(m / n);

  for (int i = tmp; i >= 1; i--) {
    if(m % i == 0 && m / i >= n)
    {
      cout << i << endl;
      return 0;
    }
  }

}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

void ReadFirstInput(int *snukesNumber, int *candyTypes)
{
    //printf_s("Enter the number of Snukes and Snacks: \n");
    scanf("%d %d", snukesNumber, candyTypes);
}

void CountTricks(int *snukesArray, int *snukesNumber)
{
    int counter = 0;
    
    for(int i = 0; i < *snukesNumber; i++)
    {
        if(snukesArray[i] != 1)
        {
            counter++;
        }
    }
    printf("%d \n", counter);
}

void CreateArray(int *snukesNumber, int *candyTypes)
{
    int *dArray = malloc(100 * sizeof(int));
    int *aArray =  malloc(100 * 100 * sizeof *aArray);
    int *snukesArray = malloc(100 * sizeof(int));
    
    for(int i = 0; i < *candyTypes; i++)
    {
        scanf("%d\n", &dArray[i]);
        for(int j = 0; j < dArray[i]; j++)
        {
            scanf("%d", &aArray[i + j]);
            int snukesWithSnacks = aArray[i + j];
            snukesArray[snukesWithSnacks - 1] = 1;
        }
    }
    
    CountTricks(snukesArray, snukesNumber);
    free(dArray);
    free(aArray);
    free(candyTypes);
}

int main(void)
{
    int *snukesNumber = malloc(3 * sizeof(int));
    int *candyTypes = malloc(3 * sizeof(int));
    
    ReadFirstInput(snukesNumber, candyTypes);
    CreateArray(snukesNumber, candyTypes);
    
    return 0;
}


Measured memory_bytes: 1712
#include <bits/stdc++.h>
using namespace std;
int main() {
  int A,B,C;
  cin >> A >> B >> C;
  for (int i = 0; i < B; i++) {
    if ((i*A)%B == C) {
      cout << "YES";
      return 0;
    }
  }
  cout << "NO";
}

Measured memory_bytes: 3616
n=int(input())
if n<=111:
    print(111)
elif n<=222:
    print(222)
elif n<=333:
    print(333)
elif n<=444:
    print(444)
elif n<=555:
    print(555)
elif n<=666:
    print(666)
elif n<=777:
    print(777)
elif n<=888:
    print(888)
else:
    print(999)

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

#define debug(a) cout << #a << " " << a << endl;
#define _debug(a, i) cout << #a << "[" << i << "]" << " = " << a[i] << endl;
#define fastio ios_base::sync_with_stdio(false); \
			cin.tie(0);							 \
			cout.tie(0);
#define PI 3.141592654

using namespace std;

using ll = long long;
const int MOD = 998244353;
const ll INF = 1e18 + 9;

ll powmod(ll base, ll exp, const ll MOD) { ll ans = 1; while (exp) { if (exp & 1)	ans = (ans * base) % MOD; base = (base * base) % MOD; exp >>= 1; }return ans; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll modInverse(ll n, const ll p) { return powmod(n, p - 2, p); }
void add(ll& x, ll v) { x = (x + v) % MOD; if (x < 0) x += MOD; }
//ll f[500005];
//ll kCn(ll k, ll n) { return (f[n] * modInverse((f[n - k] * f[k]) % MOD, MOD)) % MOD; }


void test_case() {

}

const int mxN = 3001;
ll dp[mxN][mxN];

int main() {
	fastio;
	//#ifndef ONLINE_JUDGE
	//	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
	//#endif // !ONLINE_JUDGE
	int N, S;
	cin >> N >> S;
	vector<int> a(N);
	for (int i = 0; i < N; ++i) {
		cin >> a[i];
	}
	
	dp[0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= S; ++j) {
			dp[i + 1][j] += 2 * dp[i][j];
			dp[i + 1][j] %= MOD;
			if (j + a[i] <= S) {
				dp[i + 1][j + a[i]] += dp[i][j];
				dp[i + 1][j + a[i]] %= MOD;
			}
			
		}
	}
	cout << dp[N][S];
	return 0;
}


Measured memory_bytes: 73928
var line;
var moji;
var result = 0;

var readline = require('readline');
var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line',function(x){
    line = x;
});

rl.on('close',function(){
    
    moji=line.split("");
    if(moji.length<3){console.log(0);}
    else{
        dfs(0,[]);
        console.log(result);
    }
});

function dfs(n,comb){
    if(n === moji.length){calc(comb); return(0);}

    // 入力値と同桁 かつ "7","5","3","0"のみを含む数の全パターン探索
    comb[n]=0; dfs(n+1,comb);
    comb[n]=3; dfs(n+1,comb);
    comb[n]=5; dfs(n+1,comb);
    comb[n]=7; dfs(n+1,comb);
}

function calc(comb){
    var num = "";

    // "7","5","3"の出現回数をカウントするカウンタ
    var counter_3=0;
    var counter_5=0;
    var counter_7=0;
    
    // 357077等、途中桁に0を含む数を除去するためのフラグ
    var flag = false;

    comb.forEach(function(x){num += x;});
    num = Number(num);

    if(num <= Number(line)){
        for(var i=0;i<moji.length;i++){
            if(comb[i]===3){counter_3++; flag=true;}            
            else if(comb[i]===5){counter_5++; flag=true;}            
            else if(comb[i]===7) {counter_7++; flag=true;} 
            else{if(flag===true){counter_3=0;counter_5=0;counter_7=0; break;}}
        }
        //console.log(comb,counter_3,counter_5,counter_7);
        if(counter_3 >=1 && counter_5>=1 && counter_7>=1){result++;}
    }
}  


Measured memory_bytes: 10552
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] array = new int[n];
		for(int i = 0;i<n;i++){
			array[i] = sc.nextInt();
		}

		int min = 0;
		int count = 0;
		min = array[0];
		for(int i = 1;i<n;i++){
			if(min >= array[i]){
				min = array[i];
			}else{
				count++;
			}
		}
System.out.println(n-count);

	}
}

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

#define MOD ((int)(1e9+7))

using namespace std;

typedef long long int Int;

Int pnum[1000];

bool IsPrime(Int n)
{
    Int num = sqrt(1.0*n);
    if(n == 2)
    {
	return true;
    }

    for(int i = 2;i <= num;i += 2)
    {
	if(n % i == 0)
	    return false;
    }

    return true;
}

Int Solve(Int n)
{
    Int count = 1;

    for(int i = 0;i < 1000;i++)
	pnum[i] = 1;

    for(int i = 2;i <= n;i++)
    {
	Int temp = i;
	for(int j = 2;j <= temp;) {
	    if(temp % j == 0 && IsPrime(j))
	    {
		pnum[j]++;
		temp /= j;
	    } else {
		j++;
	    }
	}
    }

    for(int i = 0;i < 1000;i++)
    {
	count = (count*pnum[i])%MOD;
    }

    return count;
}

int main(void)
{
    Int n;
    cin>>n;

    cout<<Solve(n)<<endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        String str = "";

        while(sc.hasNext()) {
        	str += sc.nextLine();
        }
        str = str.toLowerCase();

        char[] alphabet = new char[] {'a','b','c','d','e','f','g','h','i','j','k',
        							  'l','m','n','o','p','q','r','s','t','u','v',
        							  'w','x','y','z'};

        int[] ans = new int[alphabet.length];

        for(int i = 0; i < str.length(); ++i) {
        	for(int j = 0; j < alphabet.length; j++) {
        		if(str.charAt(i) == alphabet[j]) {
        			ans[j]++;
        		}
        	}
        }

        for(int i = 0; i < alphabet.length; i++) {
        	System.out.println(String.format("%s : %d", alphabet[i], ans[i]));
        }

    }
}


Measured memory_bytes: 26272
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define pb push_back
#define mt make_tuple
const int N = 1e5 + 10;
ll minwt[110][N],inp[110][2];
bool dp[110][N];
int main(){
	int n,w,s=0,flag;
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>inp[i][0]>>inp[i][1];
		s += inp[i][1];
	}
	for(int i=0;i<=s;i++){
		dp[0][i] = false;
		minwt[0][i] = 0; 
	}
	dp[0][0] = true;
	for(int i=1;i<=n;i++){
		dp[i][0] = true;
		minwt[i][0] = 0;
		for(int j=1;j<=s;j++){
			if(inp[i][1] <= j){
				flag = 0;
				if(dp[i-1][j]){
					dp[i][j] = true;
					minwt[i][j] = minwt[i-1][j];
					flag = 1;
				}
				if(dp[i-1][j-inp[i][1]]){
					dp[i][j] = true;
					if(flag == 1){
						minwt[i][j] = min(minwt[i][j],minwt[i-1][j-inp[i][1]]+inp[i][0]);
					}
					else	minwt[i][j] = minwt[i-1][j-inp[i][1]]+inp[i][0];
					flag = 1;
				}
				if(flag==0)	dp[i][j] = false;
			}
			else{
				dp[i][j] = dp[i-1][j];
				minwt[i][j] = minwt[i-1][j];
			}
		}
	}
	for(int i=s;i>=0;i--){
		if(dp[n][i] && minwt[n][i] <= w){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 90368
#include <set>
#include <array>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <vector>
#include <tuple>
#include <string>
#include <math.h>
#include <time.h>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <limits>
#include <climits>
#include <numeric>
#include <functional>

#define lnd '\n'
// #define reverse(i, n) for(ll i = n-1; i >= 0; --i)
#define from(i, n) for (ll i = 0; i < n; ++i)
#define loop(i, n) for(ll i = 0; i < n; i++)
#define REPN(i, n) for (ll i = 1; i <= n; ++i)
#define ALL(s) (s).begin(), (s).end()
#define rALL(s) (s).rbegin(), (s).rend()
#define sz(s) (int)(s).size()
#define mk make_pair
#define pb push_back
#define sqr(s) ((s) * (s))

using namespace std;

typedef long long ll;
typedef long long int lli;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;

template <class T>
T GCD (T a, T b) {
  if(a == 0) return b;
  return GCD(b%a, a);
}

template <class T>
T LCM(T a, T b){
  return a*b/GCM(a,b);
}

template <class T>
T modpow(T x, T p){
    T res = 1;
    while(p > 0){
        if(p&1) res *= x;
        x *= x;
        p /= 2;
    }
    return res;
}

template <class T>
T modpow(T x, T p, ll mod){
    T res = 1;
    while(p > 0){
        if(p&1) res = (res*x)%mod;
        x = (x*x)%mod;
        p /= 2;
    }
    return res%mod;
}

template <class T>
void print(T a[], ll n){
    for (ll i = 0; i < n; i++) std::cout << a[i] << ' ';
    cout << endl;
}

template<class T>
void printc(T c){
    for(auto const& v: c) std::cout << v << ' ';
    cout << endl;
}

struct HASH{
  size_t operator()(const pair<long,long>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

bool pair_sort(const pair<int, int> &p1, const pair<int,int> &p2){
    if(p1.first != p2.first) return p1.first < p2.first;
    else return p1.second < p2.second;
}

const int INF = std::numeric_limits<int>::max();
const ll M_INF = std::numeric_limits<ll>::min();
const ll LL_INF = std::numeric_limits<ll>::max();

void solution();
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solution();
    return 0;
}

void solution(){
  ll k;
  cin >> k;
  
  if(k < 10){
    cout << k << endl;
    return;
  }

  deque<ll> queue;
  for(ll i = 1; i < 10; i++) queue.push_back(i);
  ll index = 9;
  while(queue.size()){
    ll cur = queue.front();
    queue.pop_front();
    ll d = cur%10;
    ll nxt = cur*10;
    if(d != 0){
      index++;
      ll tmp = nxt+d-1;
      if(index == k){
        cout << tmp << endl;
        return;
      }
      queue.push_back(tmp);
    }

    index++;
    ll tmp = nxt+d;
    if(index == k){
      cout << tmp << endl;
      return;
    }
    queue.push_back(tmp);

    if(d != 9){
      index++;
      ll tmp = nxt+d+1;
      if(index == k){
        cout << tmp << endl;
        return;
      }
       queue.push_back(tmp);
    }
  }
}     



Measured memory_bytes: 768
N,W = map(int,input().split())
wv = {}
for i in range(N):
    w,v = map(int,input().split())
    if w not in wv.keys():
        wv[w] = []
    wv[w].append(v)

for w in wv.keys():
    wv[w] = sorted(wv[w],reverse=True)

wv_ruiseki = {}
for w in wv.keys():
    wv_ruiseki[w] = [0,wv[w][0]]
    for i in range(2,len(wv[w])+1):
        wv_ruiseki[w].append(wv_ruiseki[w][i-1] + wv[w][i-1])


w = []
for i in wv.keys():
    w.append(i)

ans = 0
if len(w) == 1:

    for i in range(len(wv[w[0]])+1):
        if w[0]*i <= W:
            ans = max(ans , wv_ruiseki[w[0]][i])
elif len(w) == 2:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            if w[0]*i + w[1]*j <= W:
                ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j])

elif len(w) == 3:

    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                if w[0]*i + w[1]*j + w[2]*k <= W:
                    ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k])
elif len(w) == 4:
    for i in range(len(wv[w[0]])+1):
        for j in range(len(wv[w[1]])+1):
            for k in range(len(wv[w[2]])+1):
                for t in range(len(wv[w[3]])+1):
                    if w[0]*i + w[1]*j + w[2]*k + w[3]*t <= W:
                        ans = max(ans , wv_ruiseki[w[0]][i]+ wv_ruiseki[w[1]][j] + wv_ruiseki[w[2]][k] + wv_ruiseki[w[3]][t])


print(ans)


Measured memory_bytes: 41968
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<int, P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i, x) for (int i = 0; i < x; i++)
#define rep1(i, x) for (int i = 1; i <= x; i++)
#define rrep(i, x) for (int i = x - 1; i >= 0; i--)
#define rrep1(i, x) for (int i = x; i > 0; i--)
#define sor(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define lb(vec, a) lower_bound(vec.begin(), vec.end(), a)
#define ub(vec, a) upper_bound(vec.begin(), vec.end(), a)
#define uniq(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())
#define mp1(a, b, c) P1(a, P(b, c))

const int INF = 1000000000;
const ll M = 1000000000;
const int dir_4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir_8[8][2] = {{1, 0},  {1, 1},   {0, 1},  {-1, 1},
                         {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

/*----------------------------------------------/
/- char         : %c  | char *       : %s  | short        : %hd
/- int          : %d  | long         : %ld | long long    : %lld
/- unsigned short:%hu | unsigned int : %u  | unsigned long: %lu
/- u_long long  : %llu| (octal)      : %o  | (hexadecimal): %x
/- float        : %f  | double       : %lf |
/----------------------------------------------*/

/*----------------------------------------------/
/- INT_MAX, LONG_MAX   : 1<<15 = 2.1*pow(10, 9)       (= 2147483647)
/- UINT_MAX, ULONG_MAX : 1<<16 = 4.2*pow(10, 9)       (= 4294967295)
/- LLONG_MAX           : 1<<63 = 9.2*pow(10, 18)      (= 9223372036854775807)
/- ULLONG_MAX          : 1<<64 = 1.8*pow(10, 19)      (= 18446744073709551615)
/----------------------------------------------*/

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

int main() {
    char c[100];
    rep(i, 10) { cin >> c[i]; }

    int y, m, d;
    y = ctoi(c[0]) * 1000 + ctoi(c[1]) * 100 + ctoi(c[2]) * 10 + ctoi(c[3]) * 1;
    m = ctoi(c[5]) * 10 + ctoi(c[6]) * 1;
    d = ctoi(c[8]) * 10 + ctoi(c[9]) * 1;
    if (y > 2018 && m > 4) {
        cout << "TBD";
    } else if (y > 2019) {
        cout << "TBD";
    } else {
        cout << "Heisei";
    }
    /* ====================================== */
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int a,b;
double c;
int main()
{
	cin>>a>>b;
	c=double(a+b)/2.0;
	//cout<<c<<endl;
	if(c>=(a+b)/2+0.5)cout<<(a+b)/2+1;
	else cout<<(a+b)/2;
	
	
	return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
  public static void main(String args[]){
	  Scanner sc = new Scanner(System.in);
	  int s = sc.nextInt();
	  System.out.println(s / 60 / 60 + ":" + s / 60 % 60 + ":" + s % 60);
	  sc.close();
  }
}


Measured memory_bytes: 26280
#include <stdio.h>
#include <stdlib.h>

typedef struct _vec{
    int *data;
    int cnt;
}VEC;

int main(){
    int i;
    int n,q;
    scanf("%d %d\n",&n,&q);
    
    VEC v[n];
    for(i=0;i<n;i++){
        v[i].cnt=0;
    }
    
    int com,t,x;
    while(q--){
        scanf("%d %d \n",&com,&t);
        switch(com){
            case 0:
                //pushback
                scanf("%d\n",&x);
                if(v[t].cnt==0){
                    v[t].data=(int*)malloc(sizeof(int));
                }else{
                    v[t].data=(int*)realloc(v[t].data,sizeof(int)*(v[t].cnt+1));
                }
                v[t].data[v[t].cnt++]=x;
                break;
            case 1:
                //dump
                if(v[t].cnt!=0)printf("%d\n",v[t].data[v[t].cnt-1]);
                break;
            case 2:
                //clear
                if(v[t].cnt!=0){
                    v[t].data=(int*)realloc(v[t].data,sizeof(int)*(--v[t].cnt));
                }
                break;
        }
    }
    
    for(i=0;i<n;i++){
        if(v[t].cnt!=0){
            free(v[t].data);
            v[t].cnt=0;
        }
    }
    
    return 0;
}


Measured memory_bytes: 2340
N=int(input())
A=[int(x) for x in input().split()]

#1からスタートしてlistの数字だけ左にシフトして論理和を取る。
#例えば1->4を左にシフトして論理和をとると1->10000->（元の1との論理和で）10001。
#さらに例を続ける。この次に5があるとき、10001->1000100000->（同様に）1000110001。
#つまり、スタートの1を除くと、5,6,10桁目にbitが立つ状態になる。
#求めたい部分集合の合計値が作れるかどうかはn+1桁目にbitが立っているかどうかを調べればよい。
#上記例（[4,5]の操作）では5,6,10桁目にbitが立っている＝4,5,9が作れているということ。
bits=1
for b in A:
  bits|=bits<<b

#解説どおり、答えはsum(list)/2以上で作れる部分和の最小値。
#上記bitsの定義を前提にbitsをsum(list)/2桁分だけ右にシフト。
#ココで最下位bitが立っていれば、答えはsum(list)/2。
#あとは1つずつ右にシフトして（答えも+1して）調べていくだけ。
ans=sum(A)
ans=(ans+1)//2
bits >>= ans
while True:
  if bits&1:
    break
  else:
    bits>>=1
    ans+=1
print(ans)

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

signed main(){
  int a=0,cnt=0;
  for(int i=0;i<3;i++){
    char s;cin>>s;
    if(s=='R')a=max(a,++cnt);
    else cnt=0;
  }
  cout<<a<<endl;
}

Measured memory_bytes: 3580
// ABC043_C

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long LL;
#define PB push_back
#define ALL(_v) (_v).begin(), (_v).end()

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    int ans = 0;
    for(int i = -100; i <= 100; i++) {
        int tmp = 0;
        for(int j = 0; j < v.size(); j++) {
            tmp += (v[j] - i) * (v[j] - i);
        }
        if(i == -100) {
            ans = tmp;
        }
        
        if(ans > tmp) {
            ans = tmp;
        }
        
    }
    
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    
    int n,sum=0,a[1000];
    cin>>n;
    for(int i=0 ;i <n;i++)  cin>>a[i];
    
    for(int i=0 ;i <n;i++){
        for(int j=i+1;j<n;j++){
            sum+=(a[i]*a[j]);
        }
    }
    cout<<sum<<"\n";
}

Measured memory_bytes: 256
import sys
import math
input = sys.stdin.readline


def main():
    sc = Scan()
    a, b = sc.intarr()

    ans = (a-1) * (b-1)

    print(ans)


def format_str(num):
    if num < 10:
        return "00" + str(num)
    elif num < 100:
        return "0" + str(num)
    else:
        return str(num)


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


def display(array):
    for a in range(len(array)):
        if len(array) - a != 1:
            print(array[a], end=' ')
        else:
            print(array[a])


def gcd(a, b):  # 最大公約数
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):  # 最小公倍数
    return a * b // gcd(a, b)


main()


Measured memory_bytes: 3064
def hantei(n):
    for i in range(len(n)):
        if n[i]!="A" and n[i]!="G" and n[i]!="T" and n[i]!="C":
            return False

s=input()
T=[]
n=[]
m=[]
x=0

for i in range(len(s)-1):
    for j in range(i+1,len(s)):
        T.append(s[i:j+1])

for i in range(len(s)):
    T.append(s[i])

flag=False
for i in range(len(T)):
    w=T[i]
    if hantei(w)!=False:
        n.append(w)


for i in range(len(n)):
    m.append(len(n[i]))

if not m:
    print(0)
else:
    print(max(m))

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 998244353;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {   
    string T; cin >> T;
    rep(i, T.size()){
        if(T[i]=='?') cout << "D";
        else cout << T[i];
    }
    cout << ln;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
int main()
{
   int a[3][3];

  for(int i=0;i<3;i++)
  {
    for(int j=0;j<3;j++)
    {
       cin>>a[i][j];
    }
  }
  
  int n;
  cin>>n;
  int b[n];

  for(int i=0;i<n;i++)
  {
     cin>>b[i];
  }
  
  for(int i=0;i<3;i++)
  {
    for(int j=0;j<3;j++)
    {
      for(int x =0;x<n;x++)
      {
         if(a[i][j]==b[x])
           a[i][j]=0;
      }
    }
  }

  bool ju = false;
  
  rep(i,3)
  {
    
     if(a[0][i]==0)
     {
        if(a[1][i]==0)
        {
           if(a[2][i]==0)
           {
              ju = true;
              break;
           }
        }
     }
  }
  
  if(!ju)
  {
    rep(i,3)
  {
    
     if(a[i][0]==0)
     {
        if(a[i][1]==0)
        {
           if(a[i][2]==0)
           {
              ju = true;
              break;
           }
        }
     }
  }
  }
  
  if(!ju)
  {
     if(a[0][0]==0&&a[1][1]==0&&a[2][2]==0)
     {
       ju = true;
     }
    
     if(a[0][2]==0&&a[1][1]==0&&a[2][0]==0)
     {
       ju = true;
     }
  }
  
  cout<<(ju?"Yes":"No")<<endl;
  
  return 0;
  
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<complex>
#include<stack>
   
using namespace std;
   
int main(){
       
    int n;
    cin>>n;
       
    while(n-- > 0){
        vector<int> ans;
        vector<int> a;
        vector<int> b;
           
        string c,d;
        cin>>c>>d;
           
        for(int i = 0; i < (int)c.size(); ++i){
            a.push_back(c[c.size()-1-i]-'0');
        }
        for(int i = 0; i < (int)d.size(); ++i){
            b.push_back(d[d.size()-1-i]-'0');
        }
           
           
        int kuri = 0;
        while(!a.empty() || !b.empty() || kuri!=0){
            int sum = kuri;
            kuri = 0;
               
            if(!a.empty()){
                sum += a[0];
                a.erase(a.begin());
            }
               
            if(!b.empty()){
                sum += b[0];
                b.erase(b.begin());
            }
               
            ans.push_back(sum%10);
            kuri += sum/10;
        }
           
        if(ans.size()>80)puts("overflow");
        else{
            for(int i = 0; i < (int)ans.size(); ++i){
                printf("%d",ans[ans.size()-1-i]);
            }puts("");
        }
    }
       
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    int A[2], K; cin >> A[0] >> A[1] >> K;
    int i = 0;
    while (K--) {
        if (A[i] % 2) A[i]--;
        A[i] = A[i] / 2;
        A[!i] += A[i];
        i = !i;
    }
    cout << A[0] << ' ' << A[1] << '\n';
    return 0;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include<iostream>
#include<vector>

using namespace std;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
#define rep(i, n) for (i32 i = 0; i < (i32)(n); i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using P = pair<i64, i64>;

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    i32 n;
    cin >> n;
    i32 sum = 0;
    i32 i = 0;
    while (sum <= n) {
        i++;
        sum = i * (i - 1) / 2;
        if (sum == n) {
            break;
        }
    }
    if (sum != n) {
        cout << "No" << endl;
        return 0;
    }
    i--;
    vector<vector<i32>> table(i);
    i32 val = 1;
    rep(j, i) {
        rep(k, j + 1) {
            table[j].emplace_back(val);
            val++;
        }
    }
    cout << "Yes" << endl;
    cout << i + 1 << endl;
    cout << i << " ";
    rep(j, i) {
        cout << table[j][0] << " \n"[j == i - 1];
    }
    for (i32 j = 1; j < i; j++) {
        cout << i << " ";
        bool flag = false;
        i32 col = j, row = 0;
        rep(k, i) {
            if (flag) {
                cout << table[col][row] << " \n"[k == i - 1];
                col++;
            } else {
                cout << table[col][row] << " \n"[k == i - 1];
                if (table[col][row] == table[col].back()) {
                    flag = true;
                    col++;
                } else
                    row++;
            }
        }
    }
    cout << i << " ";
    rep(j, i) {
        cout << table[j][j] << " \n"[j == i - 1];
    }
    /*rep(j,i) {
        for (auto v:table[j])cout << v << " \n"[v == table[j].back()];
    }*/
}

Measured memory_bytes: 4188
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>


std::vector<std::vector<int>> edge;
std::vector<std::pair<int, int>> range;
std::vector<int> res;
constexpr int inf = std::numeric_limits<int>::max();
constexpr std::pair<int, int> all_ok(-1, -1);
constexpr std::pair<int, int> ng(inf, inf);


bool merge(std::pair<int, int>& x, const std::pair<int, int>& y){
    if(y == ng){ x = ng; return false; }
    if(y == all_ok) return true; 
    if(x == all_ok){ x.first = y.first - 1; x.second = y.second + 1; return true; }
    if((x.first & 1) ^ (y.first & 1)){
        if(x.first  < y.first  - 1) x.first  = y.first  - 1;
        if(x.second > y.second + 1) x.second = y.second + 1;
        if(x.first > x.second){ x = ng; return false; }
        return true;
    }
    x = ng;
    return false;
}

bool dfs1(const int v, const int par = -1){
    for(const int nv : edge[v]) if(nv != par){
        dfs1(nv, v);
        if(not merge(range[v], range[nv])) return false;
    }
    return true;
}

void dfs2(const int v, const int par = -1){
    for(const int nv : edge[v]) if(nv != par){
        res[nv] = (range[nv].first <= res[v] - 1) ? res[v] - 1 : res[v] + 1;
        dfs2(nv, v);
    }
}

int main(void){
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(16);
    
    int n; std::cin >> n;
    edge.assign(n, std::vector<int>());
    for(int i = 1; i < n; ++i){
        int u, v; std::cin >> u >> v; --u; --v;
        edge[u].push_back(v); edge[v].push_back(u);
    }
    
    range.assign(n, all_ok);
    int m; std::cin >> m;
    for(int i = 0; i < m; ++i){ 
        int v, p; std::cin >> v >> p; --v;
        range[v].first = p; range[v].second = p;
    }
    if(not dfs1(0)){ std::cout << "No\n"; return 0; }
    std::cout << "Yes\n";
    res.resize(n); res[0] = range[0].first;
    dfs2(0);
    for(int i = 0; i < n; ++i) std::cout << res[i] << '\n';
  
    return 0;
}

Measured memory_bytes: 16160
def main():
    L = input()
    MOD = 10 ** 9 + 7
    dp = [[0] * 2 for _ in range(10 ** 6 + 5)]
    dp[0][0] = 1
    for i in range(len(L)):
        # a + b = 0
        if L[i] == '0':
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
        else:
            dp[i+1][1] = (dp[i][0] + dp[i][1]) % MOD
        
        # a + b = 1
        if L[i] == '0':
            dp[i+1][1] += dp[i][1] * 2 % MOD
            dp[i+1][1] %= MOD
        else:
            dp[i+1][0] += dp[i][0] * 2 % MOD
            dp[i+1][1] += dp[i][1] * 2 % MOD
            dp[i+1][0] %= MOD
            dp[i+1][1] %= MOD

    ans = (dp[len(L)][0] + dp[len(L)][1]) % MOD
    print(ans)
    

if __name__ == "__main__":
    main()

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

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

#define FOR(i, s, e) for (ll(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (ll(i) = (s); (i) > (e); (i)--)
#define debug(x) cout << #x << ": " << x << endl
#define mp make_pair
#define pb push_back
const ll MOD = 1000000007;
const int INF = 1e9;
const ll LINF = 1e16;
const double PI = acos(-1.0);
int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/10/08  Problem: codefestival2017_qual B  / Link:   ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

ll N,M;

ll ans = 0LL;
ll d[200002];
ll t[200002];

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


	map<ll, ll>ma;
	cin >> N;
	FOR(i, 0, N) {
		cin >> d[i];
		ma[d[i]]++;
	}
	cin >> M;
	bool f = 1;
	FOR(i, 0, M) {
		cin >> t[i];
		if (ma[t[i]] >= 1) {
			ma[t[i]]--;
		}
		else {
			f = 0;
		}
	}


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

	return 0;
}


Measured memory_bytes: 15872
n = int(input())
r = [int(input()) for i in range(n)]

rmin = r[0]
rmax = r[1] - r[0]
for i in range(1,len(r)):
    if rmin > r[i]:
        rmin = r[i]
    else:
        rmax = max(rmax,r[i] - rmin)

print(rmax)


Measured memory_bytes: 13596
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    ll n,m,d;
    cin>>n>>m>>d;
    cout<<fixed;
    cout<<setprecision(10);
    if (d==0)
        cout<<(1.0/n)*(m-1)<<endl;
    else
        cout<<(2.0*(n-d))/(n*n)*(m-1)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(c) c.begin(),c.end()
#define PB push_back

using namespace std;
typedef long long ll;

int main()
{
  int N; cin >> N;
  int b4 = 0, b2 = 0, odd = 0;
  REP(i, N) {
    int A; cin >> A;
    if (A % 4 == 0) b4++;
    else if (A % 2 == 0) b2++;
    else odd++;
  }
  if (b2 > 0) odd++;
  if (b4 + 1 >= odd) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

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

using namespace std;

#define REP(i,first,last) for (int i=first;i<last;i++)
#define MAX(x,y) (x > y ? x : y)
#define MIN(x,y) (x < y ? x : y)
#define prints(str) cout << str << " ";
#define printn(str) cout << str << endl;

int main(){
  int N,K;
  cin >> N >> K;
  bitset<5001> dp;
  dp[0] = 1;
  vector<int> card_list;

  REP(i,0,N){
    int val;
    cin >> val;
    if (val < K) {
      card_list.push_back(val);
    }
  }
  sort(card_list.begin(), card_list.end(), greater<int>());

  int ans = 0;
  for (auto card: card_list) {
    ++ans;
    for (int i=K-card;i<K;++i) {
      if (dp[i]) {
        ans = 0;
        break;
      }
    }
    dp |= dp << card;
  }
  printn(ans);
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		long s1 = sc.nextLong();
		long s2 = sc.nextLong();
		for(int i = 1; i<N; i++){
			long x1 = sc.nextLong();
			long x2 = sc.nextLong();
			long val1 = s1 / x1;
			long val2 = s2 / x2;
			if(val1 == 0){
				val1 = 1;
				s1 = x1;
			}
			if(val2 == 0){
				val2 = 1;
				s2 = x2;
			}
			if(s1 % x1 != 0){
				val1++;
				s1 = val1 * x1;
			}
			if(s2 % x2 != 0){
				val2++;
				s2 = val2 * x2;
			}
			if(val1 > val2){
				s2 = val1 * x2;
			}
			else if(val2 > val1){
				s1 = val2 * x1;
			}
		}
		long res = s1 + s2;
		System.out.println(res);
	}
}

Measured memory_bytes: 25168
n, q = map(int,input().split())
graph = [[] for i in range(n+1)]
for i in range(n-1):
    f, t = map(int,input().split())
    graph[f].append(t)
    graph[t].append(f)

px = [0] * (n+1)
for i in range(q):
    p, x = map(int,input().split())
    px[p] += x

v = [0] * (n+1)
q = [[1,0]]
while q:
    x, parent = q.pop()
    v[x] += v[parent]
    v[x] += px[x]
    for y in graph[x]:
        if y == parent:
            continue
        q.append([y,x])

ans = [str(i) for i in v[1:]]
print(' '.join(ans))

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


#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define pb push_back
#define inf 1e9+11
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;

void pre(){
}

void solve(){
	ll n; cin >> n;
	ll m[n][3]; rep(i,n) rep(j,3) cin >> m[i][j];
	ll score[n][3];
	memset(score, 0x00, sizeof(score));
	rep(i,n){
		if(i == 0){
			score[i][0] = m[i][0];
			score[i][1] = m[i][1];
			score[i][2] = m[i][2];
		}
		else rep(j,3){
				score[i][j] = max(score[i-1][(j+1)%3] + m[i][j], score[i-1][(j+2)%3] + m[i][j]  ); 
			}
	}
	ll mv2 = max(score[n-1][0], score[n-1][1]);
	ll mv =  max( mv2, score[n-1][2] );
	cout << mv << endl;
}
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	solve();	
	return 0;
}




Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(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 fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}


int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int a = x2 - x1;
	int b = y2 - y1;
	cout << x2 - b << " " << y2 + a << " " << x1 - b << " " << y1 + a << endl;
}


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

r = [None] * N
# A = A[::-1]  # 扱いやすくするためにひっくり返す

# nの倍数の箱に入っているボールの個数
# (nは含まない)
def f(n):
    i = 2
    cnt = 0
    while n * i <= N:
        # print('-', n, i, r)
        cnt += r[(n * i)-1]
        i += 1
    # print('--', n, cnt, r)
    return cnt

n = N
while n > 0:
    c = f(n)
    # print(n, c, A[n-1])
    if c % 2 == A[n-1]:
        r[n-1] = 0
    else:
        r[n-1] = 1
    n -= 1

# print(r)

r_a = []
r_cnt = r.count(1)
print(r_cnt)
for i, ri in enumerate(r):
    if ri == 1:
        r_a.append(str(i+1))

if r_cnt != 0:
    print(" ".join(r_a))



Measured memory_bytes: 17204
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int K = sc.nextInt();
        int N = sc.nextInt();
        int[] A = new int[N];
        Integer[] D = new Integer[N];

        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        for (int i = 0; i < N - 1; i++) {
            D[i] = A[i + 1] - A[i];
        }

        D[N - 1] = K - A[N - 1] + A[0];

        Arrays.sort(D, Comparator.reverseOrder());

        System.out.println(K - D[0]);
    }
}


Measured memory_bytes: 83356
for i in range(int(input())):
    y, m, d = map(int, input().split())
    print(196471 - ((y - 1) * 195 + (y - 1) // 3 * 5 + 20 * (m - 1) - min(1, y % 3) * ((m - 1) // 2) + d))



Measured memory_bytes: 5592
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

mint pw(mint a, ll b) {
	if (b == 0) { return 1; }
	mint ret = pw(a, b >> 1);
	ret *= ret;
	if (b & 1) { ret *= a; }
	return ret;
}

typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;

typedef vector<mint> vmint;
typedef vector<vector<mint>> vvmint;
typedef vector<vector<vector<mint>>> vvvmint;

//////////////////////////////////////


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

	vvll dp(N + 1, vll(3, 0));

	repn(i, N) {
		ll a[3];
		rep(j, 3) cin >> a[j];

		rep(j, 3) {
			dp[i][j] = max(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + a[j];
		}
	}

	cout << max<ll>({ dp[N][0],dp[N][1],dp[N][2] });
}



Measured memory_bytes: 8784
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N=2e5+10;
int n;
long long k,sum=0;
long long a[N],b[N],f[N];

bool cmp(long long a,long long b)
{
	return a>b;//
}
bool check (long long x)
{
	for (int i=1;i<=n;++i)
	{
		f[i]=x/b[i];//x为最大的a[i]*b[i]所以f[i]>=a[i] 
	}
	
	long long res=0;
	
	for (int i=1;i<=n;++i)
	{
		res+=max(0ll,a[i]-f[i]);//a[i]-f[i]<=0
	}
	
	return res<=k;
}
long long BS()
{
	long long l=0,r=1e12;
	
	while (l+1<=r)
	{
		long long mid=l+r>>1;
		if (check(mid))
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	return r;
}
int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;++i)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for (int i=1;i<=n;++i)
	{
		cin>>b[i];
	}
	if (sum<=k)
	{
		cout<<"0";
		return 0;
	}
	sort(a+1,a+1+n);//a从小到大排 
	sort(b+1,b+1+n,cmp);//b从大到小排 
	cout<<BS();
	return 0;
}

Measured memory_bytes: 4992
W=87,i,n;char a[100001],s[100001];f(x,y){*a=x;a[1]=y;for(i=1;i<n-1;i++)a[i+1]=a[i]==W^a[i-1]==W^s[i]=='o'?83:W;if(*a==W^*s=='o'^a[n-1]==a[1]|a[n-1]==W^s[n-1]=='o'^a[n-2]==*a)return;puts(a);exit(0);}main(){scanf("%d%s",&n,&s);f(83,83);f(83,W);f(W,83);f(W,W);puts("-1");}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
ll mod=1e9+7;
int main()
{
    ll a,b,x;
    cin>>a>>b>>x;
    ll p=b/x;
    p-=a/x;
    if(a%x==0)
    p++;
    cout<<p<<endl;
}

Measured memory_bytes: 3600
from collections import Counter
max_=10**6+1
ans=0

n=int(input())
data=list(map(int,input().split()))

b=[True]*(max_+1)
data.sort()
c=Counter(data)
#print(c)

for d in data:
    if b[d]:
        for j in range(d,max_,d):
            b[j]=False
        if c[d]==1:#複数存在考慮
            ans+=1
print(ans)


Measured memory_bytes: 43756
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, H, W; cin >> N >> H >> W;
  int ans = (N-H+1)*(N-W+1);
  cout << ans << endl;
}

Measured memory_bytes: 3572
#include<stdio.h>
#include<stdlib.h>

#define Ni 3

int pzl[Ni][Ni],tmp[Ni][Ni];
int Dx[4]={0,1,0,-1},Dy[4]={1,0,-1,0};

void emblem(int *a,int *b){
  int i,j;
  for(i=0;i<3;i++){
    for(j=0;j<3;j++){
      if(!pzl[i][j]){
	*a = j;
	*b=i;
      }
    }
  }
}

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

int check(){
  int i,A,S=0;
  for(i=0;i<9;i++){
    A = pzl[i/3][i%3];
    if(A){
      A--;
      S += abs(i/3-A/3) + abs(i%3 - A%3);
    }
  }
  
  return S;
}

int defain(int a,int b,int P,int D,const int shin){
  int i,hi,A,B,result;
  hi = check();
  if(hi==0){
    return D;
  }
  
  if(D+hi>shin){
    return -1;
  }

  for(i=0;i<4;i++){
    A = a+Dx[i];
    B = b+Dy[i];
    if(~P && i==(P+2)%4) {
      continue;
    }
    if(!(0<=A && A<3 && 0<=B && B<3)){
      continue;
    }
    swap(&pzl[b][a],&pzl[B][A]);
    result = defain(A,B,i,D+1,shin);
    if(~result){
      return result;
    }
    swap(&pzl[b][a],&pzl[B][A]);
  }
  
  return -1;
  
}

int main(){
  int i,j,li,TA,a,b;

  for(i=0;i<3;i++){
    for(j=0;j<3;j++){
      scanf("%d",&pzl[i][j]);
    }
  }

  emblem(&a,&b);
  for(li=0;li<100;li++){
    for(i=0;i<3;i++){
      for(j=0;j<3;j++){
	tmp[i][j]=pzl[i][j];
      }
    }
    
    TA = defain(a,b,-1,0,li);
    if(TA!=-1){
      printf("%d\n",TA);
      break;
    }

    for(i=0;i<3;i++){
      for(j=0;j<3;j++){
	pzl[i][j]=tmp[i][j];
      }
    }

    TA = -1;
    if(li==99){
      printf("%d\n",TA);
    }
  }

  return 0;
}




Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N; cin >> N;
    int tmp = N;
    if(N == 0){
        cout << 0 << endl;
    }else{
        int ans[100];
        int *ansptr = ans;
        for(int i = 0; i < 100; i++) ans[i] = -10;
        ansptr++;
        while(tmp != 0){
            if(tmp >= 0){
                *ansptr = tmp%2;
                tmp -= tmp%2;
                tmp = tmp/2*(-1);
            }else{
                *ansptr = tmp*(-1)%2;
                tmp -= tmp*(-1)%2;
                tmp *= -1;
                tmp = tmp/2;
            }
            ansptr++;
        }
        ansptr--;
        while(*ansptr != -10){
            cout << *ansptr;
            ansptr--;
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#include<iomanip>

using namespace std;
int main(void){
 int N;
 double T,A,H;
 int ans=0;
 double min=10000000;
 cin>>N>>T>>A;

 for(int i=0; i<N; i++){
  cin>>H;
  if(min>fabs(A-(T-H*0.006))){
   min=fabs(A-(T-H*0.006));
   ans=i+1;
  }
 }
 std::cout<<ans<<std::endl;
 return 0;
}

Measured memory_bytes: 256