akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <cstring>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int x;
    cin>>x;
    int y[x];
    for (int i=0;i<x;i++)
        cin>>y[i];
    ll alice=0,bob=0;
    sort(y,y+x);
    for (int i=x-1;i>=0;i-=2)
    {
        alice+=y[i];
    }
    for (int i=x-2;i>=0;i-=2)
        bob+=y[i];
    cout<<alice-bob<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			String[] data = scan.nextLine().split(" ", 0);
			double[] num = new double[6];
			for (int i = 0; i < 6; i++) {
				num[i] = Double.parseDouble(data[i]);
			}
			double x = (num[2]*num[4]-num[1]*num[5])/(num[0]*num[4]-num[1]*num[3]);
			if (abs(x) < 10E-9) x = 0;
			double y = -(num[2]*num[3]-num[0]*num[5])/(num[0]*num[4]-num[1]*num[3]);
			if (abs(y) < 10E-9) y = 0;
			String sx = String.format("%.3f", x);
			String sy = String.format("%.3f", y);
			System.out.println(sx + " " + sy);
		}
	}

	private static double abs(double x) {
		if (x >= 0) return x;
		else return -x;
	}
}

Measured memory_bytes: 26208
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()
template<class T>
using reverse_priority_queue = priority_queue<T, vector<T>, greater<T>>;


int main(){
    ll n;
    cin >> n;
    ll ans = (n + 1) * n / 2;
    for(ll l = 1; l <= n; ++l){
        ans += (n - l + 1) * (n + l) / 2;
        ans -= l * (n - l + 1);
    }

    REP(i, n - 1){
        ll ui, vi;
        cin >> ui >> vi;
        if(ui > vi){
            swap(ui, vi);
        }
        ans -= ui * (n - vi + 1);
    }

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


Measured memory_bytes: 3600
# ABC125D - Flipping Signs
def main():
    # neg % 2 == 0 -> all negatives disappear
    # else -> move all neg to the smallest one (abs(i))
    # if 0 in A -> move all neg there but min will be 0
    N, *A = map(int, open(0).read().split())
    mi = abs(min(A, key=abs))
    abs_sum = sum(abs(i) for i in A)
    neg = sum(i < 0 for i in A)
    ans = abs_sum if neg % 2 == 0 else abs_sum - mi * 2
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 14116
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<p> v(n);
  for (int i = 0; i < n; i++) {
    v[i].second = i + 1;
    cin >> v[i].first;
  }
  sort(ALL(v));
  rep(i, n) cout << v[i].second << ' ';
  cout << endl;
}


Measured memory_bytes: 2432
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;



int main () {
	SpeedForce;
	cin >> s;
	for (auto &e : s) if (e == '?') e = 'D';
	cout << s;

	return Accepted;
}

// B...a

Measured memory_bytes: 17864
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(' ').map { it.toInt() }
    val p = readLine()!!.split(' ').map { it.toDouble() }
    val e = p.map { (it + 1) / 2 }
    val s = DoubleArray(n + 1)
    for (i in 1..n) {
        s[i] = s[i - 1] + e[i - 1]
    }
    var ans = 0.0
    for (i in 0..n-k) {
        ans = Math.max(ans, s[i + k] - s[i])
    }
    println(ans)
}


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

void solve() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) {
        cin >> S[i];
    }

    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, -1, 0, 1};
    UnionFind uf(H * W);
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = 0; k < 4; k++) {
                int ty = i + dy[k];
                int tx = j + dx[k];
                if (ty < 0 || ty >= H || tx < 0 || tx >= W) continue;
                if (S[i][j] == S[ty][tx]) continue;
                int ind = i * W + j;
                int ind2 = ty * W + tx;
                uf.unionSet(ind, ind2);
            }
        }
    }

    vector<ll> black(H * W), white(H * W);
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int ind = i * W + j;
            
            int r = uf.root(ind);
            if (S[i][j] == '#') black[r]++;
            if (S[i][j] == '.') white[r]++;
        }
    }

    set<int> ID;
    ll ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int ind = i * W + j;
            if (ID.find(uf.root(ind)) != ID.end()) continue;
            ID.insert(uf.root(ind));

            ll N = uf.size(ind);
            ans += black[uf.root(ind)] * white[uf.root(ind)];
            //cout << black[uf.root(ind)] * white[uf.root(ind)] << endl;
        }
    }

    cout << ans << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();

    #ifdef LOCAL_ENV
    assert(cin.rdstate() & ios_base::eofbit);
    #endif
}

Measured memory_bytes: 9728
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000009)
	sc.Split(bufio.ScanWords)
	k, _ := strconv.Atoi(Scanner())
	x := []int{1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51}
	fmt.Println(x[k-1])
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define lli long long int 
int main()
{
    string s;
    cin>>s;
    lli n=s.length(),i,d=0;
    for(i=0;i<n;i++)
    d=d+s[i]-48;
    if(d%9==0)
    cout<<"Yes\n";
    else
    cout<<"No\n";
	return 0;
}

Measured memory_bytes: 3752
using System;
using System.Text;

