akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
from collections import defaultdict
from collections import deque
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, M, AB):

    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)

    def bfs(s):
        q = deque([s])
        done = {}
        done[s] = 0
        prev = {}
        goal = None
        while q:
            u = q.popleft()
            for v in g[u]:
                if v not in done:
                    done[v] = done[u] + 1
                    prev[v] = u
                    q.append(v)
                if v == s:
                    goal = u
                    break
        if goal is None:
            return None
        v = goal
        ans = [s]
        while v in prev:
            ans.append(v)
            v = prev[v]
        return ans

    ans = [0] * (2*N)
    for i in range(1, N+1):
        a = bfs(i)
        if a and len(ans) > len(a):
            ans = a
    if len(ans) == (2*N):
        print(-1)
        return
    print(len(ans))
    print(*ans, sep='\n')


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    slv(N, M, AB)


if __name__ == '__main__':
    main()


Measured memory_bytes: 47964
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const int INF = 2147483647;
const ll MOD = 1000000007;
// const ll INF = 1000000000000000000LL;

int main() {
  int n,k;
  cin >> n >> k;
  vector<double> p(n);
  rep(i,n) cin >> p[i];
  vector<int> sum(n+1);
  rep(i,n){
    sum[i+1] = sum[i]+p[i];
  }
  //隣接するk個のpが最大の最初のindex
  int index=-1;
  int nax = -1;
  rep(i,n-k+1){
    int now;
    now = max(nax,sum[i+k]-sum[i]);
    if(nax<now){
      index = i;
      nax = now;
    }
  }
  double ans=0;
  rep(i,k)
    ans+=(1+p[index+i])/2.l;
  printf("%.10lf",ans);
  return 0;
}


Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define yesno(flg) if(flg){cout<<'YES'<<endl;}else{cout<<'NO'<<endl;}
#define vi vector<int>
#define pb push_back
#define i197 1000000007
#define MAX_N 200002
using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<Pii,int> Piii;
typedef pair<int,ll> Pil;
typedef pair<ll,ll> Pll;
typedef pair<string,int> Psi;
typedef pair<Psi,int> Psii;

const int inf=1000000000;
struct edge{
	int myc,to,c,cost;
};
struct pos{
	int to,cost,color;
};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

vi vec[200001];
int x[200001]={};
int dp[200001];

int main() {
	int a,b;
	cin>>a>>b;
	cout<<max(0,a-2*b)<<endl;
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1LL << 60;
const int MAX = 1000000010;

int main() {
    int x, y, z; cin >> x >> y >> z;
    int cal = (x - z) / (y + z);
    cout << cal << endl;
    return 0;
}

Measured memory_bytes: 256
for i in range(4):
    t,n=map(int,input().split())
    if t==1:
        print(f'{6000*n}')
    elif t==2:
        print(f'{4000*n}')
    elif t==3:
        print(f'{3000*n}')
    elif t==4:
        print(f'{2000*n}')


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

using ll = long long;
#define ld long double
#define ull unsigned long long int

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  // (i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ret return

typedef pair<int, int>    pii;
typedef vector<int>       vi;
typedef vector<vi>        vii;
typedef vector<long long> vl;

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // 入力
    int w, a, b;
    cin >> w >> a >> b;

    // 処理
    if (a + w < b) {
        cout << b - (a + w) << endl;
    } else if (b + w < a) {
        cout << a - (b + w) << endl;
    } else {
        cout << 0 << endl;
    }
    // 出力

    return 0;
}


Measured memory_bytes: 256
n=int(input())
A=list(map(int,input().split()))
print(" ".join(map(str,A)))
for i in range(1,n):
    v=A[i]
    j=i-1
    while j>=0 and A[j]>v:
        A[j+1]=A[j]
        j=j-1
        A[j+1]=v
    print(" ".join(map(str,A)))


Measured memory_bytes: 5596
//g++ -std=gnu++14 a.cpp
//#include <bits/stdc++.h>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main(){
  int  N,K;
  cin >> N >> K;
  vector<int> h(1000000);
  vector<int> dp(1000000, INF);
  for(int i = 1;i <= N;i++) cin >> h.at(i);
  dp[1] = 0;
  for(int i = 1;i < N;i++){
    for(int j = 1;j <= K;j++){
      dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]));
    }
  }
  cout << dp[N] << endl;
}


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

public class AtCoder
{
  public static void Main()
  {
    var abcd = Console.ReadLine().Trim().ToCharArray().Select(e => int.Parse(e.ToString())).ToArray();
    var a = abcd[0];
    var b = abcd[1];
    var c = abcd[2];
    var d = abcd[3];

    var n = Math.Pow(2, 3);
    var op = new int[3];

    var ans = "";

    for(var i=0; i < n; i++)
    {
      op[0] = ((i >> 0) & 1) > 0 ? 1 : -1;
      op[1] = ((i >> 1) & 1) > 0 ? 1 : -1;
      op[2] = ((i >> 2) & 1) > 0 ? 1 : -1;

      var v = a
       + b * op[0]
       + c * op[1]
       + d * op[2];

       if(v == 7) break;
    } 

    var k = new []{ "-", "", "+"};

    Console.WriteLine(a + k[op[0]+1] + b + k[op[1]+1] + c+ k[op[2]+1] + d + "=7");
  }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << -1 << endl;}

