akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int insertionSort(int *,int,int);
int main (){
    int n,x[1000000],i,j,cnt=0,m,g[100];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&x[i]);
    }
    j=0;
    for(i=1;i<=n;i=3*i+1){
        g[j]=i;
        j++;
        cnt++;
    }
    m=cnt;
    cnt=0;
    for(i=1;i<=m;i++){
        cnt=insertionSort(x,n,g[m-i]);
    }
    printf("%d\n",m);
    for(i=1;i<=m;i++){
        if(i-1){
            printf(" ");
        }
        printf("%d",g[m-i]);
    }
    printf("\n");
    printf("%d\n",cnt);
    for(i=0;i<n;i++){
        printf("%d\n",x[i]);
    }
    return 0;

}

int insertionSort(int *x,int n,int g){
    int i,v,j;
    static int cnt;
    for(i=g;i<n;i++){
        v=x[i];
        j=i-g;
        while((j>=0) && (x[j]>v)){
            x[j+g]=x[j];
            j=j-g;
            cnt++;
        }
        x[j+g]=v;
    }
    return cnt;
}


Measured memory_bytes: 5700
#問題C
N = int(input())

naka=0
a_kazu=0
b_kazu=0
b_a_kazu=0
for i in range(N):
    a = str(input())
    naka+=a.count("AB")
    if (a[0]=="B" and a[-1]=="A"):
        b_a_kazu+=1
    elif a[0]=="B":
        b_kazu+=1
    elif a[-1]=="A":
        a_kazu+=1
if b_a_kazu==0:
    print(naka+min(a_kazu, b_kazu))
else:
    if (a_kazu==0 and b_kazu==0):
        print(naka+(b_a_kazu-1))
    elif (a_kazu==0 or b_kazu==0):
        print(naka+(b_a_kazu))
    else:
        print(naka+(b_a_kazu-1)+min(a_kazu+1, b_kazu+1))

Measured memory_bytes: 3064
#include<stdio.h>
int main(){
	int H,W,a[101][101],i,j;
	scanf("%d %d",&H,&W);
	for(j=0;j<W;j++)a[H][j]=0;
	for(i=0;i<H;i++)a[i][W]=0;
	a[H][W]=0;
	for(i=0;i<H;i++){
		for(j=0;j<W;j++){
			scanf("%d",&a[i][j]);
			a[i][W]+=a[i][j];
			a[H][j]+=a[i][j];
		}
	}
	for(i=0;i<W;i++)a[H][W]+=a[H][i];
	for(i=0;i<=H;i++){
		for(j=0;j<=W;j++){
			if(j!=W)printf("%d ",a[i][j]);
			else printf("%d\n",a[i][j]);
		}
	}
	return 0;
}
			
		
		

Measured memory_bytes: 636
n,k,q = map(int,input().split())
l = [0 for x in range(n)]
for _ in range(q):
    l[int(input())-1] += 1

ans = []
for i in l:
    if k- q + i > 0:
        ans.append("Yes")
    else:
        ans.append("No")
print("\n".join(ans))

Measured memory_bytes: 5912
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N;
i64 A[202020], B[202020];

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%lld%lld", A + i, B + i);

	i64 gt = 0, gm = 1LL << 60LL;
	i64 eq = 0, le = 0;
	for (int i = 0; i < N; ++i) {
		if (A[i] > B[i]) {
			gt += A[i];
			gm = min(gm, B[i]);
		} else if (A[i] == B[i]) {
			eq += A[i];
		} else {
			le += A[i];
		}
	}

	i64 ret = le;
	if (gt > 0) {
		ret += eq + gt - gm;
	}
	printf("%lld\n", ret);

	return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	
	int n;
	cin >> n;
	vector<vector<int>> x(n), y(n);
	rep(i, n){
		int a;
		cin >> a;
		rep(j, a){
			int tmp_x, tmp_y;
			cin >> tmp_x >> tmp_y;
			tmp_x--;
			x[i].push_back(tmp_x);
			y[i].push_back(tmp_y);
		}
	}
	int ans = 0;
	for(int bit=0; bit<(1<<n); bit++){
		bool ok = true;
		rep(i, n){
			if((bit & (1<<i))==0) continue;
			if(!ok) break;
			for(int j = 0; j < x[i].size(); j++){
				if(!!(bit & (1 << x[i][j])) != y[i][j]){
					ok = false;
					break;
				}
			}
		}
		if(!ok) continue;
		int cnt = 0;
		rep(j, n){
			if(bit & (1 << j)) cnt++;
		}
		if(ans < cnt) ans = cnt;
	}
	cout << ans << endl;
	return 0;
}

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


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

  vector<int> A(N,0);

  for(int i = 0;i < K;i++) {
    int d;
    cin >> d;
    for(int j = 0;j < d;j++) {
      int a;
      cin >> a;
      A[a-1]++;
    }
  }

  int ans = 0;
  for(int i = 0;i < N;i++) {
    if(A[i] == 0) ans++;
  }
  cout << ans << endl;

}


Measured memory_bytes: 3628
#include <iostream>
#include <algorithm>
#include <string>

