akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;


int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    int A[N]; rep(i, N) cin >> A[i];
    vector<int> vec;
    rep(i, N){
        if(i == 0) vec.push_back(A[i]);
        else{
            auto it = lower_bound(vec.begin(), vec.end(), A[i]);
            if(it == vec.begin()){
                vec.insert(it, A[i]);
            }
            else{
                it--;
                *it = A[i];
            }
        }
    }
    //rep(i, vec.size()) cout << vec[i] << " "; cout << endl;
    cout << vec.size() << endl;
    return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define U [1<<17]={}
typedef long long L;using namespace std;map<L,L> T U;L P U,E U,Z U,H U,C U,A U,O U,X U,B U,k,n,a,b,c,p,r;char s U;
L D(L a){L d;Z[a]=1;for(map<L,L>::iterator I=T[a].begin();d=I->first,I!=T[a].end();I++){
    d-P[a]?P[d]=a,E[d]=E[a]+1,C[d]=I->second,D(d),Z[a]+=Z[d],!H[a]|Z[H[a]]<Z[d]?H[a]=d:0:0;}}
L G(L a){r=A[a]+A[P[a]]+C[a];return r%k?r:0;}
L M(L i){return i?B[i]+M(i-(i&-i)):0;}
L S(L x,L i){for(x=G(x)-M(i+1)+M(i++);i<1<<17;B[i]+=x,i+=i&-i);}
L W(){for(c=0;p=X[a],n=X[b],p-n;a=P[p])E[p]<E[n]?swap(p,n),swap(a,b),0:0,c+=M(O[a])-M(O[p])+G(p);cout<<c+abs(M(O[a])-M(O[b]))<<endl;}
main(){for(cin>>n>>k;++p<n;T[a][b]=T[b][a]=c)cin>>a>>b>>c;
       for(D(c=p=0);p<n;p++)if(!p|H[P[p]]-p)for(a=p;!c|a;S(a=H[a],O[a]=c++))X[a]=p;
       for(cin>>a;cin>>s>>a>>b;*s&2?W():A[a]+=b,S(H[a],O[a]),a?S(a,O[a]-1):0);}

Measured memory_bytes: 33488
#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#define PLL pair<ll, ll>
#define F first
#define S second

using namespace std;

typedef long long ll;

const ll M = 1e9 + 7;
ll n;
ll cnt;
ll ans = 1;
map<PLL, PLL> ma;
ll x, y;

ll gcd(ll p, ll q)
{
    if(q == 0) return p;
    return gcd(q, p % q);
}

ll pow(ll p)
{
    if(p == 0) return 1;
    ll t = pow(p / 2);
    if(p % 2 == 0) return t * t % M;
    else return t * t % M * 2 % M;
}

int main()
{
    scanf("%lld", &n);
    for(ll i = 0; i < n; i++)
    {
        ll t1, t2;
        scanf("%lld%lld", &t1, &t2);
        if(t1 == 0 && t2 == 0)
        {
            cnt++;
            continue;
        }
        else if(t1 == 0)
        {
            x++;
            continue;
        }
        else if(t2 == 0)
        {
            y++;
            continue;
        }
        ll d = gcd(abs(t1), abs(t2));
        if((t1 ^ t2) < 0) ma[make_pair(abs(t1) / d, abs(t2) / d)].F++;
        else ma[make_pair(abs(t2) / d, abs(t1) / d)].S++;
    }
    ans *= (pow(x) + pow(y) + M - 1);
    ans %= M;
    for(auto it:ma)
    {
        ans *= (pow(it.S.F) + pow(it.S.S) + M - 1);
        ans %= M;
    }
    printf("%lld\n", (ans + cnt + M - 1) % M);
    return 0;
}


Measured memory_bytes: 19260
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

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

s = input()
t = input()

if s < t:
	print("Yes")
	sys.exit()
tmp = sorted(s)[0]
for x in t:
	if x > tmp:
		print("Yes")
		break
else:
	print("No")


Measured memory_bytes: 3892
/*g++ main.cpp -o main.out*/
/*./main.out*/
/*std::ios::sync_with_stdio(false);cin.tie(0);*/

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

