akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){

    int n,m;
    while(cin>>n>>m&&!(n==0&&m==0)){
        int sum=0;
        vector<pair<int,int> > vpii;
        for(int i = 0; i < n; i++){
            int d,p;
            cin>>d>>p;
            sum+=d;
            vpii.push_back(make_pair(p,d));
        }
        sort(vpii.begin(),vpii.end(),greater<pair<int,int> > ());
        if(sum<=m)
            cout<<0<<endl;
        else{
            int idx=0;
            while(1){
                if(vpii[idx].second<m){
                    m-=vpii[idx].second;
                    vpii[idx].second=0;
                    idx++;
                }
                else{
                    vpii[idx].second-=m;
                    break;
                }
            }
            int sumExp=0;
            for(int i = 0; i < vpii.size(); i++){
                sumExp+=vpii[i].first*vpii[i].second;
            }
            cout<<sumExp<<endl;
        }
    }

    return 0;
}

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

int main()
{
	char str[3];
	int k;
	gets(str);
		if (str[0] == str[1]) 
		{
			if (str[2] == str[3] && str[0] != str[2]) 
			{
				printf("Yes");
			}
			else 
			{
				printf("No");
			}
		}
		else if (str[0] == str[2])
		{
			if (str[1] == str[3] && str[0] != str[1])
			{
				printf("Yes");
			}
			else
			{
				printf("No");
			}
		}
		else if (str[0] == str[3])
		{
			if (str[1] == str[2] && str[0] != str[1])
			{
				printf("Yes");
			}
			else
			{
				printf("No");
			}
		}
		else
		{
			printf("No");
		}

	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

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


		int N = sc.nextInt();
		int[] h = new int[N];
		for(int i=0;i<h.length;i++){
			h[i] = sc.nextInt();
		}
		int[] cost = new int[N];
		int[] d1 = new int[N];
		int[] d2 = new int[N];

		cost[0] = 0;
		cost[1] = h[0] - h[1];
		if(cost[1]<0){
			cost[1] = cost[1]*(-1);
		}
		d1[0] = 0;
		d2[0] = 0;
		d2[1] = 0;


		int cost1 = 0;
		int cost2 = 0;


		for(int i=2;i<N;i++){
			d1[i] = h[i] - h[i-1];
			if(d1[i]<0){
				d1[i] = d1[i]*(-1);
			}
			d2[i] = h[i] - h[i-2];
			if(d2[i]<0){
				d2[i] = d2[i]*(-1);
			}

			cost1 = cost[i-1] + d1[i];
			cost2 = cost[i-2] + d2[i];
			if(cost1<cost2){
				cost[i] = cost1;
			} else {
				cost[i] = cost2;
			}
		}

		System.out.println(cost[N-1]);



	}

}


Measured memory_bytes: 50696
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[200005];
void init(){
    n = read();
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    sort(a, a + n)  ;
}
void solve(){
    for (int i = 0; i < n - 1; ++i){
        if (a[i] == a[i + 1]){
            printf("NO\n");
            return ;
        }
    }
    printf("YES\n");
}
int main(){
    init();
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define mem(x,y)		(x*)malloc(sizeof(x)*(y))

int int_sort(const void* a,const void* b)
{
	if(*(int*)a > *(int*)b)
	{
		return -1;
	}
	else if(*(int*)a < *(int*)b)
	{
		return 1;
	}
	return 0;
}

int main()
{
	int n,a,b,c;
	int* list;
	int i;
	scanf("%d",&n);
	scanf("%d %d",&a,&b);
	scanf("%d",&c);
	list = mem(int,n);
	for(i = 0;i < n;i++)
	{
		scanf("%d",&list[i]);
	}
	qsort(list,n,sizeof(int),int_sort);
	int cal = c;
	int cost = a;
	for(i = 0;i < n;i++)
	{
		if((double)cal/(double)cost < (double)(cal+list[i])/(double)(cost+b))
		{
			cal+= list[i];
			cost+=b;
		}
		else
		{
			break;
		}
	}
	printf("%d\n",cal/cost);
	return 0;
}

Measured memory_bytes: 0
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

s = 0
for i in range(N):
	s += 1/A[i]

print(1/s)

Measured memory_bytes: 5832
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  int sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    sum += A[i];
  }
  sort(A.begin(), A.end());
  //   for (int i = 0; i < N; i++) {
  //     cout << A[i] << endl;
  //   }

  double target = (double)A[N - M];
  double min = (double)sum / (4 * M);

  if (target < min) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  return 0;
}


Measured memory_bytes: 888
#include <iostream>