using std::cin;
using std::cout;
using std::endl;

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

  if (r < 1200) {
    cout << "ABC" << endl;
  }
  else if (r < 2800) {
    cout << "ARC" << endl;
  }
  else {
    cout << "AGC" << endl;
  }


  return 0;
}


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

int main() {
  int A,B,C,K;
  cin>>A>>B>>C>>K;
  int ans;
  if(K<=A) ans=K;
  else if(A<K && K<=(A+B)) ans=A;
  else ans=(2*A+B-K);
  cout<<ans<<endl;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <math.h>
int main(void){
    
    int k;
    int x;
    
    scanf("%d%d", &k, &x);
    
    for(int i=x-k+1; i<x+k; i++){
        
        printf("%d ", i);
        
    }
    
    return 0;
    
}

Measured memory_bytes: 128
class Tree:
    def __init__(self, ary):
        self.nodes = [
            Node(node, self) for node in sorted(ary, key=lambda x: x[0])
        ]
        [node.set() for node in self.nodes]
        for node in self.nodes:
            if node.parent == -1:
                node.set_depth(0)
                break

    def output(self):
        [node.output() for node in self.nodes]


class Node:
    def __init__(self, node, tree):
        self.tree = tree
        self.no = node[0]
        self.parent = -1
        self.right = False
        self.left = False
        self.children = node[2:]

    def set(self):
        if self.children:
            for i, child in enumerate(self.children):
                self.tree.nodes[child].parent = self.no
                if i < len(self.children) - 1:
                    self.tree.nodes[child].right = self.children[i + 1]
                self.left = self.children[0]

    def set_depth(self, d):
        self.depth = d
        if type(self.right) != bool:
            self.tree.nodes[self.right].set_depth(d)
        if type(self.left) != bool:
            self.tree.nodes[self.left].set_depth(d + 1)

    def output(self):
        if self.parent == -1:
            kind = 'root'
        elif not self.children:
            kind = 'leaf'
        else:
            kind = 'internal node'

        print('node {}: parent = {}, depth = {}, {}, {}'.format(
            self.no, self.parent, self.depth, kind, self.children))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 6)

    n = int(input())
    ary = [[int(_) for _ in line.strip().split()] for line in sys.stdin]
    # ary = [[int(_) for _ in input().split()] for i in range(n)]
    tree = Tree(ary)
    tree.output()



Measured memory_bytes: 145668
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
//const ll MOD=(ll)998244353;
const ll INF=(ll)1e18+10;
const double PI = 2.0*acos(0);

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 (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

void solve(int ca){
    mp::cpp_dec_float_100 x,y = 2.0f;
    cin>>x>>y;

    cout<<mp::cpp_dec_float_50(mp::floor(x*y)).str()<<endl;

}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    int ans = 1;
    for (int i = 0; i < N; i++) ans *= 3;
    int ban = 1;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        ban *= 2-a%2;
    }
    cout << ans-ban << endl;
    return 0;
}

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