#define LL long long
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define ree(n,a) memset(n,a,sizeof(n));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int main()
{
    int A,B,C,f=0;
    cin>>A>>B>>C;
    rer(i,1,B)
    {
        if((i*A)%B==C)
        {
            f=1;
            break;
        }
    }
    if(f)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
A,B=map(int,input().split())
cnt=0

for i in range(A,B+1):
    si=str(i)
    flg=True
    for j in range(len(si)//2):
        if si[j]!=si[-(j+1)]:
            flg=False
    
    if flg:
        cnt+=1
        
print(cnt)



Measured memory_bytes: 2940
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,res;
char s[500005];
int main() {
	cin>>s;
	n=strlen(s);
	res=n;
	for(int i=1; i<n; i++) {
		if(s[i]!=s[i-1])
			res=min(res,max(i,n-i));
	}
	cout<<res;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<queue>
#include<set>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,s[105],sum;
bool f[10005];
int main(){
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&s[i]);
	f[0]=1;
	fo(i,1,n){
		sum+=s[i];
		fd(j,sum,s[i])
			if (f[j-s[i]]) f[j]=1;
	}
	fd(i,sum,0) if (f[i]&&i%10!=0){	
		printf("%d\n",i);
		return 0;
	}
	printf("0\n");//!!!
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    ll n;
    cin >> n;
    Vi a(n);
    Vi num(100050,0);
    ll sum=0;
    rp(i,n) {
        cin >> a.at(i);
        num[a[i]]++;
        sum+=a[i];
    }
    ll q;
    cin >> q;
    Vi ans;
    while(q--){
        ll b,c;
        cin >> b >> c;
        num[c]+=num[b];
        sum += (c-b)*num[b];
        num[b]=0;
        ans.pb(sum);
    }
    for(auto an:ans){
        print(an);
    }
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 5848
#include <stdio.h>

#define SIZE 2000000

int main() {
  int A[SIZE];
  int H=0;
  int i, key, l, largest, tmp;
  char com[20];
  do {
    scanf("%s", com);
    if (com[0] == 'i') {
      scanf("%d", &key);
      A[++H] = key;
      for (i=H; i>1 && A[i/2]<A[i];i/=2) {
        tmp = A[i/2];
        A[i/2] = A[i];
        A[i] = tmp;
      }

    } else if (com[1]=='x') { // extract
      printf("%d\n", A[1]);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i*2;
         largest = i;
        if (l < H && A[l] > A[i])        largest = l;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (com[2]!='d');
  return 0;
}


Measured memory_bytes: 5620
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		sc.useDelimiter("\\D+");
		
		final int towns = sc.nextInt();
		final int paths = sc.nextInt();
		
		int[][] relates = new int[towns][towns];
		for(int[] tmp:relates){
			for(int i = 0; i < towns; i++){
				tmp[i] = -1;
			}
		}
		
		for(int i = 0; i < paths; i++){
			final int from = sc.nextInt();
			final int to = sc.nextInt();
			final int go = sc.nextInt();
			final int back = sc.nextInt();
			relates[from-1][to-1] = go;
			relates[to-1][from-1] = back;
		}
		
		final int start = sc.nextInt();
		final int end = sc.nextInt();
		final int price = sc.nextInt();
		final int cost = sc.nextInt();
		
		int first_cost = search(start,end,relates,towns);
		int second_cost = search(end,start,relates,towns);
		
		System.out.println(price - cost - first_cost - second_cost);
	}
	
	private static int search(final int start,final int end,int[][] relates,final int towns){
		
		int[] costs = new int[towns];
		for(int i=0; i<towns; i++){
			costs[i] = Integer.MAX_VALUE;
		}
		costs[start-1] = 0;
		
		Set<Integer> un_used = new HashSet<Integer>(); 
		for(int i = 0; i < towns; i++){
			un_used.add(i);
		}
		
		
		while(!un_used.isEmpty()){
			int cur = -1, cur_cost = Integer.MAX_VALUE;
			
			for(int i : un_used){
				if(cur_cost > costs[i]){
					cur = i;
					cur_cost = costs[i];
				}
			}
			
			un_used.remove(cur);
			
			for(int i = 0; i < towns; i++){
				if(relates[cur][i] != -1){
					if(costs[i] > (costs[cur]+relates[cur][i])){
						costs[i] = costs[cur]+relates[cur][i];
					}
				}
			}
		}
		
		return costs[end-1];
	}
	
}

Measured memory_bytes: 11000
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
using namespace std;

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

vector<pair<ll,int>> factorize(ll n){
    vector<pair<ll,int>> ans;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0)continue;
        ans.emplace_back(i,0);
        while(n%i==0){
           ans.back().second++;
           n/=i;
        }
    }
    if(1!=n) ans.emplace_back(n,1);
    return ans;
}

int main(){
    ll a,b;
    cin>>a>>b;
    ll g=gcd(a,b);
    auto res=factorize(g);
    cout<<res.size()+1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
#include <climits>

const int MAXN = 200001;

long long int solve(int& N, std::vector<int>& d)
{
    std::sort(d.begin(), d.end());

    return d[N/2] - d[N/2-1];
}

int main()
{
    int N; std::cin >> N;
    std::vector<int> d(N, 0);
    for (int i = 0; i < N; i++)
    {
        std::cin >> d[i];
    }

    long long int ans = solve(N, d);

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

Measured memory_bytes: 3728
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ll = long long int;

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

    map<ll, ll> mp;

    for (size_t i = 0; i < Q; i++)
    {
        ll ai;
        cin >> ai;
        mp[ai - 1] += 1;
    }

    vector<ll> ans(N);
    for (size_t i = 0; i < N; i++)
    {
        if (K - Q + mp[i] > 0) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

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

int main(){
    int h,a;
    cin >> h >> a;
    int i = 0;
    int count = 0;
    while(true){
        if((h - a * i) <= 0) break;
        count++;
        i++;
    }
    cout << count << endl;
    return 0;
}    

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  int N;
  int A[200002];
  scanf("%d",&N);
  for(int i=0; i<N; i++){
    scanf("%d",&A[i]);
  }
  
  int flag = 0;
  for(int i=0; i<N; i++){
    if(A[i]==1)flag++;
  }
  if(flag==0){
    printf("-1\n");
    return 0;
  }
  
  int k = 0;
  int j = 0;
  int cnt = 0;
  for(j=1; k<N; j++){
    if(k>=N)break;
    if(j>=N)break;
    for(int i=k; ; i++){
      if(A[i]==j){
        k++;
        break;
      }
      if(i>=N)break;
      cnt++;
      k++;
  	}
  }
  printf("%d\n",cnt);
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n;
	string s;
	cin >> n >> s;
	int ans = 0;
	int x = 0;
	for (auto o : s)
	{
		x += (o == 'I'?1:-1);
		ans = max(ans, x);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
s = [input() for i in range(n)]
m = int(input())
t = [input() for i in range(m)]

maxCount = 0
for i in s:
    if s.count(i) - t.count(i) > maxCount:
        maxCount = s.count(i) - t.count(i)
print(maxCount)

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

int main(){
  int k;
  cin>>k;
  string s;
  cin>>s;
  
  if(s.length()<=k)
    cout<<s<<endl;
  
  string s2;
  if(s.size()>k){
    for(int i=0;i<k;i++){
      s2=s2+s.at(i);
    }
    cout<<s2;
    cout<<"..."<<endl;
  }
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
	LL n,n1;scanf("%lld",&n);
	if(n==2)return puts("1"),0;
	int q=sqrt(n),ans=0;
	for(int i=2;i<=q;i++){
		if(n%i==0){
			LL w=n/i;n1=n;
			while(n1%i==0)n1/=i;
			if(n1%i==1)ans++;
			n1=n;
			if(w==i)continue;
			while(n1%w==0)n1/=w;
			if(n1%w==1)ans++;
		}
		else if((n-1)%i==0){
			ans+=2;
			if(1ll*i*i==n-1)ans--;
		}
	}
	printf("%d",ans+2);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
int prodmod(vector<int> w);
int summod(vector<int> w);
///CUIDADO COM MAXN
#define N 300050

int n, m, q, k, v[N], ans;
pii w[N];
string s;

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>s;
	int ans = 0;
	for(int i  =0; i < sz(s); i++){
		int j = i;
		while(j < sz(s) and s[j] == 'R'){
			j ++;
		}
		ans = max(ans, j-i);
		j=i-1;
	}
	cout<<ans<<"\n";
}
/*
    CUIDADO COM MAXN, MOD, OVERFLOW 
    >Colocar (>DEFINE INT LONG LONG<) no inicio do template
    >mod = (1e9 + 7), por padrao (NAO ESQUECER DE ALTERAR)
    >NAO ESQUECER DEFINE INT LONG LONG
    > N = 1 ? 
*/
int summod(vector<int> w){int curr=0;for(int i=0;i<sz(w); i++){curr = (curr+w[i])%mod;if(curr<0)curr+=mod;}return curr;}
int prodmod(vector<int> w){int curr = 1;
for(int i = 0; i < sz(w); i++){if(w[i] >= mod) w[i] %= mod;curr = (curr * w[i]) % mod;if(curr < 0) curr += mod;}return curr;}

Measured memory_bytes: 3636
#!/usr/bin/ruby
# -*- coding: utf-8 -*-
#fh=open("IPT1_9_A.txt")
fh=STDIN
w = fh.gets.chomp.upcase
count=0
while fh.gets
  break if $_ =~ /^END_OF_TEXT$/
  t = $_.chomp.upcase
  count += t.split.select {|wd| wd == w}.length
end
puts count

Measured memory_bytes: 8620
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  ll H;
  ll W;
  cin >>H>>W;
  
  ll N;
  cin >>N;
  vl a(N);
  rep(i,N) {
cin >>a.at(i);
  }

  ll data[H*W];
  rep(i,H*W) {
data[i]=0;
  }
  
  ll x=0;
  rep(i,N) {
    rep(j,a.at(i)) {
      data[x]=i+1;
      x++;
    }
  }
  ll y=0;
  bool ans=true;
  rep(i,H) {
    rep(j,W) {
      if(i%2==0) {
        cout<<data[i*W+j]<<" ";
      }
      
      else if(i%2!=0) {
        cout<<data[(i+1)*W-1-j]<<" ";
       
      }
   
    }
    cout<<endl;
  }
  
  
  
cout<<endl;  
  
}
        
      
      
     
      
      
    
    

  
 
      
      
  
  
  

Measured memory_bytes: 384
import javax.swing.text.StringContent;
import java.util.*;

public class Main {

    /* チェックリスト
     * 結果はintの範囲を超えていませんか？(必要な時以外はlongを使いましょう)
     * TLEしそうな処理はありませんか？
     */
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        long n = Integer.parseInt(sc.nextLine());
        List<Integer> input = new ArrayList<Integer>();
        for(long i = 0; i < n - 1;i++){
            input.add(Integer.parseInt(sc.next()));
        }
        long max = 0;
        //nが3
        //3回試行して 2 2 5
        int cur = 0;
        long prev = Integer.MAX_VALUE;
        long r = 0;
        for(int i : input){
            if(i > prev){
                r += prev;
            }else{
                r += i;
            }
            prev = i;
            cur++;
        }
        System.out.println(r + input.get(input.size() - 1));
    }
}

Measured memory_bytes: 22732
import heapq
N, M = map(int, input().split())
es = [[] for _ in range(N)]

INF = float("inf")
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))


def djkstra(start, n, es):
    # start：スタート地点のノード
    # n：ノード数
    # es：edges, ある辺のコスト

    # 最初は全部未探索
    costs = [INF] * n
    costs[start] = 0
    checked = [False] * n #調べ終わったノードはTrue
    hq = [(0, start)] # スタートからスタートまでのコスト（＝０）とスタートの番号
    heapq.heapify(hq)
    while hq: # キューに残りがある限り
        cost, v = heapq.heappop(hq) # 取り出す
        if checked[v]:
            continue # 既に調べていたら飛ばす
        checked[v] = True
        costs[v] = cost
        for to, c in es[v]: # ノードvから伸びている辺すべてについて
            if costs[to] <= cost + c:
                continue # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす
            heapq.heappush(hq, (cost+c, to)) # toに行くまでの最短距離がcost+cに更新される
        
    return costs


min_cost = [[] for _ in range(N)]
for i in range(N):
    min_cost[i] = djkstra(i,N,es)

ans = 0
for i in range(len(es)):
    for to, c in es[i]:
        if min_cost[i][to] < c:
            #print("--------")
            #print(i,to,c)
            ans += 1

print(ans//2)
#print(min_cost)

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
int mod = 1000000000+7;

int main(){

	ll n;
	cin>>n;

	ll ans=0,sum=0;
	for(ans=0;sum<n;ans++){
		sum+=ans;
	}

	cout<<ans-1<<endl;

	return 0;
}


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

vector<int> sieve(int n) {
	vector<int> res(1, 2);
	vector<bool> prime(n, true);
	for(int i = 3; i < n; i += 2) {
		if(prime[i]) {
			res.push_back(i);
			for(int j = i * 3; j < n; j += i * 2)
				prime[j] = false;
		}
	}

	return res;
}

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

	const int MAX = 100000;
	vector<int> primes = sieve(MAX / 2 + 30);

	for(int m, a, b; cin >> m >> a >> b, m;) {
		const int sq = (int)sqrt(m);
		const double ab = (double)a / b;
		int p = 0, q = 0;
		for(int i = 0; primes[i] <= sq; ++i) {
			for(int j = i; primes[i] * primes[j] <= m; ++j) {
				if(p * q < primes[i] * primes[j] && a * primes[j] <= b * primes[i]) {
					p = primes[i];
					q = primes[j];
				}
			}
		}

		cout << p << " " << q << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1292
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <functional>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <climits>

using namespace std;

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

const ll MOD = 1000000007;
const ll INF = LLONG_MAX;
const ll MAX_N = 100000;

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


int main() {
	int x,y,a=3, b=3, g1[] = {4,6,9,11};
	cin >> x >> y;
	for (int i = 0; i < 4; i++) {
		if (x == g1[i])a = 1;
		if (y == g1[i])b = 1;
		if (x == 2)a = 2;
		if (y == 2)b = 2;
	}
	if (a == b)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int d[300005];

int check1(int s);
int check2(int s,int N);

int main(void) {
	int N,i,f;
	scanf("%d",&N);
	for(i=0;i<N;i++){
		scanf("%d",&d[i]);
	}
	f=check1(N-1);
	if(f==0){printf("no\n");return 0;}
	f=check2(0,N-1);
	if(f==0){printf("no\n");return 0;}
	else {printf("yes\n");}
	return 0;
}

int check1(int s){
	int i,f;
	if(s==0){return 1;}
	for(i=s-1;i>=0;i--){
		if(d[i]>=10*(s-i)){
			f=check1(i);
			if(f==0){return 0;}else{return 1;}
		}
	}
	return 0;
}

int check2(int s,int N){
	int i,f;
	if(s==N){return 1;}
	for(i=s+1;i<=N;i++){
		if(d[i]>=10*(i-s)){
			f=check2(i,N);
			if(f==0){return 0;}else{return 1;}
		}
	}
	return 0;
}



Measured memory_bytes: 7568
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
 
using namespace std;
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define rrep(i,a,b) for (ll i = a; i >= b; i--)
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
 
using namespace std;
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define rrep(i,a,b) for (ll i = a; i >= b; i--)
#define l(s) s.length()
#define sort(v) sort(v.begin(), v.end());
#define scan(v,n) rep(i,0,n) {ll k; cin >> k; v.pb(k);}
#define print(v,n) {rep(i,0,n) cout << v[i] << " "; cout << endl;}
#define printstr(s,n) {rep(i,0,n) cout << s[i]; cout << endl;}
#define rev(a) reverse(a.begin(), a.end());
#define pb push_back
typedef long long ll;
typedef long double lld;
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
 
const ll mxN=1e5+1;
const ll N=1e18+7;
 
ll dp[mxN+1];
 
  int main() {
      int T=1;// cin >> T;
      while(T--){
          ll n,W,sum=0; cin >> n >> W;
          rep(i,1,100001) dp[i]=N;
          rep(i,0,n) {
              ll w,v;
              cin >> w >> v;
              sum+=v;
              rrep(x,100001,0) {
                  if(x>=v&&dp[x]>dp[x-v]+w) dp[x]=dp[x-v]+w;
              }
          }
          ll ans=0;
          rrep(i,mxN-1,0){
              if(dp[i]<=W){
                  cout << i;
                  break;
              }
          }
          //cout << ans;
      } 
	 return 0;
}


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

using namespace std;

#define MAX 1010
const bool debug = 0;

const long long mod = 1000000007;
int N,M,A[MAX],B[MAX];

void compute() {
  long long ans = 1;
  map<int,int> mp_A, mp_B;
  set<int> put_A, put_B;
  for(int i=0;i<N;++i) mp_A[A[i]] = i;
  for(int i=0;i<M;++i) mp_B[B[i]] = i;
  
  for(int i=N*M;i>=1;--i) {

    bool exist_A = ( mp_A.count(i) != 0 );
    bool exist_B = ( mp_B.count(i) != 0 );

    if( exist_A  && exist_B ) {
      // ans *= 1LL;
      put_A.insert( mp_A[i] );
      put_B.insert( mp_B[i] );
    } else if( exist_A ) {
      if( put_B.empty() ) {
	puts("0");
	return;
      }
      ans *= (long long)put_B.size();
      ans %= mod;
      put_A.insert( mp_A[i] );
    } else if( exist_B ) {
      if( put_A.empty() ) {
	puts("0");
	return;
      }
      ans *= (long long)put_A.size();
      ans %= mod;
      put_B.insert( mp_B[i] );
    } else {
      long long coef = ( (long long)put_A.size() * (long long)put_B.size() );
      coef %= mod;
      coef -= ( N * M - i );
      if( coef < 0LL ) coef += mod;
      ans *= coef;
      ans %= mod;
    }
    
  }
  
  cout << ans << endl;
}

int main() {
  cin >> N >> M;
  for(int i=0;i<N;++i) cin >> A[i];
  for(int i=0;i<M;++i) cin >> B[i];
  compute();
  return 0;
}


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

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

    int h,w,k;
    cin>>h>>w>>k;
    int grid[h][w];
    for(int i=0; i<h; ++i){
        string m;
        cin>>m;
        for(int j=0; j<w; ++j){
            if( m[j] == '.' ){
                grid[i][j] = 0;
            }else{
                grid[i][j] = 1;
            }
        }
    }
    int ans = 0;
    for(int r=0; r<(1<<h); ++r){
        for(int c=0; c<(1<<w); ++c){
            // rows
            set<int> rr , cc;
            for(int row=0; row<h; ++row){
                if( (1<<row) & r ){ rr.insert(row); }
            }
            for(int col=0; col<w; ++col){
                if( (1<<col) & c ){ cc.insert(col); }
            }
            int cnt = 0;
            for(int i=0; i<h; ++i){
                for(int j=0; j<w; ++j){
                    if( grid[i][j] == 1 and rr.find(i) == rr.end() and cc.find(j) == cc.end() ){
                        ++cnt;
                    }
                }
            }
            if( cnt == k ){
                ++ans;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
int D;
long long G;
vector<long long> p, c;

int main() {
    cin >> D >> G;
    p.resize(D); c.resize(D);
    for (int i=0; i<D; i++) cin >> p.at(i) >> c.at(i);

    long long res = 1<<29;
    for (int bit=0; bit<(1<<D); bit++) {
        long long sum = 0;
        long long num = 0;
        for (int i=0; i<D; i++) {
            if (bit & (1<<i)) sum += c.at(i) + p.at(i) * 100 * (i+1), num += p.at(i);
        }
        if (sum >= G) res = min(res, num);
        else {
            for (int i=D-1; i>=0; --i) {
                if (bit & (1<<i)) continue;
                for (int j=0; j<p.at(i); j++) {
                    if (sum >= G) break;
                    sum += 100 * (i+1);
                    num++;
                }
            }
            res = min(res, num);
        }
    }
    cout << res << endl;
}

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

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void run(void){
  int n,k;
  scanf("%d%d",&n,&k);
  int a[1000];
  int i,j;
  for(i=0;i<n;i++) scanf("%d",a+i);
  int64 *b=(int64 *)calloc(n*(n+1)/2,sizeof(int64));
  int len=0;
  for(i=0;i<n;i++){
    int64 sum=0;
    for(j=i;j<n;j++){
      sum+=a[j];
      b[len++]=sum;
    }
  }
  int64 ans=0;
  int bit;
  for(bit=39;bit>=0;bit--){
    int c=0;
    for(i=0;i<len;i++) if((b[i]>>bit)&1) c++;
    if(c>=k){
      ans+=((int64)1)<<bit;
      j=0;
      for(i=0;i<len;i++) if((b[i]>>bit)&1) b[j++]=b[i];
      len=j;
    }
  }
  printf("%lld\n",ans);
}

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


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
using namespace std;
using ll = long long int;

const ll INF = 1LL << 60;
int solve_testcase() {
    int N, M; cin >> N >> M;
    if(N == 0 and M == 0) return 1;

    ll sumA = 0, sumB = 0;
    vector<int> A(N), B(M);
    for(int i=0; i<N; i++) cin >> A[i], sumA += A[i];
    for(int i=0; i<M; i++) cin >> B[i], sumB += B[i];

    ll ans = INF, x = -1, y = -1;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            ll n_sumA = sumA - A[i] + B[j];
            ll n_sumB = sumB + A[i] - B[j];
            if(n_sumA == n_sumB) {
                if(A[i] + B[j] < ans) {
                    ans = A[i] + B[j];
                    x = A[i], y = B[j];
                }
            }
        }
    }

    if(ans != INF) {
        cout << x << " " << y << endl;
    }
    else {
        cout << -1 << endl;
    }
    return 0;
}

int main() {
    while(!solve_testcase());
    return 0;
}



Measured memory_bytes: 3048
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	static ArrayList<Integer> list=new ArrayList<>();
	static void eratos() {
		boolean[] prime=new boolean[10010];
		Arrays.fill(prime, true);
		for(int i=2; i<=10000; i++) {
			if(prime[i]) {
				list.add(i);
				for(int j=2; i*j<=10000; j++) {
					prime[i*j]=false;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			eratos();
			while(sc.hasNext()) {
				int n=sc.nextInt();
				if(n==0) break;
				int s=0, t=0, sum=0;
				int count=0;
				for(;;) {
					while(t<list.size() && sum<n) {
						sum+=list.get(t);
						t++;
					}
					if(sum<n) break;
					if(sum==n) {
						count++;
					}
					sum-=list.get(s);
					s++;
				}
				System.out.println(count);
				
			}

		}
	}
}


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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

const ll MOD = 1000000007;
const double EPS = 1e-9;

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    string march = "MARCH", s;
    vector<ll> cnt(5, 0LL);
    rep(n){
        cin >> s;
        repp(j, 5){
            if(s[0] == march[j]){
                cnt[j]++;
                break;
            }
        }
    }

    ll ans = 0LL;
    rep(3){
        reppp(j, i+1, 4){
            reppp(k, j+1, 5){
                ans += cnt[i] * cnt[j] * cnt[k];
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin,(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool flag){
    if(flag)cout << "Yes" << endl;
    else cout << "No" << endl;
}
void fp(bool flag, string s, string t){
    if(flag)cout << s << endl;
    else cout << t << endl;
}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl x[n];
    cin(i,x);
    intl y[n];
    rep(i,n){
        y[i] = x[i];
    }
    sort(x, x + n);
    intl sen = x[n/2];
    rep(i,n){
        if(y[i] < sen)cout << x[n/2] << endl;
        else cout << x[n/2 - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
typedef long long ll;
const int MAX_N=1e5;

int N;
ll M,A[MAX_N];
ll psm[MAX_N+1];
int main(){
	cin>>N>>M;
	psm[0]=0;
	REP(i,N){
		cin>>A[i];
		psm[i+1]=psm[i]+A[i];
		psm[i+1]%=M;
	}
	map<ll,int> mp;
	ll ans=0;
	REP(i,N+1){
		ans+=mp[psm[i]];
		mp[psm[i]]++;
	}
	cout<<ans<<endl;
	return 0;
}

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

const ll INF = 1001002003004005006ll;

ll dp[305][305];

int main() {
  int n, k;
  cin >> n >> k;
  int m = n-k;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  h.insert(h.begin(),0);
  rep(i,n+1)rep(j,m+1) dp[i][j] = INF;
  dp[0][0] = 0;
  for (int i = 1; i <= n; ++i)rep(j,m) {
    ll now = INF;
    rep(k,i) {
      chmin(now, dp[k][j]+max(0,h[i]-h[k]));
    }
    dp[i][j+1] = now;
  }
  ll ans = INF;
  rep(i,n+1) chmin(ans, dp[i][m]);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
import java.util.*;

//update 2020/1/1 23:01

public class Main{

  static Scanner sc = new Scanner(System.in);
  static StringBuilder sb = new StringBuilder();

  public static void main(String[] args) {

    long n = nextLong();
    long k = nextLong();

    long ans = 0;

    if(n>=k){
      long bai = n/k;
      if(n%k!=0){bai++;}
      k *= bai;
      ans = Math.min(n,Math.abs(n-k));
    }
    else{ //if(n<k)
      ans = Math.min(n,k-n);
    }

    System.out.println(ans);

  }

  static int lcm(int a,int b){
    return a*b*gcd(a,b);
  }

  static int gcd(int a,int b){
    if(a%b!=0){
      return gcd(b,a%b);
    }
    else{
      return b;
    }
  }

  /*
    static String toSmall(String s){
      char c = s.charAt(0);
      //if(Character.isUpperCase(c)){
      if(c<=90){
        c += 32;
      }
      return String.valueOf(c);
    }
    static String toBig(String s){
      char c = s.charAt(0);
      //if(Character.isLowerCase(c)){
      if(c>=97){
        c -= 32;
      }
      return String.valueOf(c);
    }
  */

  static String toSmall(String s){
    return s.toLowerCase();
  }

  static String toBig(String s){
    return s.toUpperCase();
  }

  static String next(){
    return sc.next();
  }

  static int nextInt(){
    return Integer.parseInt(sc.next());
  }

  static long nextLong(){
    return Long.parseLong(sc.next());
  }

  static double nextDouble(){
    return Double.parseDouble(sc.next());
  }

  static String[] splitString(String s){
    return s.split("");
  }

  static char[] splitChar(String s){
    return s.toCharArray();
  }

  static int charToInt(char a){
    return a - 48;
  }

////////////////////////////////////////////
  public static int max(int[] a){
    int lng = a.length;
    int max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
  public static long max(long[] a){
    int lng = a.length;
    long max = a[0];
    for(int i=1;i<lng;i++){
      max = Math.max(max,a[i]);
    }
    return max;
  }
////////////////////////////////////////////

////////////////////////////////////////////
  public static int min(int[] a){
    int lng = a.length;
    int min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
  public static long min(long[] a){
    int lng = a.length;
    long min = a[0];
    for(int i=1;i<lng;i++){
      min = Math.min(min,a[i]);
    }
    return min;
  }
////////////////////////////////////////////

}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<vector<int>> adj;
vector<int> v, c;

int dfs(int n=0, int p=-1, int pos=0) {
  v[n] = c[pos]; pos++;
  for (auto x: adj[n]) {
    if (x!=p) pos = dfs(x,n,pos);
  }
  return pos;
}

int main() {
  int N; cin >> N;
  adj.resize(N); v.resize(N); c.resize(N);
  rep(i,N-1) {
    int a, b; cin >> a >> b; a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  rep(i,N) cin >> c[i]; sort(c.begin(),c.end(),greater<int>());
  dfs();

  ll result = 0; repr(i,1,N) result += v[i];
  cout << result << endl;
  rep(i,N) cout << v[i] << " "; cout << endl;
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  ll A, B;
  char op;
  cin >> A;
  cin >> op;
  cin >> B;
  if (op == '+') {
    cout << (A + B) << endl;
  } else {
    cout << (A - B) << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 2e5;
bool from1[N];
bool toN[N];
bool there_exists(int n)
{
	for(int u = 1; u <= n; u++)
		if(from1[u] && toN[u])
			return true;
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m; cin >> n >> m;
	memset(from1,false,sizeof from1);
	memset(toN,false,sizeof toN);
	for(int i = 0; i < m; i++)
	{
		int u, v; cin >> u >> v;
		if(!(u<=v))
			swap(u,v);
		if(u==1)
			from1[v] = true;
		if(v==n)
			toN[u] = true;
	}
	cout<<(there_exists(n) ? "POSSIBLE" : "IMPOSSIBLE")<<endl;

	cout<<flush;
	return 0;
}

Measured memory_bytes: 640
//https://blog.csdn.net/hesorchen
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define mod 1000000007
#define MAX 100010
char p[5];
int main()
{
    p[1] = p[2] = p[3] = '*';
    int n, m;
    cin >> n >> m;
    int f = 1;
    while (m--)
    {
        int a;
        char b;
        cin >> a >> b;
        getchar();
        if (p[a] != '*' && p[a] != b)
            f = 0;
        else
            p[a] = b;
    }
    if (!f)
        return !printf("-1\n");
    else if (p[1] == '0' && n >= 2)
        return !printf("-1\n");
    else
    {
        if (n == 1 && p[2] == '*' && p[3] == '*')
            if (p[1] != '*')
                cout << p[1] - '0' << endl;
            else
                cout << 0 << endl;
        else if (n == 2 && p[3] == '*')
        {
            if (p[1] == '*')
                p[1] = '1';
            if (p[2] == '*')
                p[2] = '0';
            cout << p[1] << p[2] << endl;
        }
        else if (n == 3)
        {
            if (p[1] == '*')
                p[1] = '1';
            if (p[2] == '*')
                p[2] = '0';
            if (p[3] == '*')
                p[3] = '0';
            cout << p[1] << p[2] << p[3] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

#define FOR(i, start, end) for(ll i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

typedef struct {
    int x;
    int y;
} xy;

int main(void) {
    int N;
    cin >> N;
    
    vector<xy> city(N);
    REP (i, N) {
        cin >> city[i].x;
        cin >> city[i].y;
    }

    double sum = 0;
    REP (i, N) {
        FOR (j, i + 1, N) {
            sum += sqrt(pow(city[i].x - city[j].x, 2.0) + pow(city[i].y - city[j].y, 2.0));
        }
    }

    int nAllPath = (N * N - N) / 2;
    int nRoutePath = N - 1;
    double ans = sum * nRoutePath / nAllPath;
    printf("%.7f\n", ans);

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main()
{
int cnt;
string a,b;
cin >>a >>b;
for(int i=0;i<a.size();i++)
{if(a[i]!=b[a.size()-1-i])
 {cout <<"NO";
  system("pause"); 
  return 0;}
 if(a.size()!=b.size())
 {cout <<"No";
  system("pause"); 
  return 0;}}
 cout <<"YES";
 system("pause"); 
return 0;
}


Measured memory_bytes: 504
import java.util.Scanner;


	public class Main {
		

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
	        
			int n = sc.nextInt();
			int k = sc.nextInt();
			int s = sc.nextInt();
			int a = 0;
			int b = 0;
			
			
			if(s%2==1) {
				a = s/2;
				b = a+1;
			}else {
				a = s/2;
				b = a;
			}
			int x =0;
			
			if((s-1)==a||(s-1)==b) {
				x=s+1;
			}else {
				x=s-1;
			}
			
			if(k==n) {
				for(int i=1;i<=n-1;i++) {
					System.out.print(s+" ");
				}
				System.out.print(s);
			}else if(s==1) {
				for(int i=1;i<=k;i++) {
					System.out.print(1+" ");
				}
				for(int i=1;i<n-k;i++) {
					System.out.print(2+" ");
				}
				if(n-k-1>0) {
					System.out.println(2);
				}
				
			}else {
				if(k%2==1) {
					for(int i=1;i<=(k+1)/2;i++) {
						System.out.print(a+" "+b+" ");
					}
					for(int i=1;i<n-k-1;i++) {
						System.out.print((x)+" ");
					}
					if(n-k-1>0) {
						System.out.print((x));
					}
				}else {
					for(int i=1;i<=k/2;i++) {
						System.out.print(a+" "+b+" ");
					}
					System.out.print(a+" ");
					for(int i=1;i<n-k-1;i++) {
						System.out.print((x)+" ");
					}
					if(n-k-1>0) {
						System.out.print((x));
					}
					
				}
			}
		}
		
	}


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

int main(){
  int N,X;
  int ans=1;
  cin >> N >> X;
  vector<int> L(N);
  for(int i=0;i<N;i++) cin >> L.at(i);
  int d=0;
  for(int i=0;i<N;i++){
    d+=L.at(i);
    if(d<=X) ans++;
  }
  cout << ans << endl;
}


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> t chmax(t&a,u b){if(a<b)a=b; return a;};
template<class t, class u> t chmin(t&a,u b){if(a>b)a=b; return a;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N, K;
  IN(N, K);
  vll a(N);
  REP(i,N) IN(a[i]);

  vvll dp(2, vll(K+1, 0));
  dp[0][0] = 1;
  REP(i,N){
    vll psum(K+1, 0);
    psum[0] = dp[0][0];
    FOR(k,1,K+1) psum[k] = psum[k-1] + dp[0][k];
    REP(k,K+1){
      dp[1][k] = psum[k];
      if(k-a[i]>0) dp[1][k] -= psum[k-a[i]-1];
      dp[1][k] += MOD;
      dp[1][k] %= MOD;
    }
    swap(dp[0], dp[1]);
  }

  mat_print(dp);

  OUT(dp[0][K]);

  return 0;
}

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

d = {}
k = {}
for i in range(-1000,1001):
    d[i] = pow(i,5)
    k[d[i]] = i
i = 1000

while True:
    if X + d[i] in d.values():
        b = i
        a = k[X + d[i]]
        break
    i -= 1

print(a, b)

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

int d, n;
int t[210];
int a[210], b[210], c[210];
int dp[210][210];
int main()
{
  cin >> d >> n;
  for(int i = 1; i <= d; i++)
    cin >> t[i];
  for(int i = 1; i <= n; i++)
    cin >> a[i] >> b[i] >> c[i];

  memset(dp, -1, sizeof dp);
  for(int i = 1; i <= n; i++)
    if(a[i] <= t[1] && t[1] <= b[i])
      dp[1][i] = 0;

  for(int i = 1; i <= d - 1; i++)
    for(int j = 1; j <= n; j++)
      if(dp[i][j] != -1)
	for(int k = 1; k <= n; k++)
	  if(a[k] <= t[i + 1] && t[i + 1] <= b[k])
	    dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abs(c[j] - c[k]));

  int ans = 0;
  for(int i = 1; i <= n; i++)
    if(dp[d][i] != -1)
      ans = max(ans, dp[d][i]);

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

Measured memory_bytes: 1344
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;

int main(){

    int N, M;
    cin >> N >> M;

    long long prob = 1;
    for(int i = 0; i < M; i ++){
        prob *= 2;
    }

    cout << ( (N - M) * 100 + 1900 * M) * prob << endl; 

}

Measured memory_bytes: 768
#!/usr/bin/env python3
import sys
# from typing import List, Tuple, Dict
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


class UnionFind:
    def __init__(self, N):
        # type: (int) -> None
        self.N = N
        self.parent = list(range(N))  # type: List[int]

    def root(self, x):
        # type: (int) -> int
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

    def same(self, x, y):
        # type: (int, int) -> bool
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        # type: (int, int) -> None
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        # type: () -> str
        groups = {}  # type: Dict[int, List[int]]
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result


def kruskal(num_vertices, edges):
    # type: (int, List[Tuple[int, int, int]]) -> int
    """Kruscal法: 最小全域木を求める
    edgesについて破壊的なことに注意
    """
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


N = int(input())
l = []
for i in range(N):
    l.append([i] + list(map(int, input().split())))

edges = []
sorted_x = sorted(l, key=lambda c: c[1])
sorted_y = sorted(l, key=lambda c: c[2])

for e in range(N-1):
    i0, x0, y0 = sorted_x[e]
    i1, x1, y1 = sorted_x[e+1]
    edges.append((i0, i1, x1-x0))

    i0, x0, y0 = sorted_y[e]
    i1, x1, y1 = sorted_y[e+1]
    edges.append((i0, i1, y1-y0))

print(kruskal(N, edges))


Measured memory_bytes: 112560