int main()
{
    int h, w;
    std::string str[50];
    std::cin >> h >> w;
    for (int i = 0; (i < h); ++i) {
        std::cin >> str[i];
    }
    for (int i = 0; (i < h); ++i) {
        for (int j = 0; (j < w); ++j) {
            if (str[i][j] == '.') {
                str[i][j] = '0';
            }
        }
    }
    for (int i = 0; (i < h); ++i) {
        for (int j = 0; (j < w); ++j) {
            if (str[i][j] == '#') {
                for (int ii = -1; (ii <= 1); ++ii) {
                    if ((i + ii >= 0) && (i + ii < h)) {
                        for (int jj = -1; (jj <= 1); ++jj) {
                            if ((j + jj >= 0) && (j + jj < w)) {
                                if (((ii != 0) || (jj != 0)) && (str[i + ii][j + jj] != '#')) {
                                    ++str[i + ii][j + jj];
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; (i < h); ++i) {
        std::cout << str[i] << std::endl;
    }
    return 0;
}


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

int N, *X;

void input() {
    cin >> N;
    X = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> X[i]; 
    }
}

void solve() {
    int ans;
    int sum = 0;
    for (int i = 1; i <= 100; i++) {
        for (int j = 0; j < N; j++) {
            sum += (X[j] - i) * (X[j] - i);
        }
        if (i == 1) {
            ans = sum;
        } else {
            if (sum < ans) {
                ans = sum;
            }
        }
        sum = 0;
    }
    cout  << ans << endl;
}

void free() {
    delete[] X;
}

int main() {
    input();
    solve();
    free();
    return 0;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int main() {
    long double x, y;
    cin >> x >> y;
    cout << (int)(log2(y / x)) + 1 << endl;
}

Measured memory_bytes: 640
// luogu-judger-enable-o2
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
void judge(int x)
{
	if(x<0)
	{
		x=-x;
		printf("-");
	}
	if(x>=10)
		judge(x/10);
	putchar('0' + x % 10);
}
int main()
{
	int n;
	string s,t;
	scanf("%d",&n);
	cin>>s>>t;
	for(int i=n;i>=1;--i)
		if(s.substr(n-i,i)==t.substr(0,i))
		{
			judge(2*n-i);
			printf("\n");
			return 0;
		}
	judge(2*n);
	printf("\n");
}

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

using namespace std;

int main(int argc, char const* argv[])
{
	int n{};
	int lent{100000};
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		lent += lent * 0.05;
		if (lent % 1000) {
			lent = (lent / 1000) * 1000;
			lent += 1000;
		}
	}
	cout << lent << std::endl;
	return 0;
}

Measured memory_bytes: 2980
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    inp = [int(x) for x in input().split()]
    A[i] = inp[0]
    B[i] = inp[1]

def sort(index):
    if len(index) <= 1:
        return index
    
    min_i = []
    max_i = []

    for i in index[1:]:
        if(B[i] < B[index[0]]):
            min_i.append(i)
        elif(B[i] > B[index[0]]):
            max_i.append(i)
        else :
            if (A[i] <= A[index[0]]):
                min_i.append(i)
            else:
                max_i.append(i)
    max_i.append(index[0])
    
    result = sort(min_i)
    result = result + sort(max_i)

    return result

si = sort(list(range(N)))
total = 0
for i in si:
    total += A[i]
    if(total > B[i]):
        print("No")
        exit()
print("Yes")

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

const int mod = 1000000007;
auto func=[](ll i, ll j) { return abs(i) < abs(j); };

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  // プラスとマイナスに分ける
  vector<ll> ps;
  vector<ll> ms;
  for(auto v : a) {
    if(v >= 0) {
      ps.push_back(v);
    } else {
      ms.push_back(v);
    }
  }

  vector<ll> ans_vec;

  if(k == n) {
    for(auto v : a) {
      ans_vec.push_back(v);
    }
  }
  else if(ps.size() == 0 && k % 2 == 1) {
    sort(a.begin(), a.end(), func);
    rep(i, k) {
      ans_vec.push_back(a[i]);
    }
  }
  else {
    sort(ps.begin(), ps.end(), greater<ll>());
    sort(ms.begin(), ms.end(), less<ll>());

    int ps_cur = 0;
    int ms_cur = 0;
    while(ans_vec.size() < k) {
      ll p = -1;
      if(ps_cur+1<ps.size()) {
        p = ps[ps_cur] * ps[ps_cur+1];
      }
      ll m = -1;
      if(ms_cur+1<ms.size()) {
        m = ms[ms_cur] * ms[ms_cur+1];
      }
      if(p > m || ans_vec.size() + 1 == k) {
        ans_vec.push_back(ps[ps_cur]);
        ps_cur += 1;
      } else {
        ans_vec.push_back(ms[ms_cur]);
        ans_vec.push_back(ms[ms_cur+1]);
        ms_cur += 2;
      }
    }
  }

  mint ans = 1;
  for(auto v : ans_vec) {
    ans *= v;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 9432
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1LL<<62;
const int MAX = 1e5;

int main() {
    string s; cin >> s;
    set<char> st;
    rep(i,s.size()) st.insert(s[i]);
    rep(i,26) {
        auto itr = st.find(char('a'+i));
        if (itr == st.end()) {cout << char('a' + i) << endl; return 0;}
    }
    cout << "None" << endl;
}

Measured memory_bytes: 512
#include <iostream>

using namespace std;

void submit(int a, int b){
    if(a > b){
        for(int i = 0; i < a; i++)
            cout<<b;
        } else if(b > a){
            for(int i = 0; i < b; i++)
                cout<<a;
        } else{
            for(int i = 0; i < a; i++)
                cout<<a;
        }
}
int main()
{
    int n, m;
    cin>>n>>m;
    submit(n, m);

    return 0;
}


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

int main()
{
    ll n,W,i,j;
    cin>>n>>W;

    ll A[n+1][2];
    for(i=1;i<=n;i++)
        cin>>A[i][0]>>A[i][1];

    ll dp[W+1],temp[W+1];

    for(i=0;i<=W;i++)
        dp[i]=0;
    
    temp[0]=0;

    for(j=1;j<=n;j++)
    {
        for(i=1;i<=W;i++)
        {
            if(i>=A[j][0])
                temp[i]=max(dp[i],dp[i-A[j][0]]+A[j][1]);
            else
                temp[i]=dp[i];
        }

        for(i=1;i<=W;i++)
            dp[i]=temp[i];
    }

    cout<<dp[W]<<"\n";
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        ans += a - 1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}

//がんばってputintつくるかぁ
const int MAX = 10000;
const int dm = 1 << 17;
char dn[dm], * di = dn, * owad = dn + dm - 20;
class shuturyoku_unko {
public:
	char C[MAX * 4];
	shuturyoku_unko() : C() {
		rep(i, MAX) {
			int X = i;
			rep(j, 4) {
				C[i * 4 + 3 - j] = '0' + X % 10;
				X /= 10;
			}
		}
	}
	void putint(ll A) {
		if (owad < di) {
			fwrite(dn, 1, di - dn, stdout);
			di = dn;
		}
		int dig = 1;
		if (A >= 100000000) {
			if (A >= 10000000000) dig = 3;
			else if (A >= 1000000000) dig = 2;
			memcpy(di + 4 + dig, C + A % 10000 * 4, 4);
			A /= 10000;
			memcpy(di + dig, C + A % 10000 * 4, 4);
			A /= 10000;
			memcpy(di, C + A * 4 + 4 - dig, dig);
			di += 8 + dig;
		}
		else if (A >= 10000) {
			if (A >= 10000000) dig = 4;
			else if (A >= 1000000) dig = 3;
			else if (A >= 100000) dig = 2;
			memcpy(di + dig, C + A % 10000 * 4, 4);
			A /= 10000;
			memcpy(di, C + A * 4 + 4 - dig, dig);
			di += 4 + dig;
		}
		else {
			if (A >= 1000) dig = 4;
			else if (A >= 100) dig = 3;
			else if (A >= 10) dig = 2;
			memcpy(di, C + A * 4 + 4 - dig, dig);
			di += dig;
		}
		*di++ = '\n';
	}
} f;



int A[100001];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();
	ll kotae = 0;
	rep(i, N) {
		int kari = getint();
		A[kari]++;
		kotae += kari;
	}

	int Q = getint();
	rep(i, Q) {
		int b = getint();
		int c = getint();

		A[c] += A[b];
		kotae += A[b] * ll(c - b);
		A[b] = 0;

		f.putint(kotae);
	}


	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

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

int main(){
  int n;
  int I[1001],P[1001],Q[1001],R[1001],C[1001];
  
  while(cin >> n ,n){
    for(int i=0;i<n;i++){
      cin >> I[i] >> P[i] >> Q[i] >> R[i];
      C[i] = P[i]*4 + Q[i]*9 + R[i]*4;
    }
    cin >> P[n] >> Q[n] >> R[n] >> C[n];
    
    int ans = 0;
    for(int i=0;i<n;i++){
      if(P[i]<=P[n] && Q[i]<=Q[n] && R[i]<=R[n] && C[i]<=C[n]){
	cout << I[i] << endl;
	ans++;
      }
    }
    if(!ans)cout << "NA\n";
  }
}

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    cout << ((n-1)+(k-1)-1) / (k - 1)<< endl;
    return 0;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define debug2(x, y)                       \
  cerr << "(" << #x << "," << #y << ") = " \
       << "(" << x << "," << y << ")\n"
#define all(x) x.begin(), x.end()
#define each(a, x) for (auto& a : (x))
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define int long long
#define yn(x) puts((x ? "Yes" : "No"))
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
const int MX = 1e5 + 5, INF = 5LL << 57, MOD = 1e9 + 7;

int N, M;
string S;
vi va, vb;

void input() {
  ;
  int K,A,B;
  cin>>K;
  cin>>A>>B;
  bool ans = false;
  rep(i,1,1212){
    if (A <= K*i && K*i <= B){
      ans=true;
      break;
    }
  }
  cout<<(ans? "OK" : "NG");
  ;
}
void solve() {
  ;
  ;
}
signed main() {
  cout << setprecision(12);
  input();
  solve();
  return 0;
}

Measured memory_bytes: 3676
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val sequence = readLine()!!.split(' ').map { it.toInt() }
    readLine()!!.toInt()
    val questions = readLine()!!.split(' ').map { it.toInt() }

    fun f(i: Int, m: Int): Boolean {
        if (m == 0) {
            return true
        }
        if (i >= n) {
            return false
        }
        val r1 = f(i + 1, m)
        val r2 = f(i + 1, m - sequence[i])
        return r1 || r2
    }

    questions.forEach {
        println(if (f(0, it)) "yes" else "no")
    }

}


Measured memory_bytes: 32848
#define _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <unordered_map> //C++11
using namespace std;

typedef long long ll;

int n;
ll a[100001], s[100001];

int main() {
	cin >> n;
	cin >> a[0];
	s[0] = a[0];
	for (int i = 1; i < n; i++) {
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	ll m1 = 0, m2 = 0;
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (i % 2 == 0) {
			if (sum <= 0) {
				m1 += abs(sum) + 1;
				sum = 1;
			}
		}
		else {
			if (sum >= 0) {
				m1 += abs(sum) + 1;
				sum = -1;
			}
		}
	}
	sum = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (i % 2 == 0) {
			if (sum >= 0) {
				m2 += abs(sum) + 1;
				sum = -1;
			}
		}
		else {
			if (sum <= 0) {
				m2 += abs(sum) + 1;
				sum = 1;
			}
		}
	}
	cout << min(m1, m2) << endl;
	return 0;
}

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

#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

#define int long long
using namespace std;
const int INF = 2e16;
const int MOD = 1e9 + 7;
const int MB = 20;

vector<int> get(vector<int>& a) {
	int l = 0, r = 0;
	vector<int> z(a.size());
	for (int i = 1; i < a.size(); i++) {
		if (r >= i) {
			z[i] = min(z[i - l], r - i + 1);
		}
		while (i + z[i] < a.size() && a[i + z[i]] == a[z[i]]) {
			z[i]++;
		}
		if (i + z[i] - 1 > r) {
			l = i;
			r = i + z[i] - 1;
		}
	}
	return z;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}

	vector<int> one(n - 1), two(n - 1);
	for (int i = 0; i < n - 1; i++) {
		one[i] = a[i] ^ a[i + 1];
		two[i] = b[i] ^ b[i + 1];
	}
	one.pb(a[n - 1] ^ a[0]);
	two.pb(b[n - 1] ^ b[0]);
	vector<int> q = two;
	q.pb(-1);
	for (int i : one) q.pb(i);
	for (int i : one) q.pb(i);

	vector<int> z = get(q);
	vector<pair<int, int>> ans;
	for (int i = n + 1; i <= 2 * n; i++) {
		if (z[i] >= n) {
			ans.pb({ i - n - 1, a[i - n - 1] ^ b[0]});
		}
	}
	for (auto& p : ans) {
		cout << p.first << " " << p.second << '\n';
	}
}

signed main() {
	/*
	freopen("search.in", "r", stdin);
	freopen("search.out", "w", stdout);
	*/
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cout << fixed;
	cout.precision(12);
	solve();
}

Measured memory_bytes: 28048
N,M = gets.split.map &:to_i
es = {}
rs = {}
(N+M-1).times{ n,m = gets.split.map &:to_i; es[n] ||= {}; rs[m] ||= {}; es[n][m] = rs[m][n] = 1 }
sorted = IO.popen("tsort", "r+") {|io|
  io.puts es.map{ |n,h| h.keys.map{ |m| [n,m] } }.flatten.join(" ")
  io.close_write
  io.readlines.join
}.split.map(&:to_i)

dp = Array.new(N+1,0)
sorted.each{ |n|
  (es[n] || {}).keys.each{ |m| dp[m] = dp[n] + 1 if dp[n] >= dp[m] }
}
puts (1..N).map{ |m|
  (rs[m] || {}).keys.find{ |n| dp[m] - 1 == dp[n] } || 0
}


Measured memory_bytes: 97260
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int n,k;

vector<int> a;

bool OK(long long id)
{
	long long cnt=0;
	for(int i=0;i<n;i++)
	{
		cnt+=((a[i]+id-1)/id-1);
	}
	//cout << cnt << endl;
	return (cnt<=k);
}

int main()
{
	cin >> n >> k;
	a=vector<int>(n);
	for(int i=0;i<n;i++)
		cin >> a[i];
	
	long long left=0,right=1000000000;
	while (right - left > 1)
	{
		long long mid = left + (right - left) / 2; // 区間の真ん中
		//cout << left << "\t" << right << endl;
		if(OK(mid))
			right=mid;
		else
			left=mid;
	}

	cout << right << endl;



}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std; 
const int MOD = 1e9 + 7 ; 

signed main() {
	int h , w ; cin >> h >> w ; 
	vector<vector<char> > grid(h+1,vector<char> (w+1,0)) ; 
	for (int i = 1; i < h+1; ++i) {
		for (int j = 1; j < w+1; ++j) {
			cin >> grid[i][j] ; 
		}
	}
	vector<vector<int> > dp(h+1,vector<int> (w+1,0)) ; 
	for (int i = 1; i < h+1; ++i) {
		if ( grid[i][1] != '.' ) break ; 
		else dp[i][1] = 1 ; 
	}
	for (int i = 1; i < w+1; ++i) {
		if ( grid[1][i] != '.' ) break ; 
		else dp[1][i] = 1 ; 
	}
	for (int i = 2; i < h+1; ++i) {
		for (int j = 2; j < w+1; ++j) {
			if ( grid[i][j] == '.' ) {
				dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD ; 
			}
		}
	}
	cout << dp[h][w] << endl ;
	return 0 ; 
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll n,m;
ll u[N],v[N],f[N];
ll ans[N],cnt[N];
int find(int x){
    return f[x]==x?f[x]:f[x]=find(f[x]);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
    }
    ans[m]=n*(n-1)/2;
    for(int i=1;i<=n+1;i++) f[i]=i,cnt[i]=1;
    for(int i=m-1;i>=1;i--){
        int fx=find(u[i+1]),fy=find(v[i+1]);
        if(fx==fy) ans[i]=ans[i+1];
        else{
            ans[i]=ans[i+1]-cnt[fx]*cnt[fy];
            f[fx]=fy;
            cnt[fy]+=cnt[fx];
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}
const int MAX_N=105;
int dp[3][MAX_N];
int grid[3][MAX_N];
int n;
int main()
{
	cin>>n;
	For(i,1,2)
	{
		For(j,1,n)
		{
			cin>>grid[i][j];
		}
	}
	For(i,1,2)
	{
		For(j,1,n)
		{
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
		}
	} 
	cout<<dp[2][n]<<endl;
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a,b,x,c;
	while(1){
		scanf("%d %d",&a,&b);
		if(a==0&&b==0) break;
		if(a<b){
			x=a; a=b; b=x;
		}
		c=0;
		while(b!=0){
			a=a%b; x=a; a=b; b=x; c++;
		}
		printf("%d %d\n",a,c);
	}
	return 0;
}

Measured memory_bytes: 2588
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

void print(){ std::cout << std::endl; }
template<typename H> void print(H&& head){ std::cout << head << std::endl; }
template<typename H, typename... T> void print(H&& head, T&&... tail){
  std::cout << head << " ", print(std::forward<T>(tail)...);
}

int main()
{
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::ios::sync_with_stdio(false);

  ll K;
  std::cin >> K;

  ll ans = 0LL;
  for (ll a = 1; a <= K; a++) {
    for (ll b = 1; b <= K; b++) {
      ll x = std::__gcd(a, b);
      for (ll c = 1; c <= K; c++) {
        ll y = std::__gcd(x, c);
        ans += y;
      }
    }
  }

  print(ans);
  return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=405,Mod=998244353;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,A[MAXN],B[MAXN],F[MAXN][MAXN][MAXN],iFac[MAXN],Inv[MAXN],Fac[MAXN],w,N,ans;
inline int Fp(int x,int k){int ans=1;for(;k;k>>=1,x=1ll*x*x%Mod)if(k&1)ans=1ll*ans*x%Mod;return ans;}
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();
	Rep(i,1,n)A[i]=read(),B[i]=read(),w+=A[i],N+=B[i];
	iFac[0]=Fac[0]=1;Rep(i,1,MAXN-1)Inv[i]=Fp(i,Mod-2),iFac[i]=1ll*iFac[i-1]*Inv[i]%Mod,Fac[i]=1ll*Fac[i-1]*i%Mod;
	F[0][0][0]=Mod-1;
	Rep(i,1,n)Rep(j,0,w)Rep(k,0,N){
		F[i][j][k]=F[i-1][j][k];int tmp=1;
		if(j>=A[i])Rep(l,0,min(k,B[i]-1))F[i][j][k]=(F[i][j][k]-1ll*F[i-1][j-A[i]][k-l]*tmp%Mod*iFac[l]%Mod+Mod)%Mod,tmp=1ll*tmp*A[i]%Mod;
	}
	Rep(i,0,w)Rep(j,0,N)ans=(ans+1ll*w*Inv[i]%Mod*Fp(Inv[i],j)%Mod*F[n][i][j]%Mod*Fac[j])%Mod;
	cout<<ans<<'\n';
	return 0;
}




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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_H = 11;
const int MAX_W = 1001;

int H, W, K;
string S[MAX_H];

int countW(int x, int sy, int gy)
{
  int ret = 0;
  FOR(y,sy,gy) {
    ret += (S[y][x] == '1' ? 1 : 0);
  }
  return ret;
}

int wc[MAX_H];

int solve(int bit)
{
  vector<II> vec;
  int l = 0;
  int r = 1;
  REP(h,H-1) {
    if((bit >> h) & 1) {
      vec.push_back(II(l,r));
      l = r;
      r = l+1;
    } else {
      r++;
    }
  }
  vec.push_back(II(l,r));

  memset(wc, 0, sizeof(wc));

  int ret = 0;
  REP(x,W) {
    REP(vi,vec.size()) {
      wc[vi] += countW(x, vec[vi].first, vec[vi].second);
      if (wc[vi] > K) {
        return INF;
      }
    }
    if (x < W-1) {
      bool check = false;
      REP(vi,vec.size()) {
        if (wc[vi] + countW(x+1, vec[vi].first, vec[vi].second) > K) {
          check = true;
        }
      }
      if (check) {
        memset(wc, 0, sizeof(wc));
        ret++;
      }
    }
  }

  return ret;
}

signed main()
{
  cin >> H >> W >>K;
  REP(h,H) {
    cin >> S[h];
  }

  int ans = INF;
  REP(s,(1 << H-1)) {
    ans = min(__builtin_popcount(s) + solve(s), ans);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 384
import sys,bisect,heapq

mod = 10**9+7

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(input())

def GCD(a,b):
    while(a%b != 0):
        a,b = b,a%b
    return b

def LCM(a,b):
    return a*b//GCD(a,b)

def main():
    N = I()
    A = LI()

    count_m = 0
    for a in A:
        if a < 0:
            count_m += 1
    A_abs = [abs(a) for a in A]

    if count_m %2 == 0:
        return(sum(A_abs))
    else:
        return(sum(A_abs)-2*(min(A_abs)))

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


Measured memory_bytes: 60832
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    }
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! chmax {
    ($x:expr, $e:expr) => {
        if $x < $e {
            $x = $e;
        }
    };
}
macro_rules! chmin {
    ($x:expr, $e:expr) => {
        if $x > $e {
            $x = $e;
        }
    };
}

const INF: i64 = 1 << 60;

use std::iter::IntoIterator;

fn join_string<T, S>(elems: T) -> String
where
    T: IntoIterator<Item = S>,
    S: ToString,
{
    elems
        .into_iter()
        .map(|i| i.to_string())
        .collect::<Vec<String>>()
        .join(" ")
}

fn main() {
    input!{
        N: usize,
        A: [i64; N],
    }
    let mut x = vec![0; N];
    for i in 0..N {
        if (i+1) % 2 != 0 {
            x[0] += A[i];
        } else {
            x[0] += -A[i];
        }
    }
    x[0] /= 2;
    for i in 0..(N-1) {
        x[i+1] = A[i] - x[i];
    }
    let x: Vec<i64> = x.into_iter().map(|i| i * 2).collect();
    println!("{}", join_string(x));
}


Measured memory_bytes: 14588
import sys
input = lambda: sys.stdin.readline().rstrip()

# BinaryIndexedTree
# O(logN)で累積和取得と値の更新
# add(i,x)...i番目にxを加算
# sum(i,j)...[i,j)の累積和を取得
class BinaryIndexedTree:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a

n,q=map(int,input().split())
a=list(map(int,input().split()))
Bit=BinaryIndexedTree(n)
for i in range(n):Bit.add(i,a[i])
for _ in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    Bit.add(a,b)
  else:
    print(Bit.sum(a,b))

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

int main(void)
{
	string S;
	cin >> S;
	
	bool flg = false;
	for (int i = 97; i <= 122; ++i) {
		flg = false;
		for (int j = 0; j < S.length(); ++j) {
			if (i == S[j]) {
				flg = true;
				break;
			}
		}
		if (!flg) {
			cout << char(i) << endl;
			return 0;
		}
	}
	
	cout << "None" << endl;

	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>

int main(void) {
  int m, f, r, i, j;
  while( 1 ) {
    scanf("%d%d%d", &m, &f, &r);
    if(m == -1 && f == -1 & r == -1) break;
    if(m == -1 || f == -1 || m + f < 30) {
      printf("F\n");
      continue;
    }
    int s = m + f;
    if(s >= 80) printf("A\n");
    else if(s >= 65) printf("B\n");
    else if(s >= 50) printf("C\n");
    else if(s >= 30) {
      if(r >= 50) printf("C\n");
      else printf("D\n");
    }
  }
  return 0;
}


Measured memory_bytes: 2592
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
const double PI = 3.14159265358979323846;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  bool flag = false;
  if(b - a == c - b) flag = true;
  if(flag) cout << "YES" << endl;
  else cout << "NO" << endl;
}

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


int main() {
    long long X,x = 0,ans;
    cin >> X;

    if ((X%1000)/100>=5) x = (X%1000)/100 - 5;
    else x = (X%1000)/100;


    ans = 1000*(X/500) + 100*x + 5*((X%100)/5);

    cout << ans << endl ;
    

}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys
import os

#input_text_path = __file__.replace('.py', '.txt')
#fd = os.open(input_text_path, os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())

a, b, c = list(map(int, input().split()))
if a < b < c:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 7652
C = 1_000_000_007

n, m = gets.split.map(&:to_i)
broken = m.times.map {gets.to_i}

dp = Array.new(n + 1)
dp[0] = 1
dp[1] = 1
broken.each {|s| dp[s] = 0}

(2..n).each do |i|
  dp[i] = (dp[i - 1] + dp[i - 2]) % C unless dp[i]
end

puts dp[n]

Measured memory_bytes: 3764
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<complex>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
#define MOD 1000000007
#define EPS (long double) 1e-8
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};

int main(void) {
	while(1) {
		int n, m, p;
		cin>>n>>m>>p;
		if(n == 0 && m == 0 && p == 0) break;
		vector<int> x(n);
		int sum = 0;
		REP(i, n) {
			cin>>x[i];
			sum += x[i] * 100;
		}
		ll res = 0;
		if(x[m - 1] != 0) res = sum * (100 - p) / 100 / x[m - 1];
		cout<<res<<endl;
	}
}

Measured memory_bytes: 3024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String NS = scanner.next();
		scanner.close();

		int NI = Integer.parseInt(NS);
		int A = 0;

		for (int n = 0; n < NS.length(); n++) {
			String ns = NS.substring(n, n + 1);
			int a = Integer.parseInt(ns);
			A = A + a;
		}
		if (NI % A == 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}
}

Measured memory_bytes: 21844
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n = sc.read();
    let lr = (0..n)
        .map(|_| (sc.read(), sc.read()))
        .collect::<Vec<(i64, i64)>>();
    let inv = lr.iter().map(|&(l, r)| (-r, -l)).collect();
    println!("{}", cmp::max(solve(lr), solve(inv)));
}

fn solve(lr: Vec<(i64, i64)>) -> i64 {
    let n = lr.len();
    let mut left = lr
        .iter()
        .enumerate()
        .map(|(i, &(l, _))| (l, i))
        .collect::<Vec<_>>();
    left.sort();
    left.reverse();
    let mut right = lr
        .iter()
        .enumerate()
        .map(|(i, &(_, r))| (r, i))
        .collect::<Vec<_>>();
    right.sort();

    let mut cur = 0;
    let mut ans = 0;
    let mut used = vec![false; n];
    let mut left = left.into_iter();
    let mut right = right.into_iter();
    while let Some((_, i)) = left.next() {
        if used[i] {
            continue;
        }
        used[i] = true;
        let (l, r) = lr[i];
        if cur < l {
            ans += l - cur;
            cur = l;
        } else if r < cur {
            ans += cur - r;
            cur = r;
        }

        while let Some((_, i)) = right.next() {
            if used[i] {
                continue;
            }
            used[i] = true;
            let (l, r) = lr[i];
            if cur < l {
                ans += l - cur;
                cur = l;
            } else if r < cur {
                ans += cur - r;
                cur = r;
            }

            break;
        }
    }
    ans + cur.abs()
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

int a[10];

int main() {
    int n, x, y, f;
    cin >> n;
    while (n--) {
        for (int i = 0; i < 10; i++) cin >> a[i];
        x = y = f = 0;
        for (int i = 0; i < 10; i++) {
            if (a[i] > x)
                x = a[i];
            else if (a[i] > y)
                y = a[i];
            else {
                f = 1;
                break;
            }
        }
        if (f)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}


Measured memory_bytes: 2952
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n, m;std::cin >> n >> m;
  ll one_time = m*1900+(n-m)*100;
  std::cout << (1<<m)*one_time << '\n';
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
	unsigned int N, M, X, a;
	int cost_front_sum = 0, cost_back_sum = 0;
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		cin >> a;
		if (a < X)
			cost_front_sum++;
		else
			cost_back_sum++;
	}

	if (cost_front_sum > cost_back_sum) 
		cout << cost_back_sum << endl;
	else
		cout << cost_front_sum << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

A = ['SUN', 'MON', 'TUE' , 'WED' ,'THU', 'FRI', 'SAT']

S = input()

for i in range(7):
    if A[i] == S:
        print(7-i)
        exit()


Measured memory_bytes: 9060
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
using namespace std;

int next(int L, int a) {
  char format[256], str1[256], str2[256];
  sprintf(format, "%%0%dd", L);
  sprintf(str1, format, a);
  strcpy(str2, str1);
  sort(str1, str1 + L);
  sort(str2, str2 + L, greater<int>());
  return atoi(str2) - atoi(str1);
}

int main() {
  int a, L;
  while (scanf("%d%d", &a, &L), a|L) {
    map<int, int> S;
    for (int i = 0; ; ++i) {
      if (S.count(a)) {
        printf("%d %d %d\n", S[a], a, i - S[a]);
        break;
      } else {
        S.insert(make_pair(a, i));
        a = next(L, a);
      }
    }
  }
}

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

int main(){

    while(1){
        int N;
        cin>> N;
        if(N==0) break;

        int ans=0;
        for(int l=2; l<=50; l++){
            for(int i=1; i<N; i++){
                int s=(2*i+l-1)*l/2;
                ans+=s==N;
            }
        }

        cout<< ans<< endl;

    }

    return 0;
}

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename A,typename B>istream&operator>>(istream&is,pair<A,B> &p){is>>p.fi>>p.se;return is;}
template<typename A,typename B>ostream&operator<<(ostream&os,const pair<A,B> &p){os<<"("<<p.fi<<","<<p.se<<")";return os;}
template<typename T>istream&operator>>(istream&is,vector<T> &t){REP(i,t.size())is>>t[i];return is;}
template<typename T>ostream&operator<<(ostream&os,const vector<T>&t){os<<"{";REP(i,t.size()){if(i)os<<",";os<<t[i];}cout<<"}";return os;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n;
    cin>>n;
    vi vec(n-1);
    cin>>vec;
    int ans=vec[0]+vec.back();
    FOR(i,1,n-1){
        ans+=min(vec[i-1],vec[i]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <array>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vsort(x) sort(x.begin(),x.end())

using int64 = uint64_t;

using namespace std;
template<typename T>
void ccout(T* array, int length) {
	int c;
	cout << array[0];
	for (c = 1;c < length;c++) {
		cout << " " << array[c];
	}
}
void solve(int a) {
	int x[3];
	x[2] = a % 60;
	a /= 60;
	x[1] = a % 60;
	a /= 60;
	x[0] = a;
	ccout<int>(x, 3);
	cout << endl;
}
int main() {

	int i, j, k;
	int a[3][2] = {};
	int x, y, z;
	rep(i, 0, 6) {
		cin >> x >> y >> z;
		a[i / 2][i % 2] = x * 3600 + y * 60 + z;
	}
	rep(i, 0, 3) {
		solve(a[i][1] - a[i][0]);
	}
	return 0;
}

Measured memory_bytes: 3076
// ConsoleApplication2.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cctype>
using namespace std;

int main() {
    int n, a[21] = {}, b[20] = {}, c[20] = {}, p = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n-1; i++) {
        cin >> c[i];
    }
    for (int i = 0; i < n; i++) {
        p += b[a[i]-1];
        if (a[i + 1] == a[i] + 1) p += c[a[i]-1];
    }
    cout << p << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
namespace nym
{
	typedef long long ll;
	const int N=2010,MOD=1000000007;
	template<typename T>inline void inc(T a,T &b){b=(a+b)%MOD;}
	int n,m,k;
	ll f[N],g[N];
	void solve()
	{
		scanf("%d%d%d",&n,&m,&k);
		f[0]=g[0]=1;
		ll ans=0,tmp;
		int lim=(n+m)/(k-1)+10;
		for(int i=1;i<=lim;i++)
		{
			for(int j=1;j<=n;j++)g[j]=(g[j-1]+f[j])%MOD;
			for(int j=1,dj;j<=n;j++)
			{
				if(j<k)tmp=g[j-1];
				else tmp=g[j-1]-g[j-k];

				dj=i*(k-1)-j;
				if(j%(k-1)==n%(k-1) && dj<m && dj%(k-1)==(m-1)%(k-1))
					inc(tmp,ans);
				inc(tmp,f[j]);
			}

//			printf("pos %d : ",i);
//			for(int j=0;j<=n;j++)
//				printf("%lld ",f[j]);
//			printf("\n");
		}
		printf("%lld\n",(ans%MOD+MOD)%MOD);
	}

}
int main()
{
	nym::solve();
	return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
s=['.'+input()+'.' for _ in range(h)]
s=['.'*(w+2)]+s+['.'*(w+2)]
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=='#':
            if s[i-1][j]=='.' and s[i+1][j]=='.' and s[i][j-1]=='.' and s[i][j+1]=='.':
                print('No')
                exit()
print('Yes')

Measured memory_bytes: 3064
import { readFileSync } from 'fs'
function main() {
  const input = readFileSync('/dev/stdin', 'utf8')
  const [n, s] = input.split('\n').map(v => v.trim())
  const half = Number(n) / 2
  const str = s.substr(0, half)
  const str2 = s.substr(half)
  console.log(str === str2 ? 'Yes' : 'No')
}
main()

Measured memory_bytes: 7372