//二項係数 mod p
ll modinv(ll n, ll p) {
  ll a = p, u = 1, v = 0;
  while (a) {
    ll t = n / a;
    n -= t * a;
    swap(n, a);
    u -= t * v;
    swap(u, v);
  }
  u %= p;
  if (u < 0) u += p;
  return u;
}

ll ncr(ll n, ll r, ll p) {
  if (n < 0 || r < 0 || n < r) return 0;
  r = min(r, n - r);
  ll ans = 1;
  for (ll i = 0; i < r; i++) {
    ans *= (n - i) % p;
    ans %= p;
  }
  for (ll i = 0; i < r; i++) {
    ans *= modinv(i + 1, p);
    ans %= p;
  }
  return ans;
}

int main() {
  ll n, p = 1000000007;
  cin >> n;

  vll a(n + 1), check(n, -1);
  ll x, y;
  for (ll i = 0; i < n + 1; i++) {
    cin >> a[i];
    if (check[a[i] - 1] == -1) check[a[i] - 1] = i;
    else {
      x = check[a[i] - 1];
      y = i;
    }
  }

  vll ans1(0);
  for (ll i = 1; i <= n + 1; i++) {
    if (i == 1) ans1.push_back(ncr(n + 1 - (y - x), i, p));
    else if (ans1[i - 2] > 0) {
      ll z = ans1[i - 2] * (n + 2 - (y - x + i)) % p;
      z *= modinv(i, p);
      ans1.push_back(z % p);
    }
    else ans1.push_back(ncr(n + 1 - (y - x), i, p));
  }

  vll ans2(0);
  for (ll i = 1; i <= n + 1; i++) {
    if (i == 1) ans2.push_back(ncr(n - (y - x), i - 2, p));
    else if (ans2[i - 2] > 0) {
      ll z = ans2[i - 2] * (n - (y - x + i - 3)) % p;
      z *= modinv(i - 2, p);
      ans2.push_back(z % p);
    }
    else ans2.push_back(ncr(n - (y - x), i - 2, p));
  }

  vector<vll> ans3(n + 1, vll(2));
  for (ll i = 1; i <= n + 1; i++) {
    if (i == 1) {
      ans3[i - 1][0] = ncr(n + 1, i, p);
      ans3[i - 1][1] = ncr(n + 2 - (y - x), i, p);
    }
    else {
      ll z = ans3[i - 2][0] * (n + 2 - i) % p;
      z *= modinv(i, p);
      ans3[i - 1][0] = z % p;
      ll w = ans3[i - 2][1] * (n + 3 - (y - x + i)) % p;
      w *= modinv(i, p);
      ans3[i - 1][1] = w % p;
    }
    ll ans = ans1[i - 1];
    ans += ans2[i - 1];
    ans %= p;
    ans += ans3[i - 1][0];
    ans %= p;
    ans -= ans3[i - 1][1];
    if (ans < 0) ans += p;
    cout << ans << endl;
    //cout << ans3[i - 1][0] << " " << ans3[i - 1][1] << endl;
  }
}

Measured memory_bytes: 9844
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vb = vector<bool>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
using vbvb = vector<vector<bool>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int mod = 1000000007;
const int inf = 1001001001;



int main(void) {
  ll n,a,b;
  cin >> n >> a >> b;
  if((b-a)%2==0)cout << (b-a)/2 << endl;
  else {
    ll ans = 0;
    ans = min((b-(a-1)-1-1)/2+a,(n-(a+(n-b)+1))/2+n-b+1);
    cout << ans << endl;
  }
}






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

using namespace std;

typedef long long int ll;

ll dp[3000][3000];
bool dpv[3000][3000];
vector<int> deq(3000);

ll solve(int l, int r, int flag) { // flag = 1 -> Taro
    if(dpv[l][r])
        return dp[l][r];
    if(l > r)
        return 0;
    if(l == r) {
        dpv[l][r] = true;
        if(flag)            
            return dp[l][r] = deq[l];
        else
            return dp[l][r] = -deq[l];
    }
  	dpv[l][r] = true;
    if(flag) {
        return dp[l][r] = max((ll)deq[l] + solve(l+1, r, 1-flag), (ll)deq[r] + solve(l, r-1, 1-flag));
    } else {
        return dp[l][r] = min(solve(l+1, r, 1-flag) - (ll)deq[l], solve(l, r-1, 1-flag) - (ll)deq[r]);
    }
}

int main() {
    int n, tp;
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> deq[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            dpv[i][j] = false;
        }
    }
    cout << solve(0, n-1, 1) << "\n";
}