namespace AtCoderWorkspace
{
    public class Class137_2
    {
        private static void Main(string[] args)
        {
            var inputs = Console.ReadLine().Split(' ');

            int x, k = 0;
            int.TryParse(inputs[0],out k);
            int.TryParse(inputs[1],out x);
            
            int start = x - (k - 1);
            int end = x + (k - 1);
            
            StringBuilder sb = new StringBuilder();

            for (int i = start; i <=end ; i++)
            {
                if (i == end)
                {
                    sb.Append(i);
                }
                else
                {
                    sb.Append(i + " ");
                }
            }
            Console.WriteLine(sb.ToString());
        }
    }
}

Measured memory_bytes: 13140
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
   int x,y,z,d;
   cin>>x>>y>>z>>d;
   if(abs(x-z)<=d || (abs(x-y)<=d && abs(y-z)<=d)){
    cout<<"Yes"<<endl;
   }
   else{cout<<"No"<<endl;}
}

Measured memory_bytes: 3608
#include<stdio.h>
#define max 100000
int a[max],n;
int partition(int p,int r);

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

int partition(int p,int r){
	int x,i,j,tmp;
	x=a[r];
	i=p-1;
	for(j=p; j<r; j++)
	{
		if(a[j]<=x){
			i++;
			tmp=a[i];
			a[i]=a[j];
			a[j]=tmp;
		}
	}
	
	tmp=a[i+1];
	a[i+1]=a[r];
	a[r]=tmp;
	
	return i+1;
}



Measured memory_bytes: 2144
import numpy as np


def main():
    w, h, n = map(int, input().split())
    xyas = [list(map(int, input().split())) for _ in range(n)]
    board = np.array([[0 for i in range(w)] for j in range(h)])
    for x, y, a in xyas:
        if a == 1:
            board[:, :x] = 1
        elif a == 2:
            board[:, x:] = 1
        elif a == 3:
            board[-y:, :] = 1
        elif a == 4:
            board[:-y, :] = 1
    ans = (w*h) - np.sum(board)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 27208