int main() {
  int A,B;
  cin >> A >> B;
  int ans = 0;
  for (int i=A; B >= i; i++){
    if (i/10000 == i%10 && i/10%10 == i/1000%10){
      ans +=1;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
package main
import (
    "fmt"
    "math"
)
func main(){
    var N,K,ans float64
    fmt.Scan(&N, &K)
    for i:=1.0;i<=N;i++{
        for j, k:=0.0, i;;j, k = j+1, k*2{
            if k>=K{
                ans +=  math.Pow(0.5, j) / N
                break
            }
        }
    }
    fmt.Println(ans)
}


Measured memory_bytes: 512
n = int(input())
l = list(map(int, input().split()))
pre_pre = l[0]
pre = l[1]
count = 0
for i in range(2, n):
    cur = l[i]
    if pre_pre < pre < cur or cur < pre < pre_pre:
        count += 1
    pre_pre = pre
    pre = cur
print(count)


Measured memory_bytes: 38256
import java.util.*;

class Main {
  static String[] strs={
    "dream",
    "dreamer",
    "erase",
    "eraser"
  };

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

    while (true) {
      boolean endsWithStr=false;
      for (String str: strs) {
        if (S.endsWith(str)) {
          endsWithStr=true;
          S=S.substring(0,S.length()-str.length());
          break;
        }
      }
      if (!endsWithStr) {
        System.out.println("NO");
        break;
      }
      if (S.length()<=0) {
        System.out.println("YES");
        break;
      }
    }
  }
}


Measured memory_bytes: 55960
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fr(i,n) for(i=0;i<n;i++)
int main()
{
    set<string>s;
    int n;
    string ss;
    cin>>n;
    while(n--)
    {
        cin>>ss;
        s.insert(ss);
    }
    cout<<s.size();
}




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

int main() {
    long long n, c, k;
    cin >> n >> c >> k;
    vector<int> t(n);
    for(int i = 0; i < n; ++i) cin >> t[i];
    
    sort(t.begin(), t.end());
    
    int res = 0;
    for(int i = 0; i < n;) {
        int start = i;
        while(i < n && t[i] <= t[start] + k && i - start < c) ++i;
        
        ++res;
    }
    
    cout << res << endl;
}


Measured memory_bytes: 640
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const int INF = (1LL << 60); // 1152921504606846976
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
int nmax=200000; // 2*(10^5)
vvec g(nmax);



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    string s;
    cin>>s;
    int c=INF;
    int f=-1;
    rep(i,s.size()){
        if(s[i]=='C'){
            c=min(c,i);
        }
        if(s[i]=='F'){
            f=max(f,i);
        }
    }
    if(c<f) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 4992
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> pll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define re0 return 0
#define exout(x) printf("%.10f\n", x)
#define pb push_back
const ll mod = 1000000007;
const ll INF = 1e16;

int main() {
    ll n; 
    double a, b, c = 0, ans;
    cin >> n;

    rep(i, n) {
        cin >> a;
        b = 1.0/a;
        c += b;
    }

    ans = 1.0/c;

    exout(ans);
    re0;
}

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

using namespace std;
using ll =long long;
using db = double;

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

#define che(a,string) cout<<"//"<<string <<"=="<<(a)<<"//" <<endl;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define leftunique(v) SORT(v);(v).erase(unique((v).begin(),(v).end()),(v).end())
//leftuniqueは配列から同じ要素のものを取り除く 例 4 6 2 1 3 4 1 2 なら 1 2 3 4 6 になる
bool IsInt(double a){int b = a/1;if(a==b){return true;}else {return false;}}
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}
const int mod = 1e9 + 7;
const ll INF = 1LL << 60;

ll dp[110][100100] = {0}  ;
//ここから書き始める
int main()
{
	cout << setprecision(10);
	ll n , w; 
	cin >> n >> w;

	vector<ll> weight(110), value(110);
	rep(i,n) cin >> weight.at(i) >> value.at(i);

	for(int i = 0 ; i <=n ; i++){
		for(int sum_w = 0; sum_w <= w; sum_w ++){
			if(i == 0) dp[0][sum_w] =0 ;
			//i = 1 から、1番目の品物を入れるかどうかの選択をする

			//sum_wからi番目の品物の重さを引いた値が0以上なら品物を取ったほうが良い
			else if(sum_w - weight[i-1] >= 0){
				chmax(dp[i][sum_w], dp[i-1][sum_w -weight.at(i-1)] + value.at(i-1));
			}
			//取らないor取った結果、1個前の品物取ったほうが価値が高かった。ってときはdp[i-1][sum_w]を採用する
			if(i!=0)chmax(dp[i][sum_w],dp[i-1][sum_w]);
		}
	}
	cout << dp[n][w] << endl;

}


Measured memory_bytes: 80128
import java.util.Scanner;

class Main
{
    public static void main(String[] args)
    {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] b = new int[110];
      for (int i=0; i<n-1; i++) b[i] = sc.nextInt();
      int sum = 2*b[0];
      if(n>2) {
        for (int i=1; i<n-1; i++) {
           if(b[i]>=b[i-1]) sum += b[i]; 
           else sum += 2*b[i]-b[i-1];
        }
      }
      System.out.println(sum);
    }
}



Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
const ll INF = 1LL << 60;