Measured memory_bytes: 78592
program abc164b
      implicit none
      integer::a,b,c,d
      integer::i

         read *, a,b,c,d

         do i=1,100
            c=c-b
            if (c<=0) then
               print *, 'Yes'
               exit
            end if

            a=a-d
            if (a<=0) then
               print *, 'No'
               exit
            end if
         end do

   end program abc164b

Measured memory_bytes: 2800
n,m,q=map(int,input().split())
abc=[]
def f(L):
    v=0
    for a,b,c,d in abc:
        #print(L[b-1],L[a-1],c)
        if L[b-1]-L[a-1] !=c:
            pass
        else:
            v+=d
    else:
        return v
def gen(ls):
    res=[]
    for l in ls:
        for j in range(l[-1],m+1):
            ll = l.copy()
            ll.append(j)
            res.append(ll)
    return res

for _ in range(q):
    a,b,c,d=map(int,input().split())
    abc.append((a,b,c,d))
K = [[1]]
for _ in range(n-1):
    K = gen(K)
max_=0
for k in K:
    max_=max(max_,f(k))
print(max_)

Measured memory_bytes: 85284
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int main() {
	int n;
	long long X = 0, x = 0, ans = 1000000000000000000LL;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		X += a[i];
	}
	for (int i = 0; i < n; i++) {
		x += a[i];
		if (i < n - 1)ans = min(ans, abs(X - 2 * x));
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define llong long long
#define pb(a) push_back(a)
#define INF 9999999

using namespace std;

typedef pair<int,int> P;

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

int main(){
	int n,x,m[100];
	cin>>n>>x;
	REP(i,n)cin>>m[i];
	int c=x,ans=0;
	SORT(m,n);
	REP(i,n){
		c-=m[i];
		ans++;
	}
	ans+=c/m[0];
	cout<<ans;
}


Measured memory_bytes: 384
x,y,a,b,c = gets.split.map(&:to_i)
ps = gets.split.map(&:to_i).sort.reverse[0..(x-1)]
qs = gets.split.map(&:to_i).sort.reverse[0..(y-1)]
rs = gets.split.map(&:to_i).sort

while !rs.empty? do
  cand = rs.pop
  min = [ps[-1], qs[-1]].min
  break if min >= cand
  
  if ps[-1] <= qs[-1]
    ps.pop
    ps.unshift cand
  elsif qs[-1]
    qs.pop
    qs.unshift cand
  end
end


count = 0

ps.each {|i| count += i }
qs.each {|i| count += i }

puts count

Measured memory_bytes: 34128
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		while (true)
		{
			int n = sc.nextInt();
			if (n == 0) break;
			long total = 0;
			for (int i = 0; i < n / 4; i++)
			{
				total += sc.nextLong();
			}
			System.out.println(total);
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	int a5=0,a7=0;
	if(a==5)
	{
		a5++;
		
	}
	else if(a==7)
	{
		a7++;
	}
	if(b==5)
	{
		a5++;
		
	}
	else if(b==7)
	{
		a7++;
	}
	if(c==5)
	{
		a5++;
		
	}
	else if(c==7)
	{
		a7++;
	}
	if(a5==2&&a7==1)
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int a;
  int b;
  int c;
  int k;
  cin>>a>>b>>c;
  if (a>b){
    k=a;
    a=b;
    b=k;
  }
  if (b>c){
    k=b;
    b=c;
    c=k;
  }
  if (a>b){
    k=a;
    a=b;
    b=k;
  }
  cout<<a<<" "<<b<<" "<<c<<endl;
}


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

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

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

template <class Key, class T>
using gp_hash_table = __gnu_pbds::gp_hash_table<Key, T>;

#ifdef ENABLE_DEBUG
template <typename T>
void debug(T value) {
  cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  cerr << value << ", ";
  debug(args...);
}
#define DEBUG(...)                              \
  do {                                          \
    cerr << " \033[33m (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ":\033[0m ";        \
    debug(__VA_ARGS__);                         \
    cerr << endl;                               \
  } while (0)
#else
#define debug(...)
#define DEBUG(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  i64 K;
  cin >> K;
  int i = 1;
  int m = 7;
  unordered_set<int> seen;
  for (;; ++i) {
    m %= K;
    if (m == 0) {
      cout << i << endl;
      return 0;
    }
    if (seen.count(m)) {
      cout << -1 << endl;
      return 0;
    }
    seen.insert(m);
    m = m * 10 + 7;
  }
}


Measured memory_bytes: 42636
//chiragjn
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define gibe_de_fast_io_b0ss ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const ll mod = 1e9 + 7;
const ll INF = 0x7FFFFFFFFFFFFFFF/2;
int main(){
    gibe_de_fast_io_b0ss;
    int a, b;
    bool ok = 1;
    vector<int> arr(5, 0);
    for(int i = 0; i < 3; i++) {
        cin>>a>>b;
        arr[a]++;
        arr[b]++;
        if(arr[a] > 2 || arr[b] > 2) {
            ok = 0;
        }
    }
    if(ok) {
        cout<<"YES";
    }
    else {
        cout<<"NO";
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rep3(i, n) for (int i = 1; i < (int)(n+1); i++)
#define rep4(i, s, n) for (int i = (s); i < (int)(n+1); i++)
#define repr(i,n) for (int i = (n-1); i>=0;i--)
#define repr2(i,s,n) for (int i = (n-1); i>=(int)(s);i--)
#define repr3(i,n) for(int i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Grid = vector<vector<int>>;
const ll INF = 10011032323450010;
const ld PI = 3.14159265358979323846;



int main() {
     
    int a,b,c;
    cin>>a>>b>>c;
    if(b-a==c-b){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
return 0;
}



Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXH=100;
const int MAXW=100;

int wantwhite,wantblack;

int h,w;
char g[MAXH][MAXW+1];

void run() {
	scanf("%d%d",&wantwhite,&wantblack);

	h=MAXH,w=MAXW/2;
	REP(x,h) {
		REP(y,w) g[x][y]=y==0?'#':y==w-1?'.':x%2==0?'#':'.';
		g[x][w]='\0';
	}

	int havewhite=1,haveblack=1;
	for(int x=0;x<h;x+=2) for(int y=1;y<w-1;y+=2) if(haveblack<wantblack) g[x][y]='.',++haveblack;
	for(int x=h-1;x>=0;x-=2) for(int y=2;y<w;y+=2) if(havewhite<wantwhite) g[x][y]='#',++havewhite;

	printf("%d %d\n",h,w); REP(x,h) printf("%s\n",g[x]);
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 256
using System;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        long N = sc.NextLong();

        long ans = long.MaxValue;

        for (long i = 1; i * i <= N; i++)
        {
            if (N % i == 0)
            {
                long j = N / i;
                ans = Math.Min(i + j - 2, ans);
            }
        }

        Console.WriteLine(ans);
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
	ll x, k, d;
	cin >> x >> k >> d;
    if (x<0) x *= -1;
    if (x/d>k) {
    	cout << x - k*d << "\n";
        return 0;
    }
    ll mod = x % d;
    ll div = k - x/d;
    if (div%2==0) {
        cout << mod << "\n";
    } else {
        cout << d - mod << "\n";
    }
	
	return 0;
}


Measured memory_bytes: 3636
h,w=map(int, input().split())
a=[list(map(int, input().split())) for i in range(h)]
for i in range(h):
    a[i].append(sum(a[i]))
b=[]
for i in range(w+1):
    s=0
    for j in range(h):
        s+=a[j][i]
    b.append(s)
for i in a:print(*i)
print(*b)


Measured memory_bytes: 6228
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int read(){
    char c;int s=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}while(isdigit(c=getchar()));
    return s*t;
}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
int abs(int x){return x>0?x:-x;}
void mins(int &a,int b){if(a>b)a=b;}
void maxs(int &a,int b){if(a<b)a=b;}
//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
/*------------------------------------------------------------*/
const int inf=0x3f3f3f3f;

int n,l,r,ans;
char s[100010];

int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    bool ok=1;ans=0;
    l=1;r=n;
    while(l<r){
    	if(s[l]==s[r]){
			l++,r--;
		}else
    	if(s[l]=='x'){
    		ans++;l++;
    	}else
    	if(s[r]=='x'){
    		ans++;r--;
    	}else{
    		ok=0;break;
    	}
    }
    if(ok)printf("%d",ans);else printf("-1");
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    auto a = vector<int>(n);
    auto b = vector<int>(n);
    auto c = vector<int>(n - 1);
    for (auto &a_i : a) {
        cin >> a_i;
        a_i--;
    }
    for (auto &b_i : b)
        cin >> b_i;
    for (auto &c_i : c)
        cin >> c_i;

    auto last = -100;
    auto sum = 0LL;
    for (auto a_i : a) {
        sum += b[a_i];
        if (a_i == last + 1)
            sum += c[a_i - 1];
        last = a_i;
    }

    cout << sum;
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);
		int count = 0;
		for (int i = 0; i < n - 2; i++) {
			for (int j = i + 1; j < n - 1; j++) {
				int ab = a[i] + a[j];
				int idx = lowerBound(a, ab);
				count += (idx - j);
			}
		}
		System.out.println(count);
	}

	private static int lowerBound(int[] a, int x) {
		int l = 0;
		int r = a.length;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			if (a[mid] < x) {
				l = mid;
			} else {
				r = mid;
			}
		}
		return l;
	}
}