#include <bits/stdc++.h>
using namespace std;
long long ans, n, p, t, a[10000], L, D = 1; string s;
int main(){
    cin >> n >> p >> s;
    for(int i = n - 1; i >= 0 ; i--){
        L = s[i] - '0', t = (D * L + t) % p, D = (D * 10) % p;
        ans += ((10 % p) != 0)?(t == 0) + a[t]++ : ((L % p) == 0) * (i + 1);
    }
    cout << ans << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) cin >> a[i];

  vector<int> t(100000, 0);
  for (int i=0; i<n; i++) {
    t[a[i]]++;
  }
  int cnt = 0;
  for (int i=0; i<t.size()-2; i++) {
    cnt = max(cnt, t[i] + t[i+1] + t[i+2]);
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 1024
N = int(input())
array = list(map(int,input().split()))
hai = []
tya = []
midori = []
mizu = []
ao = []
ki = []
dai = []
aka = []
mu = []
for i in array:
    if i <= 399:
        hai.append(i)
        continue
    if i <= 799:
        tya.append(i)
        continue
    if i <= 1199:
        midori.append(i)
        continue
    if i <= 1599:
        mizu.append(i)
        continue
    if i <= 1999:
        ao.append(i)
        continue
    if i <= 2399:
        ki.append(i)
        continue
    if i <= 2799:
        dai.append(i)
        continue
    if i <= 3199:
        aka.append(i)
        continue
    mu.append(i)
ans = 0
if len(hai) != 0:
    ans += 1
if len(tya) != 0:
    ans += 1
if len(midori) != 0:
    ans += 1
if len(mizu) != 0:
    ans += 1
if len(ao) != 0:
    ans += 1
if len(ki) != 0:
    ans += 1
if len(dai) != 0:
    ans += 1
if len(aka) != 0:
    ans += 1
ans_min = max(ans,1)
ans_max = ans + len(mu)
print(ans_min,ans_max)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
typedef long long lint;
const int N=131080;
int n;
class pair{
	public:
		lint x,y;
		friend bool operator < (const pair &a,const pair &b);
};

bool operator < (const pair &a,const pair &b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}

inline int nxi(){
	int x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
	return x;
}

inline int x_bound(std::vector <pair> &vt,const lint _lim){
	int l=0,r=vt.size()-1,mid;
	while(l!=r){
		mid=(l+r+1)>>1;
		if(vt[mid].x>_lim) r=mid-1;
		else l=mid;
	}
	return l;
}

inline int y_bound(std::vector <pair> &vt,const lint _lim){
	int l=0,r=vt.size()-1,mid;
	while(l!=r){
		mid=(l+r)>>1;
		if(vt[mid].y>_lim) l=mid+1;
		else r=mid;
	}
	return l;
}

inline void sanitize_seq(std::vector <pair> &vt){
	const int sz=vt.size();
	int p1=1,p2=1;
	for(; p1<sz; ++p1){
		if(vt[p1].x!=vt[p2-1].x&&vt[p1].y<vt[p2-1].y) vt[p2++]=vt[p1];
	}
	while((int)vt.size()>p2) vt.pop_back();
}

namespace G{
	int cnt,nxt[N][2],wt[N][2];
	lint lim_w;
	std::vector <pair> vt[N];

	inline void add(const int a,const int b,const int v){
		bool f=nxt[a][0]>0;
		nxt[a][f]=b,wt[a][f]=v;
	}

	void dfs(const int x){
		if(!nxt[x][0]){
			vt[x].push_back((pair){0,0});
			return;
		}
		dfs(nxt[x][0]);
		dfs(nxt[x][1]);
		if(vt[nxt[x][0]].size()>vt[nxt[x][1]].size()){
			std::swap(nxt[x][0],nxt[x][1]);
			std::swap(wt[x][0],wt[x][1]);
		}

		const int c0=nxt[x][0],c1=nxt[x][1];
		const lint v0=wt[x][0],v1=wt[x][1];
		const int lim_l=vt[c0].size();

		for(int i=0,j,lst_j=-1; i<lim_l; ++i){
			const lint _lim=lim_w-vt[c0][i].y-v0-v1;
			j=x_bound(vt[c1],_lim);
			if(vt[c1][j].x>_lim) continue;
			if(j!=lst_j){
				lst_j=j;
				vt[x].push_back((pair){vt[c0][i].x+v0,vt[c1][j].y+v1});
			}
		}
		for(int i=lim_l-1,j,lst_j=-1; i>=0; --i){
			const lint _lim=lim_w-vt[c0][i].x-v0-v1;
			j=y_bound(vt[c1],_lim);
			if(vt[c1][j].y>_lim) continue;
			if(j!=lst_j){
				lst_j=j;
				vt[x].push_back((pair){vt[c1][j].x+v1,vt[c0][i].y+v0});
			}
		}
		std::sort(vt[x].begin(),vt[x].end());
		sanitize_seq(vt[x]);
	}

	bool jdg(const lint tgt){
		lim_w=tgt;
		for(int i=1; i<=n; ++i){
			vt[i].clear();
		}
		dfs(1);
		return !vt[1].empty();
	}
}

inline lint solve(){
	lint l=0,r=2e10,mid;
	while(l!=r){
		mid=(l+r)>>1;
		if(G::jdg(mid)) r=mid;
		else l=mid+1;
	}
	return l;
}

int main(){
	n=nxi();
	for(int i=2; i<=n; ++i){
		int fr=nxi();
		G::add(fr,i,nxi());
	}
	printf("%lld\n",solve());
	return 0;
}

Measured memory_bytes: 29812
#include <stdio.h>

int main( int argc, char *argv[] )
{
	int sx,sy,tx,ty;
	scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
	for(int i=0; i<tx-sx;i++)printf("R");
	for(int i=0; i<ty-sy;i++)printf("U");
	for(int i=0; i<tx-sx;i++)printf("L");
	for(int i=0; i<ty-sy;i++)printf("D");
	printf("D");
	for(int i=0; i<tx-sx+1;i++)printf("R");
	for(int i=0; i<ty-sy+1;i++)printf("U");
	printf("L");
	printf("U");
	for(int i=0; i<tx-sx+1;i++)printf("L");
	for(int i=0; i<ty-sy+1;i++)printf("D");
	printf("R\n");
	return 0;
}


Measured memory_bytes: 128
a, b, c, d = gets.chomp.split(' ').map(&:to_i)

t1 = a / d + ((a % d != 0) ? 1 : 0)
t2 = c / b + ((c % b != 0) ? 1 : 0)

puts t1 >= t2 ? 'Yes' : 'No'


Measured memory_bytes: 14312
/*
        Author: Prokash
                CSE48, JU

*/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int ara[2005];
int main()
{
    FAST;
    int t,n;
    set<int>s;
    cin>>t;
    while(t--)
    {
        cin>>n;
        s.insert(n);
    }
    cout<<s.size()<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n; cin >> n;
    long long ans = 0;
    for (long long i = 1; i * i <= n; i++) {
        // i
        if (n % i != 0) continue;
        long long c = i; long long d = n/i;
        if (c < d-1) ans += d-1;
        if (i == n / i) break;
        // n/i
        if (d < c-1) ans += c-1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
    int n, R[MAX];
    
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &R[i]);
    
    int maxv = R[1] - R[0];
    int minv = R[0];
    
    for (int i=1; i<n; i++) {
        maxv = max(maxv, R[i] - minv);
        minv = min(minv, R[i]);
    }
    
    printf("%d\n", maxv);
    
    return 0;
}


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

int main(){
    int n,arr[101],m,p,t,sum=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>p>>t;
        int temp=sum;
        temp+=(t-arr[p-1]);
        cout<<temp<<endl;
    }
    return 0;
}


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

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);

int main() {
    int a[5], ans = 0;
    rep(i, 5) cin >> a[i];
    int min = 11, index = 0;
    rep(i, 5) {
        if((a[i]%10) != 0) {
            if(min > (a[i]%10)) {
                min = a[i]%10;
                index = i;
            }
        }
    }
    rep(i, 5) {
        if(index == i) ans += a[index];
        else {
            ans += a[i]+9-((a[i]+9)%10);
        }
    }
    cout << ans << endl;

    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        ret %= MOD;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

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

ll inv(ll a) {
    return a_n(a, MOD-2);
}



Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var A = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var B = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        var ans = 0L;

        for (int i = 0; i < N; i++)
        {
            var defeatCount = Math.Min(A[i], B[i]);
            A[i] -= defeatCount;
            B[i] -= defeatCount;
            ans += defeatCount;

            if(0 < B[i])
            {
                defeatCount = Math.Min(A[i + 1], B[i]);
                A[i + 1] -= defeatCount;
                B[i] -= defeatCount;
                ans += defeatCount;
            }
        }

        WriteLine(ans);
    }
}