int main() {
    int d; cin >> d;
    string s = "Christmas";
    int n = 25 - d;
    for (int i = 0; i < n; i++) {
        s += " Eve";
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
	char s[99];
	char*t="YAKI";
	scanf("%s",s);
	
	int flag=1;
	for(int i=0;i<4;i++)if(s[i]!=t[i])flag=0;
	puts(flag?"Yes":"No");
}

Measured memory_bytes: 128
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	luca := make([]int, n+1)
	luca[0] = 2
	luca[1] = 1
	for i := 2; i <= n; i++ {
		luca[i] = luca[i-1] + luca[i-2]
	}
	fmt.Println(luca[n])
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <cctype>
using namespace std;
 
#define MD 1000000007
typedef long long int ll;

int main(){
    ll x,y;
    cin>>x>>y;
    int ans=0;
    while(x<=y){
        x*=2;
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let mut itr = s.split_whitespace().map(|e| e.parse::<i64>().unwrap());
    let a: i64 = itr.next().unwrap();
    let b: i64 = itr.next().unwrap();

    println!("{}", if a <= b { "unsafe" } else { "safe" });
}


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

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  int i, j;

  for ( ; ; )
  {
    char d[ 8 ], s[ 8 ];
    int hit   = 0
      , blow  = 0;

    scanf ( " %s %s", d, s );
    if ( !( strcmp ( d, "0" ) || strcmp ( s, "0" ) ) )  break ;

    for ( i = 0; i < 4; ++i )
    {
      hit += !!( d[ i ] == s[ i ] );
    }

    for ( j = 0; j < 4; ++j )
    for ( i = 0; i < 4; ++i )
    {
      if ( j == i ) continue ;

      blow += !!( d[ j ] == s[ i ] );
    }

    printf ( "%d %d\n", hit, blow );
  }

  return ( 0 );
}

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

int main(){
	string s;
  	cin>>s;
  	long long int sum=0;
  	for(char c : s){
    	sum+=(c-'0');
    }
  	if(sum%9ll==0)
      cout<<"Yes";
  	else
      	cout<<"No";
}

Measured memory_bytes: 3728
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct turtle{
	double x, y, angle;
};

double rad (double dig){
	return dig * M_PI / 180;
}

void move (struct turtle *t, double len){
	t->x += len * cos (rad (t->angle));
	t->y += len * sin (rad (t->angle));
}

void turn (struct turtle *t, double dig){
	t->angle += dig;
}

int main(void) {
	int l, d;
	struct turtle *T;

	T = (struct turtle*) malloc (sizeof (struct turtle));
	T->x = 0;
	T->y = 0;
	T->angle = 90;

	while (1){
		scanf ("%d,%d", &l, &d);
		if (l==0 && d==0) break;
		move (T, l);
		turn (T, d * -1);
	}
	printf ("%d\n%d\n", (int)T->x, (int)T->y);
	free (T);
	return 0;
}

Measured memory_bytes: 0
fun main(args: Array<String>) {
    val S = readInputLine()

    if (S == "zyxwvutsrqponmlkjihgfedcba") {
        println(-1)
        return
    }

    val used = BooleanArray(26)

    S.forEach { used[it - 'a'] = true }

    if (S.length != 26) {
        for (i in 0 until 26) {
            if (!used[i]) {
                println(S + ('a' + i).toString())
                return
            }
        }
    } else {
        val Sarr = S.toCharArray()

        for (i in 26 - 1 downTo 0) {
            for (j in Sarr[i] + 1..'z') {
                if (!used[j - 'a']) {
                    Sarr[i] = j
                    for (k in 0..i) {
                        print(Sarr[k])
                    }
                    println()
                    return
                }
            }
            used[Sarr[i] - 'a'] = false
        }
    }
}

fun readInputLine(): String {
    return readLine()!!
}


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

int main()
{
    int h, w;
    cin >> h >> w;
    char mat[h][w];
    int dp[h][w];

    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> mat[i][j];
        }
    }

    for (int i = 0; i < w; i++)
        dp[0][i] = (mat[0][i] == '0');
    for (int i = 1; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            if (mat[i][j] == '0')
                dp[i][j] = dp[i - 1][j] + 1;
            else
                dp[i][j] = 0;
        }
    }

    int ans = -1;
    for (int i = 0; i < h; i++)
    {
        // pair<left end, height>
        stack<pair<int, int>> s;
        for (int j = 0; j < w; j++)
        {
            if (s.empty())
            {
                s.push({j, dp[i][j]});
            }
            else if (dp[i][j] > s.top().second)
            {
                s.push({j, dp[i][j]});
            }
            else if (dp[i][j] == s.top().second)
            {
                // do nothing.
            }
            else if (dp[i][j] < s.top().second)
            {
                int left;
                while (!s.empty() && dp[i][j] < s.top().second)
                {
                    pair<int, int> now = s.top();
                    s.pop();
                    // make rectangle
                    ans = max(ans, (j - now.first) * (now.second));
                    left = now.first;
                }
                s.push({left, dp[i][j]});
            }
        }

        while (!s.empty())
        {
            pair<int, int> now = s.top();
            s.pop();
            ans = max(ans, (w - now.first) * (now.second));
        }
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 12584
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
    int N;
    cin >> N;
    int count = 0;
    vector<int> A(N) ;
    for(int i=0;i<N;i++){
        cin >> A.at(i) ;
    }

    bool next;
    int num =0;

    for(int i=0;i>=0;i++){
        bool finished = false;
        bool next = false;
        for(int j=0;j<N;j++){
            if( (A.at(j)%2)==1 ){
             finished = true;
                break;
            }
            else if(((A.at(j)%2)==0)&&(j==N-1)){
                next = true;
            }
            
        }
        if(finished){
            break;
        }
        else{
            num = num + 1;
            if(next){
                for(int k=0;k<N;k++){
                    A.at(k) = (A.at(k))/2 ;
                }
            }
        }
    }
    cout << num << endl;

}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
 
#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
ll MOD = 1e9+7;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }
 
int main(){
  ll i, j;
  ll n;
  cin >> n;
  if(n < 105)
  cout << 0 << endl;
  else if(n < 135)
  cout << 1 << endl;
  else if(n < 165)
    cout << 2 << endl;
  else if(n < 189)
    cout << 3 << endl;
  else if(n < 195)
    cout << 4 << endl;
  else 
    cout << 5 << endl;
    
 
  return 0;
}

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

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    for (size_t i = 0; i < n; i++) cin >> p[i];
    for (size_t i = 0; i < n; i++) cin >> q[i];

    vector<int> perm(n);
    for (size_t i = 0; i < n; i++) perm[i] = i+1;
    int order_p = -1;
    int index = 0;
    do {
        bool same = true;
        for (size_t i = 0; i < n; i++) {
            if (perm[i] == p[i]) {
                continue;
            } else {
                same = false;
                break;
            }
        }
        if (same) {
            order_p = index;
            break;
        }
        index++;
    } while(next_permutation(perm.begin(), perm.end()));

    for (size_t i = 0; i < n; i++) perm[i] = i+1;
    int order_q = -1;
    index = 0;
    do {
        bool same = true;
        for (size_t i = 0; i < n; i++) {
            if (perm[i] == q[i]) {
                continue;
            }else{
                same = false;
                break;
            }
        }
        if (same) {
            order_q = index;
            break;
        }
        index++;
    } while(next_permutation(perm.begin(), perm.end()));

    cout << abs(order_p - order_q) << endl;
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
//#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> Pi;
typedef long long int ll;
const int INF=(ll)(1<<30)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
int a[100100];