Measured memory_bytes: 27024
n, m=map(int,input().split())
a=[0]*(m+1)
for _ in range(n):
	s=list(map(int, input().split()))
	for i in range(1, len(s)):
		a[s[i]]+=1
c=0
for i in range(m+1):
	if a[i]==n:
		c+=1
print(c)

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 1000005;
const int MM = 998244353;

ll F[MX], I[MX], IF[MX];

ll pw(ll a, ll b = MM-2){
	ll r = 1;
	while(b){
		if( b&1 ) r = r*a % MM;
		a = a*a % MM; b /= 2;
	}
	return r;
}

ll C(int x, int y){ return F[x+y] * IF[x] % MM * IF[y] % MM; }

int main()
{
	I[1] = 1;
	for(int i = 2; i < MX; i++) I[i] = (MM - MM/i) * I[MM%i] % MM;
	F[0] = IF[0] = 1;
	for(int i = 1; i < MX; i++){
		F[i] = F[i-1] * i % MM;
		IF[i] = IF[i-1] * I[i] % MM;
	}

	int N, M;
	scanf("%d%d", &N, &M);
	if( N > M ) swap(N, M);
	ll ans = M;
	ll tot = IF[N+M] * F[N] % MM * F[M] % MM;
	for(int i = 1; i <= N; i++){
		ans = (ans + tot * C(N-i, M-i) % MM * C(i, i) % MM * pw(2)) % MM;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 23808
/*Coded by::
    **Avinash Tiwary**
    **BE/10298/2015**
    **Production Engineer**
    **Producing <code>**
*/
#include<bits/stdc++.h>
#define buf ios_base::sync_with_stdio (0), cin.tie (0)
typedef long long ll;
typedef double dob;
#define MAX 50010
#define M5 200009
#define M6 2000009
#define M 1000000007
#define INF 5e17
using namespace std;
typedef vector<ll> V;
typedef queue<ll > Q;
typedef stack<ll> S;
typedef pair<ll,ll> P;
#define mp make_pair
#define mt make_tuple
#define pb push_back
ll fac[M6],not_prime[M6],ar[M5];
ll power(ll x,ll n)
{   if(n==0||x==0) return 1;
    else if(n%2 == 0) return power((x*x)%M,n/2);
    else return (x*power((x*x)%M,(n-1)/2))%M;
}
string s[MAX];
void fact(){
    fac[0]=1;
    for(ll i=1;i<M6;i++) fac[i]=(i*fac[i-1])%M;
}
void sieve(){
    not_prime[1]=1; not_prime[0]=1;
    for(ll p=2;p*p<M6;p++){
        if(!not_prime[p]){
            for(ll i=p*2;i<=MAX;i+=p) not_prime[i]=1;
        }
    }
}
int main(){
    buf; 
    //sieve(); 
    //fact();
    ll l,r,i,j,p,q,h,s,d,test,n,ans; //string s; 
    cin>>q>>h>>s>>d;
    cin>>n;
    ans=1e18;
    ans=min(ans,n*4*q);
    ans=min(ans,n*2*h);
    ans=min(ans,n*s);
    if(n%2){
        r=(n/2)*d;
        r=min(r+s,min(r+h*2,r+q*4));
        ans=min(ans,r);
    }
    else{
        ans=min(ans,(n/2)*d);
    }
    cout<<ans;
    return 0;
} 

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

#define INIT    0
#define TRUE    1

int main() {

    int x   = INIT;
    int y   = INIT;
    int tmp = INIT;

    while (TRUE) {
        cin >> x;
        cin >> y;

        if ((x == 0) && (y == 0)) {
            break;
        }
        else {
            if (x > y) {
                tmp = x;
                x   = y;
                y   = tmp;
            }

            cout << x << " " << y << endl;
        }
    }
}

Measured memory_bytes: 1160
#include <iostream>
#include <cstdio>
#include <limits>
using namespace std;

int main() {
  int n, min = numeric_limits<int>::max(), max = numeric_limits<int>::min(), input;
  long long int sum = 0;
  cin >> n;
  for (int i=0; i<n; i++) {
    cin >> input;
    sum += (long long int)input;
    if (input < min) min = input;
    if (input > max) max = input;
  }
  printf("%d %d %lld\n", min, max, sum);
  return 0;
}



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


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

    vector<ll> ryuka(n+1);
    ryuka[0] = 2;
    ryuka[1] = 1;
    for(int i = 0; i < n-1; i++){
        ryuka[i+2] = ryuka[i+1] + ryuka[i];
    }
    cout << ryuka[n] << endl;

}


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

using namespace std;

int main() {
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int a;
   cin >> a;
   string s;
   cin >> s;
   if (a >= 3200)
      cout << s << '\n';
   else
      cout << "red" << '\n';
   return 0;
}


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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

 
int main() {
  int N;
  cin >> N;
  VI h(N), a(N);
  REP(i,N) {
    cin >> h.at(i);
  }
  a.at(1) = abs(h.at(0) - h.at(1));
  FOR(i,2,N) {
    int x,y;
    x = a.at(i-2) + abs(h.at(i-2)-h.at(i));
    y = a.at(i-1) + abs(h.at(i-1)-h.at(i));
    a.at(i) = min(x,y);
  }
  cout << a.at(N-1) << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define endl "\n"
const int MAX= 100005 ;
const long long mod = 1.0e9+7;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t;
t=1;    while(t--)
    {
        int n,m,i,x,y,z;
        cin>>n>>m;
        cout<<n*m<<endl;
    }
    return 0;
}

Measured memory_bytes: 3640
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

n = I()
A = LI()

cnt = [0] * n

sa = set(A)
csa = Counter(A)

for v in sa:
    if cnt[v-1] != 0:
        continue
    cnt[v-1] = csa[v]

for c in cnt:
  print(c)


Measured memory_bytes: 65208
#include<bits/stdc++.h>
using namespace std;
int main()
{     
  unsigned long long a,b[100005],i,c[100005],sum=0;
  scanf("%ld",&a);
  for(i=1;i<=a+1;i++)
  cin>>b[i];
  for(i=1;i<=a;i++)
  cin>>c[i];
  for(i=1;i<=a;i++)
  { 
  	if(b[i]+b[i+1]<=c[i])
  	{
  		sum=sum+b[i]+b[i+1];
  		b[i]=0;
  		b[i+1]=0;
	  }
	  else if(b[i]+b[i+1]>c[i] &&b[i]<=c[i])
	  {
	  	sum=sum+c[i];
		b[i+1]=b[i]+b[i+1]-c[i];
	  	b[i]=0;
	  }
	  else if(b[i]+b[i+1]>c[i] &&b[i]>c[i])
	  {
	  	sum=sum+c[i];
	  	b[i]=b[i]-c[i];
	  }
	  
	}
	
	printf("%ld",sum);
}

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

using namespace std;

#define LL long long
#define Re register
#define U unsigned
#define forn(i,a,b) for(Re int i = a;i <= b;++i)
#define nfor(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define pb push_back
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const double PI=atan(1.)*4.;
const int maxn=1e6+5;
const int inf = 0x3f3f3f3f;
const int mod=2019;
const double e=2.71828182845904523536;
int dir[4][2]={1,0,0,1,-1,0,0,-1};

int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
   	cout.tie(0);
    int l,r;
    cin>>l>>r;
    int mi=min(l+2019,r);
    int mj=max(r-2019,l);
    //cout<<mi<<" "<<mj<<endl;
    int ans=1e9+7;
    for(int i=l;i<=mi;i++)
        for(int j=r;j>=mj;j--)
        {
            if(i==j)continue;
            int res=((i%mod)*(j%mod)%mod);
            ans=min(res,ans);
        }
    cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
a=(`tr 1 1`)
r=0
s=0
for x in ${a[@]}
do
    if((x%10==0))
    then
        s=$((s+x))
    else
        s=$((s+(x/10+1)*10))
        r=$((10-x%10>r?10-x%10:r))
    fi
done
echo $((s-r))


Measured memory_bytes: 3768
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int length = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
		    arr[i] = sc.nextInt();
		}
		int left = -1;
		int right = left + length - 1;
		int min = 0;
		int minIdx = -1;
		StringBuilder sb = new StringBuilder();
		while (true) {
		    left++;
		    right++;
		    if (right >= n) {
		        break;
		    }
		    if (minIdx < left) {
		        min = Integer.MAX_VALUE;
		        for (int i = left; i <= right; i++) {
		            if (min >= arr[i]) {
		                min = arr[i];
		                minIdx = i;
		            }
		        }
		    } else {
		        if (arr[right] <= min) {
		            min = arr[right];
		            minIdx = right;
		        }
		    }
		    if (left > 0) {
		        sb.append(" ");
		    }
		    sb.append(min);
		}
		System.out.println(sb);
	}
}