Measured memory_bytes: 45916
package main
import (
	"fmt"
	"os"
	"bufio"
	"strconv"
	"sort"
)
//sort関数はGo1.8~らしい
var stdin = bufio.NewScanner(os.Stdin)

type Data struct{
	A int
	B int
}
//~Go1.7
type ByAData []Data

func (a ByAData)Len()int {
	return len(a)
}
func (a ByAData)Less(i,j int) bool {
	return a[i].A < a[j].A
}
func (a ByAData)Swap(i,j int){
	a[i],a[j] = a[j],a[i]
}

func Input_int() int {
	stdin.Scan()
	out,err := strconv.Atoi(stdin.Text())
	if err != nil{
		panic(err)
	}
	return out
}


func main() {
	stdin.Split(bufio.ScanWords)
	N,M := Input_int(),Input_int()
	Datas := []Data{}
	for i := 0; i < N; i++ {
		Data_temp := Data{Input_int(),Input_int()}
		Datas = append(Datas,Data_temp)
	}
	//sort.Slice(Datas,func (i,j int) bool {return Datas[i].A<Datas[j].A})
	sort.Sort(ByAData(Datas))
	items := 0
	sum := 0
	for i:=0;items<M;i++ {
		if (Datas[i].B + items) > M{
			sum += (M-items)*Datas[i].A
			break
		}else{
			sum += Datas[i].A*Datas[i].B
			items += Datas[i].B
		}
	}
	fmt.Println(sum)
}

Measured memory_bytes: 7040
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, v, p, ans;
vector<int> a;

bool f(int x){
    long long w = v-p, y = a[x] + m;
    if(w > 0){
        w *= m;
        for(int i=p-1;i<n;i++){
            if(i != x){
                long long r = y - a[i];
                if(r < 0) return false;
                if(r > m) r = m;
                w -= r;
            }
        }
    }else{
        w = a[p-1] - y;
    }
    
    return (w <= 0);
}

int main(void){
    cin >> n >> m >> v >> p;
    a.assign(n, 0);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(), a.end(), greater<int>());

    int ok = p-1, ng = n;
    while(ok + 1 < ng){
        int mid = (ok + ng) / 2;
        if(f(mid)) ok = mid;
        else ng = mid;
    }

    cout << ng << endl;
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int H, W;
int G[10][10], cost[10][10];
int A[205][205];