int main(){
	cin>>n;
	REP(i,n)
		cin>>a[i];
	
	sort(a,a+n);
	int sa=0;
	for(int i=0;i<n-1;i++){
		if(a[i]==a[i+1]){
			sa++;
		}
	}
	cout<<n-((sa+1)/2)*2<<endl;
	return 0;
}

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> vecStair(n + 1, 0);
	{
		int a;
		for (int i = 0; i < m; ++i) {
			cin >> a;
			vecStair[a] = 1;
		}
	}

	vector <long long> vecRoot(n + 1, 0);
	vecRoot[0] = 1;
	for (int i = 0; i < n - 1; ++i){
		if (vecStair[i] || vecStair[i + 1] || vecStair[i + 2]) {
			if (vecStair[i + 1] && vecStair[i + 2]) {
				break;
			}
			vecRoot[i + 1] = (vecRoot[i] + vecRoot[i + 1]) % 1000000007LL;
			continue;
		}
		vecRoot[i + 1] = (vecRoot[i] + vecRoot[i + 1]) % 1000000007LL;
		vecRoot[i + 2] = (vecRoot[i] + vecRoot[i + 2]) % 1000000007LL;
	}
	long long result = (vecRoot[n - 1] + vecRoot[n]) % 1000000007LL;
	cout << result << endl;

	return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define  rep(i,a,b) for(i=a;i<b;i++)
#define ll long long int
#define ld long double
using namespace std;
int main()
{
IOS;
ll a,b,k;
cin>>a>>b;
if((a+b)%2==0)
cout<<(a+b)/2;
else
cout<<"IMPOSSIBLE";
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

ll f(ll x){
  if(x%4==3){
    return 0;
  }
  else if(x%4==1){
    return 1;
  }
  else if(x%4==2){
    return 1+x;
  }
  else
    return x;
}

int main() {
  ll a,b;
  cin >> a >> b;
  if(a!=0){
    a--;
  }
  ll s=f(b),t=f(a);
  s=s^t;
  cout << s << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<map>
using namespace std;
typedef long long ll;
ll n,s[26],d[365][26],t[365],ans,u[26],q,a,b,c,MAX=-10000000,L,A[365],M,MM,ok;
int main(void){
    cin>>n;
    for(int i=0;i<26;i++){
        cin>>s[i];
    }
    for(int i=0;i<n;i++){
        M=0;
        for(int j=0;j<26;j++){
            cin>>d[i][j];
            if(M<d[i][j]){MM=j;M=d[i][j];}
        }
        t[i]=MM+1;
    }
    
    
    //for(int i=0;i<n;i++){
    //        t[i]=rand()%26+1;
    ///    }
        
        
    q=20000;
    while(q--){
        a=rand()%n;
        b=rand()%26;
        ans=0;
        for(int i=0;i<26;i++)u[i]=0;
        
        c=t[a];
        t[a]=b+1;
        
        for(int i=0;i<n;i++){
            ans+=d[i][t[i]-1];
            u[t[i]-1]=i+1;
            for(int j=0;j<26;j++){
                ans-=s[j]*(i+1-u[j]);
            }
        }
        if(ok==0){MAX=ans;ok=1;}
        if(MAX<ans){
            MAX=ans;
        }
        else t[a]=c;
    }
    
    for(int i=0;i<n;i++){
        cout<<t[i]<<endl;
    }
    //cout<<MAX<<endl;
}


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

int n,m,l;
LL d[305][305],p[305][305];
int main(){
scanf("%d%d%d",&n,&m,&l);
	memset(d,0x3f,sizeof d);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		d[u][v] = d[v][u] = min(d[u][v] , (LL)w);
	}	
	for(int i=1;i<=n;i++) d[i][i] = 0;	
	memset(p,0x3f,sizeof p);
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)	
			for(int j=1;j<=n;j++)
				d[i][j] = min(d[i][j] , d[i][k] + d[k][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(d[i][j] <= l)
				p[i][j] = 1;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)	
			for(int j=1;j<=n;j++)
				p[i][j] = min(p[i][j] , p[i][k] + p[k][j]);
	int q;scanf("%d",&q);
	for(int x,y;q--;){
		scanf("%d%d",&x,&y);
		printf("%lld\n",p[x][y] >= p[0][0] ? -1 :p[x][y] - 1);
	}
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int n;
std::vector<std::vector<std::pair<int, std::pair<i64, i64>>>> g;

std::vector<i64> solve(int s, bool f) {
	typedef std::pair<i64, int> P;
	std::priority_queue<P, std::vector<P>, std::greater<P>> qu;
	std::vector<i64> min_cost(n, 1LL << 60); min_cost[s] = 0; qu.push({0, s});
	while(!qu.empty()) {
		auto p = qu.top(); qu.pop();
		
		for(auto e : g[p.second]) {
			i64 cost = p.first;
			if(f) cost += e.second.first;
			else cost += e.second.second;
			if(cost >= min_cost[e.first]) continue;
			min_cost[e.first] = cost;
			qu.push({cost, e.first});
		}
	}
	
	return min_cost;
}

int main() {
	int m, s, t; cin >> n >> m >> s >> t; s--; t--; g.resize(n);
	for(int i = 0; i < m; i++) {
		i64 a, b, c, d; cin >> a >> b >> c >> d;
		
		g[a - 1].push_back({b - 1, {c, d}});
		g[b - 1].push_back({a - 1, {c, d}});
	}
	auto A = solve(s, true), B = solve(t, false);
	
	i64 mi = 1LL << 60;
	std::vector<i64> ans;
	for(int i = n - 1; i >= 0; i--) {
		mi = std::min(mi, A[i] + B[i]);
		ans.push_back(i64(1e15) - mi);
	}
	reverse(begin(ans), end(ans));
	for(auto v : ans) cout << v << endl;
	return 0;
}


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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("0 75 25 100");
            //50
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 33 66 99");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 90 20 80");
            //60
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        int A = wkArr[0];
        int B = wkArr[1];
        int C = wkArr[2];
        int D = wkArr[3];

        int DupSec = 0;
        for (int I = A; I <= B; I++) {
            if (C <= I && I <= D) {
                DupSec++;
            }
        }
        if (DupSec == 0) Console.WriteLine(0);
        else Console.WriteLine(DupSec - 1);
    }
}