Measured memory_bytes: 315644
def main():
    S = input()
    L = len(S)
    a, b = 0, 0
    for i in range(L):
        if i % 2 == 0:
            if S[i] == '0':
                a += 1
            else:
                b += 1
        else:
            if S[i] == '1':
                a += 1
            else:
                b += 1
    print(min(a, b))


if __name__ == '__main__':
    main()


Measured memory_bytes: 40688
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<u64>();

    let (n, k) = (line[0], line[1]);

    let h = read_as_vec::<u64>();
    let mut counter = 0;
    for height in h{
        if height >= k{
            counter += 1;
        }
    }

    println!("{}", counter);
}


Measured memory_bytes: 4352
#include <stdio.h>

int main(void)
{
	int A,B,C,n;
	int i,count;
	
	while(scanf("%d%d%d",&A,&B,&C),A,B,C){
		int list[500];
		int a[1000],b[1000],c[1000],r[1000];
		
		for(i=0;i<500;i++){
			list[i]=2;
		}
		
		
		scanf("%d",&n);
		
		for(i=0;i<n;i++){
			scanf("%d%d%d%d",&a[i],&b[i],&c[i],&r[i]);
			if(r[i]==1){
				list[a[i]]=1;
				list[b[i]]=1;
				list[c[i]]=1;
			}
		}
		
		for(i=0;i<n;i++){
			count=0;
			
			if(r[i]==0){
				if(list[a[i]]==1)count++;
				if(list[b[i]]==1)count++;
				if(list[c[i]]==1)count++;
			}
			if(count==2){
				if(list[a[i]]==2)list[a[i]]=0;
				if(list[b[i]]==2)list[b[i]]=0;
				if(list[c[i]]==2)list[c[i]]=0;
			}
		}
		for(i=1;i<=A+B+C;i++){
			printf("%d\n",list[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long mod = 1000000007;
        long ten = 1;
        for (int i = 0; i < N; i++) {
            ten *= 10;
            ten %= mod;
        }
        long nine = 1;
        for (int i = 0; i < N; i++) {
            nine *= 9;
            nine %= mod;
        }
        long eight = 1;
        for (int i = 0; i < N; i++) {
            eight *= 8;
            eight %= mod;
        }
        long ans = (ten-nine-nine+eight)%mod;
        System.out.println((ans+mod)%mod);
    }
    
}

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

int main() {
  int n,m;
  cin >> n >> m;
  vector<vector<int>> a(n,vector<int>(2));
  vector<int> ans(n);
  vector<vector<int>> b(m,vector<int>(2));
  for(int i=0;i<n;i++){
    cin >> a.at(i).at(0) >> a.at(i).at(1);
  }
  for(int i=0;i<m;i++){
    cin >> b.at(i).at(0) >> b.at(i).at(1);
  }
  
  int x,xx;
  for(int i=0;i<n;i++){
    int y=0;
    x = max(a.at(i).at(0) - b.at(0).at(0),-(a.at(i).at(0) - b.at(0).at(0)))
      + max(a.at(i).at(1) - b.at(0).at(1),-(a.at(i).at(1) - b.at(0).at(1)));
    for(int j=1;j<m;j++){
     xx = max(a.at(i).at(0) - b.at(j).at(0),-(a.at(i).at(0) - b.at(j).at(0)))
        + max(a.at(i).at(1) - b.at(j).at(1),-(a.at(i).at(1) - b.at(j).at(1)));
      if(x > xx){
        y = j;
        x = xx;
      }
    }
    ans.at(i) = y+1;
  }
  
  for(int i=0;i<n;i++){
    cout << ans.at(i) << endl;
  }
  return 0;
}


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

using namespace std;
#define ll long long

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int r = count(s.begin(), s.end(), 'R');
    int g = count(s.begin(), s.end(), 'G');
    int b = count(s.begin(), s.end(), 'B');

    ll ans = r * 1LL * g * 1LL * b;
    for (int dif = 1; dif <= n; dif++) {
        for (int i = 0; i < n; i++) {
            if (i + 2 * dif >= n) break;
            if (s[i] != s[i + dif] && s[i] != s[i + 2 * dif] && s[i + dif] != s[i + 2 * dif]) ans--;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
int N;
map<int, vector<P>> mp;
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    while(cin >> N, N)
    {
        mp.clear();
        priority_queue<P, vector<P>, greater<P>> que;
        que.push(P(0, 1e9 + 10));
        for(int i = 0; i < N; i++)
        {
            char ch; cin >> ch;
            if(ch == 'W')
            {
                int l, s; cin >> l >> s;
                P target = que.top(); que.pop();
                int range = target.second - target.first;
                while(range < s)
                {
                    mp[l].push_back(target);
                    s -= range;
                    target = que.top(); que.pop();
                    range = target.second - target.first;
                }
                if(range == s) mp[l].push_back(P(target.first, target.first + s));
                else
                {
                    mp[l].push_back(P(target.first, target.first + s));
                    int left = target.first + s;
                    int right = target.second;
                    que.push(P(left, right));
                }
            }
            else if(ch == 'D')
            {
                int l; cin >> l;
                vector<P> buff = mp[l];
                for(P range : buff) que.push(range);
                mp[l].clear();
            }
            else
            {
                int s; cin >> s;
                int res = -1;
                for(auto x : mp)
                {
                    vector<P> tmp = x.second;
                    for(int i = 0; i < tmp.size(); i++)
                    {
                        if(tmp[i].first <= s and s < tmp[i].second) res = x.first;
                    }
                }
                cout << res << "\n";
            }
        }
        cout << "\n";
    }
    return 0;
}




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

#define MAX_N (100010)

using namespace std;
typedef long long Int;

int par[MAX_N];
Int w[MAX_N];
Int abso[MAX_N];

void init(int N)
{
	for (int i = 0; i < N; i++) par[i] = i;
}

int goup(int x)
{
	if (x == par[x]) return (x);
	else {
		int p = goup(par[x]);
		w[x] += w[par[x]];
		return (par[x] = p);
	}
}

Int weight(int x)
{
	goup(x);
	return (w[x] + abso[x]);
}

void merge(int x, int y, Int z)
{
	z += weight(x) - weight(y);
	x = goup(x); y = goup(y);

	if (x == y) return;
	
	par[y] = x;
	w[y] = z;
}

bool same(int x, int y)
{
	return (goup(x) == goup(y));
}

int main()
{
	int N, Q;

	scanf("%d %d", &N, &Q);

	init(N);

	for (int i = 0; i < Q; i++){
		char s[16];
		scanf("%s", s);

		if (s[0] == 'C'){
			int A, B;
			scanf("%d %d", &A, &B);
			A--; B--;
			if (!same(A, B)) printf("WARNING\n");
			else {
				printf("%lld\n", weight(B) - weight(A));
			}
		}
		else {
			int A, B, C;
			scanf("%d %d %d", &A, &B, &C);
			A--; B--;
			abso[A] += C; abso[B] += C;
			merge(A, B, C);
		}
	}

	return (0);
}

Measured memory_bytes: 3152
#月曜五時間目　実践的プログラミング
#ソートして襲われてはいけない時には、できるだけ護衛をつけるようにすることが最適であるので
#ソートした後に左から貪欲に護衛をつけていって、お金がなくなったらそのまま何もしないと言う戦略で正解した。
#時間:15分
#Princess' Marriage
#学んだこと：ソートして貪欲に考える
#URL: https://onlinejudge.u-aizu.ac.jp/challenges/search/titles/2019
def solve():
    N,M=map(int,input().split())
    if N==0 and M==0:
        #終了条件
        exit()
    else:
        d=[tuple(map(int,input().split())) for _ in range(N)]
        d.sort(key=lambda x:-x[1])
        #襲われたやすいところから優先的に保護するためにソート
        cnt=0
        money=M
        #money=所持金、cnt=襲われる期待値の累計和
        for que in d:
            distance,value=que
            if money>=distance:
                money-=distance
            elif money<distance:
                cnt+=value*(distance-money)
                money=0
        print(cnt)
        return solve()

if __name__=="__main__":
    solve()


Measured memory_bytes: 15372
#include <vector>
#include <functional>
#include <deque>
#include <stdexcept>

template<typename T, typename Container = ::std::vector<T>, typename Compare = ::std::greater<typename Container::value_type>>
class sliding_window {
    using iterator_type = typename Container::const_iterator;
    using value_compare = Compare;
    using value_type = T;
    using const_reference = const value_type &;

    iterator_type right_bound, left_bound, end;
    value_compare comp;
    size_t length;
    ::std::deque<value_type> val;

public:
    void push() {
        if (left_bound == end) {
            throw ::std::runtime_error("already reached to the end");
        }
        const auto &tmp = *left_bound;
        while (!val.empty() && comp(val.back(), tmp))val.pop_back();
        val.push_back(tmp);
        ++left_bound;
        ++length;
    }

    void pop() {
        if (right_bound == left_bound) {
            throw ::std::runtime_error("interval is empty");
        }
        const auto &tmp = *right_bound;
        if (tmp == val.front())val.pop_front();
        ++right_bound;
        --length;
    }

    sliding_window(iterator_type _begin, iterator_type _end, const Compare &_comp = Compare()) : length(0),
                                                                                                 right_bound(_begin),
                                                                                                 left_bound(_begin),
                                                                                                 end(_end), comp(_comp),
                                                                                                 val({}) {}

    const size_t size() const {
        return length;
    }

    const_reference top() const {
        return val.front();
    }

    void resize(size_t n) {
        if (n < length) {
            while (n < length) {
                pop();
            }
        } else {
            while (n > length) {
                push();
            }
        }
    }

    void forward() {
        if (left_bound != end)push();
        pop();
    }

};

#include <iostream>
#include <algorithm>

int main() {
    unsigned long long N, M, K;
    scanf("%llu%llu%llu", &N, &M, &K);

    std::vector<unsigned long long> A(N), dp1(N), dp2(N);
    for (auto &i : A)scanf("%llu", &i);

    std::copy(A.begin(), A.end(), dp1.begin());

    for (unsigned long long i = 1; i != K; ++i) {
        sliding_window<unsigned long long, std::vector<unsigned long long>, std::less<>> slidingWindow(
                dp1.begin() + i - 1, dp1.end());
        std::transform(A.begin() + i, A.end(), dp2.begin() + i, [&i](auto a) { return a * (i + 1); });

        slidingWindow.push();

        for (unsigned long long j = i; j != N; ++j) {
            dp2[j] += slidingWindow.top();
            if (slidingWindow.size() == M)slidingWindow.pop();
            slidingWindow.push();
        }

        std::swap(dp1, dp2);
    }

    std::cout << *std::max_element(dp1.begin(), dp1.end()) << std::endl;

    return 0;
}

Measured memory_bytes: 2560
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())
A = []
for i in range(H + 2):
    A.append([0] * (W + 2))

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            for k in range(3):
                for l in range(3):
                    A[i + k][j + l] += 1

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            A[i + 1][j + 1] = '#'

for i in range(1, H + 1):
    for j in range(1, W + 1):
        print(A[i][j], end='')
    print('')

Measured memory_bytes: 44396
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i <= (n); i++)
#define repi(i,a,b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;

int main() {
  int N, K, X, Y;
  cin >> N >> K >> X >> Y;
  
  cout << X*min(N,K) + Y*max(0,N-K) << endl;
}


Measured memory_bytes: 256