int main(void)
{
	cin >> H >> W;
	for(int i = 0; i < 10; i++){
		for(int j = 0; j < 10; j++){
			cin >> G[i][j];
			cost[i][j] = G[i][j];
		}
	}
	for(int y = 0; y < H; y++){
		for(int x = 0; x < W; x++){
			cin >> A[x][y];
		}
	}
	
	for(int k = 0; k < 10; k++){
		for(int i = 0; i < 10; i++){
			for(int j = 0; j < 10; j++){
				cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
			}
		}
	}
	
	int ans = 0;
	for(int i = 0; i < W; i++){
		for(int j = 0; j < H; j++){
			if(A[i][j] == -1) continue;
			ans += cost[A[i][j]][1];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int h,w,k;
	std::cin >> h >> w >> k;
	std::vector<std::string> g(h);
	rep(i,h) std::cin >> g[i];
	const int INF=1e9;
	int min = INF;
	rep(c,1<<(h-1)) {
		int count=__builtin_popcount(c);
		int bc=count;
		std::vector<int> ac(bc+1,0);
		rep(i,w) {
			int j=0;
			std::vector<int> ad(bc+1,0);
			rep(xx,h) {
				ad[j]+=(g[xx][i]=='1');
				if(c>>xx&1) j++;
			}
			int brk=false;
			rep(xx,bc+1) {
				if(ad[xx]>k) {
					goto impossible;
				}
				if(!brk && ac[xx]+ad[xx]>k) {
					if(i!=0) count++;
					ac=ad;
					brk=true;
				}
			}
			if(!brk) {
				rep(xx,bc+1) ac[xx]+=ad[xx];
			}
		}
		min=std::min(min,count);
impossible:;
	}
	print(min);

	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{   int a[3][3],i,j,k=0,n,p=1,b[10],f[3][3]={0};
    for(i=0;i<3;i++)
    for(j=0;j<3;j++)
    scanf("%d",&a[i][j]);
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&b[i]);
	for(i=0;i<3;i++)
    for(j=0;j<3;j++)
    {  k=0;
	   while(k<n)
       {  if(a[i][j]==b[k])
          {  f[i][j]=1;
             k=n;
	      }
	      else k++;
	   }
	}
	for(i=0;i<n;i++)
	if(f[i][0]==1&&(f[i][1]==1)&&(f[i][2]==1)) 
	   {  printf("Yes");
	      i=n;p=0;
	   }
	if(p)
	{  for(i=0;i<n;i++)
	   if(f[0][i]==1&&(f[1][i]==1)&&(f[2][i]==1)) 
	   {  printf("Yes");
	      i=n;p=0;
	   }
	}
	if(p)
	if(f[0][0]==1&&(f[1][1]==1)&&(f[2][2]==1)||((f[2][0]==1)&&((f[1][1]==1)&&((f[0][2]==1))))) 
	   { printf("Yes");
	     p=0;
	   }
	if(p) printf("No");
} 

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

int main() {
	int x;
	cin >> x;
	if (x == 1) {
		cout << 1 << endl;
		return 0;
	}

	int max = 0;
	for (int i = 2; i <= x; i++) {
		int f = 1;
		int count = 0;
		while (f * i <= x) {
			f *= i;
			count++;
		}
		if (max < f && count >= 2)
			max = f;
	}	
	cout << max << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int L;
	int N,M=0;
	vint s;
	vector<int> e,w;
	int r;
	scan(L);
	rep(i,21){
		if((1<<i)>L){
			r=i-1;
			break;
		}
	}
	N=r+1;
	rep1(i,N-1){
		s.push_back(i); e.push_back(i+1); w.push_back(0);
		s.push_back(i); e.push_back(i+1); w.push_back(1<<(i-1));
		M+=2;
	}
	for(int t=N-1;t>=1;t--){
		if(L-(1<<(t-1))>=(1<<r)){
			s.push_back(t);
			e.push_back(N);
			w.push_back(L-(1<<(t-1)));
			L-=(1<<(t-1));
			M++;
		}
	}
	printf("%d %d\n",N,M);
	rep(i,M){
		printf("%d %d %d\n",s[i],e[i],w[i]);
	}
	return 0;
}


Measured memory_bytes: 384
import java.util.*;
class Main{
    public static void main(String args[]){
	Scanner scan = new Scanner(System.in);
	int a,b,c;
	a=scan.nextInt();
	b=scan.nextInt();
	c=scan.nextInt();
	if(a<b&&b<c)System.out.println("Yes");
	else System.out.println("No");
    }
}

Measured memory_bytes: 26228
A,B,C,D=map(int,input().split())

if C%B == 0:
    X = C//B - 1
else:
    X = C//B
if A%D == 0:
    Y = A//D -1
else:
    Y = A//D

if Y>=X:
    print('Yes')
else:
    print('No')
    

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

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

 
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
  ll N, A;
  ll ans = 0;
  double b, M = 0;
  cin >> N >> M;
  vector<ll> x(N);
    REP(i,N) {
    cin >> A;
    b += A;
    x[i] = A;
  }
  b *= (1/(4*M));
  REP(i,N) {
    if (x[i] >= b) {
      ans++;
    }
  }
  if (ans < M) cout << "No";
  else cout << "Yes";
}


Measured memory_bytes: 3720
#include <iostream>
#include <vector>
#include <stack>
#include <utility>

using namespace std;

int seq[5]={5,7,5,7,7};

bool isword(int s,int n,vector<string> list){
    if(s==5)return true;
    int sum=0;
    bool flag;
    for(int i=n;i<list.size();i++){
        sum+=list[i].length();
        if(sum==seq[s]){
            flag=isword(s+1,i+1,list);
            break;
        }
        if(sum>seq[s]){
            flag=false;
            break;
        }
    }
    if(flag)return true;
    return false;
}

int main(){
    while(true){
        int n;
        cin >> n;
        if(n==0)break;
        vector<string> list(n);
        for(int i=0;i<n;i++){
            cin >> list[i];
        }
        int ans;
        for(int i=0;i<n;i++){
            if(isword(0,i,list)){
                ans=i+1;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3176
import collections

n = int(input())
al = [int(i) for i in input().split()]
q = int(input())

counter = collections.Counter(al)

total = 0
for (v, c) in counter.most_common():
  total += v * c
for _ in range(q):
  b, c = [int(i) for i in input().split()]
  count = counter[b]
  counter[b] = 0
  counter[c] += count
  total = total + (c - b) * count
  print(total)

Measured memory_bytes: 24812
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int n;
vector<vector<ll>> a(310,vector<ll>(310)),d(310,vector<ll>(310));

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  FOR(i,1,n+1)FOR(j,1,n+1){
    cin>>a[i][j];
    d[i][j]=a[i][j];
  }
  FOR(k,1,n+1)FOR(i,1,n+1)FOR(j,1,n+1) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  FOR(i,1,n+1)FOR(j,1,n+1){
    if(a[i][j]!=d[i][j]){
      cout<<-1<<endl;
      return 0;
    }
  }
  ll ans=0;
  FOR(i,1,n+1)FOR(j,i+1,n+1){
    bool flag=true;
    FOR(w,1,n+1){
      if(w==i||w==j) continue;
      if(d[i][j]==d[i][w]+d[w][j]) flag=false;
    }
    if(flag) ans+=d[i][j];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	N := nextInt()
	v := make([]int, N)
	for i := 0; i < N; i++ {
		v[i] = nextInt()
	}

	sort.Ints(v)

	ave := make([]float64, N)
	ave[0] = float64(v[0])
	for i := 1; i < N; i++ {
		ave[i] = (ave[i-1] + float64(v[i])) / 2
	}

	fmt.Println(ave[len(ave)-1])
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cctype>
using namespace std;
int main(){
    char ch;
    int count[26]= {};
    while(cin >> ch){
        ch = tolower(ch);
        if(isalpha(ch)){
            count[ch-'a']++;
        }
    }
    for(int i=0;i<26;i++){
        printf("%c : %d\n",i+'a',count[i]);
    }
}


Measured memory_bytes: 3148
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;

const lld N = 200043;
const lld MOD = 1000000007;

lld add(lld x, lld y)
{
    x =((x%MOD)+(y%MOD))%MOD;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

lld mul(lld x, lld y)
{
    return ((x%MOD)*(y%MOD))% MOD;
}

lld binpow(lld x, lld y)
{
    lld z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

lld inv(lld x)
{
    return binpow(x, MOD - 2);
}

lld divide(lld x, lld y)
{
    return mul(x, inv(y));
}

// Combinations

/*
lld fact[N];

void precalc()
{
    fact[0] = 1;
    for(lld i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
}

lld C(lld n, lld k)
{
    return divide(fact[n], mul(fact[k], fact[n - k]));
}
*/
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t,i,j;
    //cin>>t;
    t=1;
    while(t--)
    {
        lld a,b,c,d;
        cin>>a>>b>>c>>d;
        lld ar[4]={0};
        ar[0]=max(a,b);
        ar[2]=max(c,d);
        ar[1]=min(a,b);
        ar[3]=min(c,d);
        lld ans=LLONG_MIN;
        for(i=0;i<2;i++)
        {
            for(j=2;j<4;j++)
                ans=max(ans,ar[i]*ar[j]);
        }
        cout<<ans<<endl;

    }
}





Measured memory_bytes: 3612
#include<iostream>

using namespace std;

int main(void)
{
  long long int n,a,b,tmp,ans;
  cin>>n>>a>>b;
  
  tmp=a+b;
  ans=0;
  ans=(n/tmp)*a+min(n%tmp,a);
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
n=int(input())
if 1<=n<10:
    print(n)
elif 10<=n<100:
    print(9)
elif 100<=n<1000:
    print(9+n-99)
elif 1000<=n<10000:
    print(9+900)
elif 10000<=n<100000:
    print(9+900+n-9999)
elif n==100000:
    print(9+900+90000)


Measured memory_bytes: 38384
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  int N, A[100000], kind = 0, temp;

  cin >> N;

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

  sort(A, A+N);

  for(int i = 0;i < N;i++){
    if(temp != A[i] || i == 0){
      kind++;
      temp = A[i];
    }
  }

  if(kind % 2 == 0){
    cout << kind - 1 << endl;
  } else{
    cout << kind << endl;
  }

  return 0;
}


Measured memory_bytes: 640
n = int(input())
a_array = [int(x) for x in input().split()]
flag = True
for a in a_array:
    if a % 2 == 0:
        if a % 3 == 0 or a % 5 == 0:
            continue
        else:
            flag = False
            break
print("APPROVED" if flag else "DENIED")

Measured memory_bytes: 2940
import itertools
S=str(input())
x,y=map(int,input().split())
Move=[len(s) for s in S.split('T')]#偶数番目がｘ軸の移動量、奇数番目がy軸の移動量
x -=Move[0]#初手のみ正の方向
Move_x=Move[2::2]
Move_y=Move[1::2]

def check(d,x):
  se =set([0])
  for dx in d:
    se={a+b for a,b in itertools.product(se,[-dx,dx])}
  return (x in se)

print('Yes' if check(Move_x,x) and check(Move_y,y) else 'No')


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

int a[6];

int main (){

    int x , y ;
    cin >> x >> y ;

    if ((y%2!=0)||(y>4*x)||(y<2*x))
        cout << "No";

    else
        cout << "Yes";

return 0 ;
}


Measured memory_bytes: 3636
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)

main :: IO ()
main = do
    _ <- B.getLine
    as <- map (fst . fromJust . B.readInt) . B.lines <$> B.getContents
    print $ length $ filter (odd . length) $ group $ sort as


Measured memory_bytes: 15612
import java.util.*;
public class Main {
	public static void main(String[] args) {
			Scanner scan = new Scanner(System.in);
			int[] k = new int[10000];
			while(true) {
				int n,cnt = 0;
				n = scan.nextInt();
				String check = "no";
				if(n == 0) break;
				for(int i = 0; i < n; i++) {
					k[i] = scan.nextInt();
					if(k[i] >= 1) cnt++;
					if(k[i] >= 2) check = "Yes";
				}
				if(check != "Yes") {
					System.out.println("NA");
				} else {
					System.out.println(cnt + 1);
				}
			}
	}
}

Measured memory_bytes: 158540
X = int(input())

if 400 <= X <= 599:
  print(8)
elif 600 <= X <= 799:
  print(7)
elif 800 <= X <= 999:
  print(6)
elif 1000 <= X <= 1199:
  print(5)
elif 1200 <= X <= 1399:
  print(4)
elif 1400 <= X <= 1599:
  print(3)
elif 1600 <= X <= 1799:
  print(2)
elif 1800 <= X <= 1999:
  print(1)


Measured memory_bytes: 9176
#include<iostream>
#define ll long long int
using namespace std;
int main()
{
	ll n;
	cin>>n;
	ll a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	
	ll x[n][n],y[n][n];
	
	int i=0;
	while(i<n)
	{
		x[i][i]=a[i];
		y[i][i]=0;
		i++;
	}
	
	for(int k=1;k<n;k++)
	{
		
		int i=0,j=k;
		while(i<n&&j<n)
		{
			ll q=a[i]+y[i+1][j];
			ll w=a[j]+y[i][j-1];
			
			if(q>=w)
			{
				x[i][j]=q;
				y[i][j]=x[i+1][j];
			}
			else
			{
				x[i][j]=w;
				y[i][j]=x[i][j-1];
			}
			i++;j++;
		}
		
	}
	
//    for(int i=0;i<n;i++)
//    {
//    	for(int j=0;j<n;j++)
//    	{
//    		cout<<x[i][j]<<" ";
//		}
//		cout<<endl;
//	}
//	cout<<"*******************"<<endl;
//	 for(int i=0;i<n;i++)
//    {
//    	for(int j=0;j<n;j++)
//    	{
//    		cout<<y[i][j]<<" ";
//		}
//		cout<<endl;
//	}

cout<<x[0][n-1]-y[0][n-1];
}

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

using namespace std;

int n, t[2], a[5][100010], to[100010];
int abs(int x) { return x >= 0 ? x : -x; }

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
  for (register int i = 1; i <= n; i++) {
    to[i] = a[2][i] / 3 + 1;
    if (!((a[1][i] - a[2][i] == -1 && a[2][i] - a[3][i] == -1 &&
           a[1][i] % 3 == 1) ||
          (a[1][i] - a[2][i] == 1 && a[2][i] - a[3][i] == 1 &&
           !(a[1][i] % 3))) ||
        (abs(i - to[i]) & 1)) {
      puts("No");
      return 0;
    }
    t[i & 1] ^= (a[1][i] > a[2][i]);
  }
  for (register int i = 1; i <= n; i++) {
    while (to[i] != i) {
      t[(i & 1) ^ 1] ^= 1;
      swap(to[i], to[to[i]]);
    }
  }
  puts(t[0] || t[1] ? "No" : "Yes");
  return 0;
}


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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL


typedef long long ll;
typedef pair<ll,ll> P;

#define NODE 555555
pair<ll,ll> f[2][NODE];
ll mod[] = {1000000007,1000000009};
ll kake[] = {114514,1919810};
ll inv[2];
int n;
string str;
map<pair<ll,ll>,ll> mp;

ll m_pow(ll a,ll b,ll p){
	ll ret = 1;
	ll tmp = a;
	for(ll i = 0LL;i < 60;i++){
		if(b & (1LL << i)){
			ret *= tmp;
			ret %= p;
		}
		tmp *= tmp;
		tmp %= p;
	}
	return ret;
}

vector<int> RollingHash(string str,string s){
	vector<int> ret;
	ll mark[2] = {};
	REP(i,s.size()){
		REP(j,2){
			mark[j] *= kake[j];
			mark[j] += (int)s[i];
			mark[j] %= mod[j];
		}
	}
	ll po[2];
	REP(i,2)po[i] = m_pow(kake[i],s.size()-1,mod[i]);
	ll now[2] = {};
	REP(i,str.size()){
		bool flag = true;
		REP(j,2){
			if(i >= s.size()){
				ll tmp = po[j] * (int)str[i-s.size()] % mod[j];
				now[j] = (now[j] + mod[j] - tmp) % mod[j];
			}
			now[j] *= kake[j];
			now[j] += (int)str[i];
			now[j] %= mod[j];
			if(now[j] != mark[j])flag = false;
		}
		if(flag)ret.PB(i-s.size()+1);
	}
	return ret;
}

int main(){
	
	string a,b;cin >> a >> b;
	vector<int> ans = RollingHash(a,b);
	REP(i,ans.size()){
		cout << ans[i] << endl;
	}
	
	return 0;
}



Measured memory_bytes: 26756
#include <cstdio>
#include <algorithm>
#include <cstring>

#define re register int

using namespace std;

const int maxn=200010;

int n;
int a[200100];

inline bool check(int x){
    for(re i=0;i<=n-1;i++){
        if((a[n-i]<x&&a[n-i-1]<x)||(a[n+i]<x&&a[n+i+1]<x))
            return false;
        if((a[n-i]>=x&&a[n-i-1]>=x)||(a[n+i]>=x&&a[n+i+1]>=x))
            return true;
    }
    return a[(n<<1)-1]>=x;
}
int main(){
    scanf("%d",&n);
    for(re i=1;i<=(n<<1)-1;i++){
        scanf("%d",&a[i]);
    }
    
    int l=1,r=(n<<1)-1,ans=0;
    
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))
            l=mid+1,ans=mid;
        else
            r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 896
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')


def resolve():
    s = int(input())
    x0, y0 = 0, 0
    if s % (10 ** 9) == 0:
        x1, y1 = 10 ** 9, 0
    else:
        x1, y1 = 10 ** 9, 1

    y2 = (s + x1 - 1) // x1
    x2 = 10 ** 9 - s % x1
    print(x0, y0, x1, y1, x2, y2)
    # print(s - abs(x1 * y2 - x2 * y1))


if __name__ == '__main__':
    resolve()


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

using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i < (n); --i)
#define all(x) (x).begin(), (x).end()
#define gsort(x, n) sort((x), (x + n) greater<int>())
#define rv(s) reverse((s).begin(), (s).end())
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).flont_back(a)
#define eb(x, a) (x).emplaes_back(a)
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1e9 + 7;

signed main()
{
   cin.tie(nullptr);
   ios_base::sync_with_stdio(false);

   int a, b, n, cnt = 0, ans = 0;
   string s, v;
   cin >> n >> a;

   if (n < 10)
   {
      cout << a + (100 * (10 - n)) << '\n';
   }
   else
   {
      cout << a << '\n';
   }
}

Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <string>
#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;
//#define all(v) v.begin(),v.end()
//ll mod = 1000000007 ;
//long double pie = acos(-1) ;
//ll INF = 1000000000000 ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}
//void fix_cout(){cout << fixed << setprecision(20) ;}

int main(){
	ll n,k ;
	cin >> n >> k ;
	map<ll,ll> m ;
	vll a(n),sum(n+1,0) ;
	for(int i=0;i<n;i++){
		cin >> a.at(i) ;
		sum.at(i+1) = sum.at(i)+a.at(i)-1 ;
		sum.at(i+1) %= k ;
	}
	ll ans = 0 ;
	for(int i=0;i<=n;i++){
		if(i<k){
			ans += m[sum.at(i)] ;
			m[sum.at(i)]++ ;
		}else{
			m[sum.at(i-k)]-- ;
			ans += m[sum.at(i)] ;
			m[sum.at(i)]++ ;
		}
	}
//	for(int i=0;i<n+1;i++) cout << sum.at(i) << (i==n?'\n':' ') ;
	cout << ans << endl ;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int x,y,z,k;
  cin >> x >> y >> z >> k;
  vi a(x),b(y),c(z);
  REP(i,x) cin >> a[i];
  REP(i,y) cin >> b[i];
  REP(i,z) cin >> c[i];
  vi ans;
  REP(i,x)REP(j,y){
    ans.eb(a[i]+b[j]);
  }
  sort(rALL(ans));
  ans.resize(min(k,(int)ans.size()));
  vi ans2;
  REP(i,ans.size())REP(j,z){
    ans2.eb(ans[i]+c[j]);
  }
  ans = ans2;
  sort(rALL(ans));
  ans.resize(k);
  for(auto i:ans){
    cout << i << endl;
  }
}


Measured memory_bytes: 57060
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
  int n;
  cin>>n;
  double m = 100000;
  for(int i = 0; i < n; i++){
    m*=1.05;
    m/=1000;
    m=ceil(m);
    m*=1000;
   // cout<<i<<','<<m<<endl;
	//printf("%.0lf\n",m);  
}
  cout<<(int)m<<endl;
}

    

Measured memory_bytes: 1164
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

string encode(int num){
  stringstream ss;
  int i=num/1000;
  if(i>1)ss<<i;
  if(i>0)ss<<"m";
  i=(num%1000)/100;
  if(i>1)ss<<i;
  if(i>0)ss<<"c";
  i=(num%100)/10;
  if(i>1)ss<<i;
  if(i>0)ss<<"x";
  i=num%10;
  if(i>1)ss<<i;
  if(i>0)ss<<"i";
  return ss.str();
}

int decode(string str){
  int result=0;
  int tmp=1;
  for(int i=0;i<str.size();i++){
    if('2'<=str[i]&&str[i]<='9')
      tmp=str[i]-'0';
    else{
      if(str[i]=='m')
	result+=tmp*1000;
      else if(str[i]=='c')
	result+=tmp*100;
      else if(str[i]=='x')
	result+=tmp*10;
      else if(str[i]=='i')
	result+=tmp;
      tmp=1;
    }
  }
  return result;
}

int main(){ _;
  int n;cin>>n;
  REP(i,n){
    string s1,s2;cin>>s1>>s2;
    cout<<encode(decode(s1)+decode(s2))<<endl;
  }
}

Measured memory_bytes: 1224
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
B = []
C = []
for i in range(M):
    tmp_B, tmp_C = map(int,input().split())
    B.append(tmp_B)
    C.append(tmp_C)

def change(A, B, C):
    for i in range(B):
        tmp = heapq.heappop(A)
        if tmp < C:
            heapq.heappush(A, C)
        else:
            heapq.heappush(A, tmp)
            break

ZIP = zip(C, B)

ZIP = reversed(sorted(ZIP))

C, B = zip(*ZIP)

for i in range(M):
    change(A, B[i], C[i])

print(sum(A))

Measured memory_bytes: 107416
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define vv(T) std::vector<std::vector<T>>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

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

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

	ll sum = 1;
	for (int i = 0; i < k-1; ++i)
		sum += A[i];
	
	ll tmp = sum;
	for (int i = k-1; i < n; ++i)
	{
		if (i != k-1)
			sum -= A[i-k];
		sum += A[i];
		if (i != k-1)
		{
			if (sum > tmp)
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
		tmp = sum;
	}
}



Measured memory_bytes: 3980
#include <iostream>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	bool find = false;
	for (int i = 1; !find && i < 10; ++i) {
		if (N%i == 0 && N/i < 10) {
			find = true;
		}
	}
	if (find) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int N,i;
	if(scanf("%d",&N)!=1)return 1;
	for(i=0;i<N;i++) {
		int K,P;
		if(scanf("%d%d",&K,&P)!=2)return 1;
		printf("%d\n",(K-1)%P+1);
	}
	return 0;
}

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

bool check(char s){
  if (s == 'A' || s == 'G' || s == 'C' || s == 'T'){
    return true;
  }
  else{
    return false;
  }
}

int main(){
  string S;
  cin >> S;
  
  int N = (int)(S.length()), ans = 0;
  
  for (int i = 0; i < N; i++){
    int num = 0;
    for (int j = i; j < N; j++){
      if (check(S.at(j)) == true){
        num++;
      }
      else{
        break;
      }
    }
    
    ans = max(ans, num);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3572