Measured memory_bytes: 13268
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>

#define ll long long

using namespace std;

ll L, R;

int main()
{
	ll mn = 2019;

	scanf("%lld %lld", &L, &R);
	if (R - L >= 2019) printf("0\n");
	else
	{
		for (ll i = L; i <= R; ++i)
		{
			for (ll j = i + 1; j <= R; ++j)
			{
				ll temp = (i*j) % 2019;
				if (temp < mn) mn = temp;
			}
		}
		printf("%lld\n", mn);
	}

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int n,k,c;
char s[200005];
set<int> st;
set<int> st2;
set<int> st3;
int main(){
	//freopen("in.txt","r",stdin);
	scanf("%d%d%d%s",&n,&k,&c,s);
	
	int cnt=1;
	for(int i=0;i<n;i++){
		if(s[i]=='o') {
			st.insert(i+1);
			cnt++;
			i+=c;
		}
		if(cnt>k) break;
	}
	
	cnt=0;
	for(int i=n-1;i>=0;i--){
		if(s[i]=='o'){
			st2.insert(i+1);
			cnt++;
			i-=c;
		}
		if(cnt>k) return 0;
	}
	set_intersection(st.begin(),st.end(),st2.begin(),st2.end(),ostream_iterator<int>(cout,"\n"));
	//set_intersection(st.begin(),st.end(),st2.begin(),st2.end(),inserter(st3,st3.begin()));
	
	
	
	return 0;
}

Measured memory_bytes: 20480
#include<stdio.h>
#define X 1000
void insertionSort(int A[], int N);

int main(){
  int N,i,j;
  int A[X];

  scanf("%d",&N);
  
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  insertionSort(A,N);
  return 0;
}

void insertionSort(int A[], int N){
  int i,j,v;
  for(i=0;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1] = v;
    for(j=0;j<N;j++){
    if(j>0) printf(" ");
    printf("%d",A[j]);
    }
    printf("\n");
  }
}


Measured memory_bytes: 2084
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1<<28;
const int maxn=110;
const int maxm=110;
const int maxk=100010;
const int mod=1e9+7;
const double pi=acos(-1.0);
ll n,w;
ll val[4][maxn];
ll sum[4][maxn];
bool cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%lld %lld",&n,&w))
    {
        ll k[4]={1,1,1,1};
        sum[0][0]=sum[1][0]=sum[2][0]=sum[3][0]=0;
        ll w0=0;
        for(ll i=1;i<=n;i++)
        {
            ll a,b;
            scanf("%lld %lld",&a,&b);
            if(i==1) w0=a;
            val[a-w0][k[a-w0]++]=b;
        }
        sort(val[0]+1,val[0]+k[0]+1,cmp);
        sort(val[1]+1,val[1]+k[1]+1,cmp);
        sort(val[2]+1,val[2]+k[2]+1,cmp);
        sort(val[3]+1,val[3]+k[3]+1,cmp);
        for(ll i=0;i<4;i++)
            for(ll j=1;j<k[i];j++)
                sum[i][j]=sum[i][j-1]+val[i][j];
        ll ans=0;
        for(ll i=0;i<k[0];i++)
            for(ll j=0;j<k[1];j++)
            for(ll o=0;o<k[2];o++)
            for(ll l=0;l<k[3];l++)
            if(i*w0+j*(w0+1)+o*(w0+2)+l*(w0+3)<=w)
            ans=max(ans,sum[0][i]+sum[1][j]+sum[2][o]+sum[3][l]);
        printf("%lld\n",ans);
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
S = {'__min__': 0}
for _ in range(N):
    s = input()
    if S.get(s) == None:
        S[s] = 1
    else:
        S[s] += 1

M = int(input())
for _ in range(M):
    t = input()
    if S.get(t) == None:
        continue
    elif S[t] <= 1:
        S.pop(t)
    else:
        S[t] -= 1

print(max(S.values()))


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MOD = 1000000007;
int main(){
	long long int N,ans=0;
	cin>>N;
	long long int A[N];
	long long int sA[N];
	for(int i=0;i<N;i++){
		cin>>A[i];
		if(i>0)sA[i]=(sA[i-1]+A[i])%MOD;
		else sA[i]=A[i];
	}
	for(int i=1;i<N;i++){
		ans=(ans+sA[i-1]*A[i]%MOD)%MOD;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 6748
n=int(input())
INF=10**9+7
sum=0
m=INF
for i in range(n):
    a,b=map(int,input().split())
    sum+=a
    if a>b:
        m=min(m,b)
if m==INF:
    print(0)
else:
    print(sum-m)

Measured memory_bytes: 51800
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	string s; cin >> s;
	vector<int> v(3, 0);
	int cnt = 0;
	rep(i,0,3){
		if (s[i] != 'R')
			cnt = 0;
		else
			cnt++;
		v[i] = cnt;
	}
	cout << max(v[0], max(v[1], v[2])) << endl;
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b) {
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b) {
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i) {
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )) {
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


int main(void)
{
    int n;
    cin >> n;
    vector<vector<pair<int,ll>>> tree(n);

    REP(i,n-1){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        a--;
        b--;
        tree[a].push_back(pair<int,ll>(b,c));
        tree[b].push_back(pair<int,ll>(a,c));
    }

    int q,k;
    cin >> q >> k;
    k--;

    vector<ll> distance(n,0);
    vector<int> color(n,0);

    queue<int> s;
    s.push(k);
    color[k]++;
    distance[k] = 0;
    while(!s.empty()){
        int v = s.front();
        s.pop();
        for(int i = 0;i<tree[v].size();i++){
            pair<int,ll> child = tree[v][i];
            if(color[child.first] != 0){
                continue;
            }
            s.push(child.first);
            color[child.first]++;
            distance[child.first] = distance[v] + child.second;
        }
    }

    vector<ll> ans(q);
    REP(i,q){
        int x,y;
        cin >> x >> y;
        ans[i] = distance[x-1] + distance[y-1];
    }

    REP(i,q){
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#include <cstdint>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>

int main() {
  std::int_fast64_t n;
  std::cin >> n;
  std::pair<std::int_fast64_t, std::int_fast64_t> last_pair(1, n);
  for (std::int_fast64_t i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      last_pair = std::make_pair(i, n / i);
    }
  }
  std::cout << std::max(std::to_string(last_pair.first).size(), std::to_string(last_pair.second).size()) << std::endl;
  return 0;
}

Measured memory_bytes: 256
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair< int, int > pii;
typedef pair< pii, int > ppi;
#define fill(a,b) memset(a,b,sizeof(a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int inf = 0x3f3f3f3f;// (int)3e18;
const int maxn = 2000100;



int main(){
        _
        int n; cin >> n;
        vi a(n+1);
        for(int i = 1; i<=n; i++){
            cin >> a[i];
        }
        int cur  =  1;
        int tot = 0;
        while(cur!=2){
            if(tot>n)break;
            cur = a[cur];
            tot++;
            if(cur==2){
                cout<<tot<<endl;
                return 0;
            }
        }
        cout<<-1<<endl;


return 0;
}



Measured memory_bytes: 640
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 998244353;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

ll modpow(ll a, ll b){
    if(b == 0) return 1;
    else if(b % 2 == 0){
        ll d = modpow(a, b/2) % MOD;
        return (d * d) % MOD;
    }
    else{
        return (a * modpow(a, b-1)) % MOD;
    }
}

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

    int n; cin>>n;
    vector<ll> x(n);
    for(int i=0; i<n; i++) cin>>x[i];

    ll ans = 0;
    for(int i=0; i<n; i++){
        ans += modpow((1 + x[i]), i) * x[i] % MOD * modpow(2, n-i-1);
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 10740
n = int(input())
*a, = map(int, input().split())
*b, = map(int, input().split())
count = 0
for i in range(n):
    tmp = min(a[i], b[i])
    count += tmp
    b[i] -= tmp
    tmp2 = min(a[i+1], b[i])
    count += tmp2
    a[i+1] -= tmp2

print(count)

Measured memory_bytes: 19116
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD1 1000000007

int main() {
  int N;
  cin >> N;
  int A[2][N];
  rep(i, 2) {
    rep(j, N) {
      cin >> A[i][j];
    }
  }

  int S[N];
  S[0] = A[0][0];
  rep(i, N) S[0] += A[1][i];

  int ans = S[0];

  rep(i, N - 1) {
    S[i + 1] = S[i] + A[0][i + 1] - A[1][i];
    ans = max(ans, S[i + 1]);
  }

  cout << ans << endl;

}


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

    Ai = []
    for _ in range(N):
        Ai.append(input())
    Bi = []
    for _ in range(M):
         Bi.append(input())

    return N, M, Ai, Bi


def solve(N, M, Ai, Bi):
    for xi in range(N - M + 1):
        if Ai[0][xi:xi + M] == Bi[0][:]:
            for yi in range(1, M):
                if not Ai[yi][xi:xi + M] == Bi[yi][:]:
                    break
            return True

    return False


if __name__ == '__main__':
    res = solve(*get_args())
    if res:
      print("Yes")
    else:
      print("No")


Measured memory_bytes: 38256
import numpy as np
n, c, k = [int(a) for a in input().split()]
t = []
for _ in range(n):
    t.append(int(input()))
t = np.asarray(t)
t = np.sort(t)

ans = 0
count = 0
lim = 0

for i in range(t.shape[0]):
    if count == 0:
        lim = t[i] + k
        count += 1
    elif t[i] <= lim and count < c:
        count += 1
    else:
        lim = t[i] + k
        ans += 1
        count = 1

print(ans+1)

Measured memory_bytes: 17096
def main():
    # map(int, input().split())
    # l = list(map(int, input().split()))
    N = int(input())
    X = int(N / 1.08)
    flag = False
    for i in [X-1, X, X+1]:
        if int(i*1.08) == N:
            flag = True
            print(i)
            break
    if not flag:
        print(':(')


if __name__ == "__main__":
    main()

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

int main() {
  int n, m;
  vector<int> a;

  while (1) {
    int flag = 0;

    cin >> n >> m;
    if(n == 0 && m == 0)
      break;

    for (int i = 0; i < n; i++) {
      int A;
      cin >> A;
      a.push_back(A);
    }

    vector<int> sum;

    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        if(i != j) {
          int Sum = a[i] + a[j];
          sum.push_back(Sum);
        }
      }
    }

    sort(sum.begin(), sum.end(), greater<int>());

    for(int i = 0; i < sum.size(); i++){
      if(sum[i] <= m) {
          cout << sum[i] << endl;
          flag = 1;
          break;
      }
    }

    if(flag == 0) {
      cout << 'N' << 'O' << 'N' << 'E' << endl;
    }

    sum.clear();
    a.clear();
  }
  return 0;
}



Measured memory_bytes: 10736
#include <stdio.h>

int main(void){
    int i,j,N;
    int a[101];
    int cnt = 0;
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    for(i=1;i<N;i++){
        if(a[i-1]==a[i]){
            a[i] += 4;
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

Measured memory_bytes: 128
n = int(input())
xyh = [tuple(int(x) for x in input().split()) for _ in range(n)]

base = [0,0,0]
for x, y, h in xyh:
    if h > 0:
        base = [x,y,h]

for i in range(101):
    for j in range(101):
        top_h = abs(i - base[0]) + abs(j - base[1]) + base[2]
        check = 1
        for x, y, h in xyh:
            if max(top_h - abs(i - x) - abs(j - y), 0) != h:
                check = 0
                break
        if check == 1:
            print(i, j, top_h)
            exit()



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

int main(){
  string s;
  cin >> s;
  
  int ans = 0;
  int month1 = s.at(6) - '0';
  int month2 = s.at(5) - '0';
  if (month1 < 5){
    if (month2 == 0)
      ans = 1;
  }
  
  if (ans == 1)
    cout << "Heisei" << endl;
  else
    cout << "TBD" << endl;
}

Measured memory_bytes: 3552
def main():
    MOD = 10 ** 9 + 7

    s = input()

    x, a, b, c = 1, 0, 0, 0

    for char in s:
        if char == 'A':
            a = (a + x) % MOD
        elif char == 'B':
            b = (b + a) % MOD
        elif char == 'C':
            c = (c + b) % MOD
        else:
            x, a, b, c = 3 * x % MOD, (3 * a + x) % MOD, (3 * b + a) % MOD, (3 * c + b) % MOD

    print(c)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <stdio.h>

int main(void) {
	int i,n,x;
	long min,max,sum=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%ld",&x);
		sum=sum+x;
		if(i==0){
			max=x;
			min=x;
		
	}else if(x>max) {
			max=x;
	}else if(x<min){
		 min=x;
	}
	}
	printf("%ld %ld %ld\n",min,max,sum);
	return 0;
}

Measured memory_bytes: 1828
#include <bits/stdc++.h>
using namespace std;
const long long int INF = (10e11);


int main()
{
int n,m,x;
cin >> n >> m >> x;
vector <int> price(n);
vector <vector <int>> c(n,vector <int>(m));
for (int i=0; i<n; i++)
    {
        cin >> price[i];
        for (int j=0; j<m; j++)
                cin >> c[i][j];
    }

 long long int res = INF;

for (int mask=0; mask<(1<<n); mask++)
    {
        //cout << mask;
        long long now = 0;
        vector <int> cx(m,0);
            for (int j=0; j<n; j++)
                {

                    if ((mask&(1<<j))!=0)
                        {
                            //cout << j << " ";

                               now += price[j];
                                for (int ii=0; ii<m; ii++)
                                    cx[ii]+=c[j][ii];
                        }
                }
    /*
        cout << mask << " __  ";
        for (int i=0; i<m; i++) cout << cx[i] << "\n"[i!=m-1];
    */

        bool ok = true;
        for (int i=0; i<m; i++)
            if (cx[i]<x){ ok =false; break;}

        if (ok) res = min(res,now);
    }

if (res==INF) cout << "-1"; else cout << res;

}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int N;
    cin >> N;
    vector<int> D(N);
    int sum = 0;
    rep(i,N){
        cin >> D.at(i);
        sum += D.at(i);
    }
    int M;
    cin >> M;
    vector<pair<int,int>> P(M);
    rep(i,M){
        cin >> P.at(i).first >> P.at(i).second;
        cout << sum - D.at(P.at(i).first-1) + P.at(i).second << endl;;
    }
}   

Measured memory_bytes: 256