akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<long,long>
#define pdd pair<double,double>
#define ff first
#define ss second
#define w(x) int x; cin>>x; while(x--)
using namespace std;
void ffast(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
int main()
{
    ffast();
    int n,W;
    cin>>n>>W;
    int wt[n+1];
    int val[n+1];
    for(int i=1;i<=n;i++)
    	cin>>wt[i]>>val[i];
    ll dp[n+1][W+1];
    for(int w=0;w<=W;w++)
    	dp[1][w] = 0;
    dp[1][wt[1]] = val[1];
    for(int i=2;i<=n;i++){
    	for(int w=0;w<=W;w++){
    		dp[i][w] = dp[i-1][w];
    		if(w>=wt[i])
    			dp[i][w] = max(dp[i][w], val[i]+dp[i-1][w-wt[i]]);
    	}
    }
    cout<<*max_element(dp[n],dp[n]+W+1);
}

Measured memory_bytes: 81596
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int a,b;
  char c;
  cin >> a >> c >> b;
  if(c=='+'){
    cout << a+b << endl;
  }else{
    cout << a-b << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1LL << 60;
const int MOD = 1'000'000'007;

template <typename T>
void print(const T &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
}

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

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

// const int MAX = 1010;

int grid[510][510];

struct Move
{
    int y;
    int x;
    int yd;
    int xd;
};

int main()
{
    int H, W;
    cin >> H >> W;
    vector<Move> ans;
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            if (j == W - 1)
            {
                if (i != H - 1)
                {
                    if (grid[i][j] % 2 != 0)
                    {
                        --grid[i][j];
                        ++grid[i + 1][j];
                        Move m = {i, j, i + 1, j};
                        ans.push_back(m);
                    }
                }
            }
            else
            {
                if (grid[i][j] % 2 != 0)
                {
                    --grid[i][j];
                    ++grid[i][j + 1];
                    Move m = {i, j, i, j + 1};
                    ans.push_back(m);
                }
            }
        }
    }
    cout << ans.size() << endl;
    for (auto a : ans)
    {
        cout << a.y + 1 << ' ' << a.x + 1 << ' ' << a.yd + 1 << ' ' << a.xd + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 6316
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>F,R;void setF(int n,int mod){F=R=V<ll>(++n);F[0]=1;FOR(i,1,n)F[i]=F[i-1]*i%mod;R[n-1]=modInv(F[n-1],mod);FORR(i,n-1,1)R[i-1]=R[i]*i%mod;}
//ll comb(int a,int b,int m){return a<b||b<0?0:F[a]*R[b]%m*R[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7; //998244353;
const int N = 1e5;
int n;
string s;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> s;
  int ans = 0;
  FOR(i, 0, n-2) if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') ans++;
  cout << ans << endl;
}

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

int main(){
    int a,b;
    cin >> a >> b;
    int d = a / b;
    int r = a % b;
    double f = double(a) / double(b);
    cout << d << " " << r << " ";
    printf("%lf\n",f);
    return 0;
}



Measured memory_bytes: 3200
s = input()
t = input()
pre_index = 0
ans = 0
for i in t:
  if i not in s:
    ans = -1
    break
  else:
    temp = s[pre_index:]
    if i in temp:
      ans += (temp.index(i)+1)
      pre_index+= (temp.index(i)+1)
    else:
      ans += len(temp)
      pre_index = (s.index(i)+1)
      ans += pre_index
print(ans)

Measured memory_bytes: 3540
#include <iostream>
#include <cctype>
#include <cstdlib>
#include <string>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;

int comp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if(a <= c && c <= b){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
A,B,K=map(int, input().rstrip().split()) #input parameters\
work=[] #make list
for i in range(0,K):
    if A+i<=B:
        print(A+i)
for i in range(0,K):
    if B-K+i+1>=A+K:
        print(B-K+i+1)

Measured memory_bytes: 3060
<?php
  fscanf(STDIN,"%d",$n);
$s=trim(fgets(STDIN));
//print_r($s);
$x=0;
$max=0;
for($i=0;$i<$n;$i++){
  if($s[$i]=='I'){
    $x++;
  }else{
    $x--;
  }
  $max=max($x,$max);
}

echo $max."\n";

Measured memory_bytes: 4604
// In the name of god
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <bitset>
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
using namespace std;
 
template <typename T>
T next_int() {
    T x = 0, p = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ');
    if(ch == '-') {
        p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return p * x;
}
 
string next_token() {
    char ch;
    string ans = "";
    do { ch = getchar(); } while(ch <= ' ');
    while(ch > ' ') {
        ans += ch;
        ch = getchar();
    }
    return ans;
}
 
const long long INF = (long long)1e18;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)1e6 + 227 + 1;    
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;
 
long long bin_pow(long long a, long long b) {
    if(!b) return 1;
    long long ans = bin_pow(a, b / 2);
    ans = ans * ans;
    if(b % 2) ans = ans * a;
    return ans;
}

int main() {
    // freopen(".in", "r", stdin);

    long long n, a, b, c, d; 
    cin >> n >> a >> b >> c >> d;
    n--;

    if(a > b) {
        swap(a, b);
    }

    b -= a;
    a = 0;

    for(int kek = 0; kek <= n; kek++) {
        long long m = n - kek;

        long long l = m * c - kek * d;
        long long r = m * d - kek * c;

        if(b >= l && b <= r) {
            puts("YES");
            return 0;
        }
    }

    puts("NO");
}


Measured memory_bytes: 256
import java.util.Scanner; 

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = Integer.parseInt(scan.nextLine());
        String s = scan.nextLine();
        
        int length = s.length();

        if(k >= length){
            System.out.println(s);
        }else{
            String tmp = s.substring(0, k);
            System.out.println(tmp + "...");
        }

        scan.close();
    }
}

Measured memory_bytes: 38616
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author lynmisakura
 */

#include <iostream>
#include <fstream>

/*
 *  author : lynmisakura
 *  stay hungry, stay foolish, stay home.
 */
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

class EYutori {
public:
    int n,k,c;
    string s;
    vector<int> L,R;
	void solve(std::istream& cin, std::ostream& cout) {
	   cin >> n >> k >> c >> s;
	   L.resize(n,-1),R.resize(n,-1);
	   int current = 0;
	   int job_id = 0;
	   while(current < n){
	       if(s[current] == 'o'){
	          L[current] = ++job_id;
	          current += (c + 1);
	       }else{
	           current++;
	       }
	   }
	   if(job_id > k)return;
	   current = n - 1;
	   while(current >= 0){
	       if(s[current] == 'o'){
	          R[current] = job_id--;
	          current -= (c + 1);
	       }else{
	           current--;
	       }
	   }

	   vector<int> ans;
	   for(int i = 0;i < n;i++){
	       if(L[i] > 0 && L[i] == R[i]){
	           ans.push_back(i+1);
	       }
	   }
	   for(auto i : ans)cout << i << '\n';
	}
};


int main() {
	EYutori solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 4216
#include <iostream>
#include <math.h>
#include <iomanip>
#include <cstdlib>
using namespace std;
int main()
{
	int n, x[1000], y[1000];
	int x_y[1000];
	int p1 = 0;
	double p2 = 0, p3 = 0, pMax = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> y[i];
		x_y[i] = abs(x[i] - y[i]);
		p1 += x_y[i];
		p2 += x_y[i] * x_y[i];
		p3 += x_y[i] * x_y[i] * x_y[i];
		if (i == 0)
			pMax = x_y[i];
		else
			pMax = pMax > x_y[i] ? pMax : x_y[i];
	}
	p2 = sqrt(p2);
	p3 = pow(p3, 1.0 / 3.0);
	cout << fixed << setprecision(6) << p1 << endl << p2 << endl << p3 << endl << pMax << endl;
	return 0;
}


Measured memory_bytes: 3448
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;

int main(){
    int x;
    cin>>x;
    if(x>=30) puts("Yes");
    else puts("No");
}


Measured memory_bytes: 3632
import Data.Char (chr)
 
solve :: Int -> Int -> (Int, String)
solve p n = (q, chr (97 + r) : s)
  where
    (m, s) = if n > p
               then solve (p * 26) (n - p)
               else (n - 1, "")
    (q, r) = m `divMod` 26
 
main :: IO ()
main = getLine >>= putStrLn . snd . solve 26 . read


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    ll N; cin >> N;
    vector<ll> a(N), b(N); REP(i,N) cin >> a[i]; REP(i,N) cin >> b[i];
    ll n1=0, n2=0;
    REP(i,N){
        if(a[i] > b[i]) n1 += a[i]-b[i];
        else n2 += (b[i]-a[i])/2;
    }
    cout << (n1 <= n2 ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;

int main(void)
{
    IOS
    int n, t;
    cin >> n >> t;

    int ans = 100000;
    REP(i,n) {
        int a, b;
        cin >> a >> b;
        if (t >= b) {
            if (ans >= a) ans = a;
        }
    }
    if (ans == 100000) cout << "TLE" << endl;
    else cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 896
#include <iostream>

using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;++i)
    cin>>a[i];
    long b[n-k+1];
    b[0]=0;
    for(int i=0;i<k;++i)
    b[0]+=a[i];
    for(int i=1;i<n-k+1;++i){
        b[i]=b[i-1]-a[i-1]+a[k+i-1];
    }
    for(int i=1;i<n-k+1;++i)
    b[i]>b[i-1]?cout<<"Yes\n":cout<<"No\n";
}

Measured memory_bytes: 5916
a, b = map(int, input().split())

def smsll(a, b):
    return a < b
def big(a, b):
    return a > b
def equal(a, b):
    return a == b

if smsll(a, b):
    print('a < b')
elif big(a, b):
    print('a > b')
elif equal(a, b):
    print('a == b')


Measured memory_bytes: 5600
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, M;
	cin >> N >> M;

	vector<Int> x(M);

	for (Int i = 0; i < M; i++) {
		cin >> x[i];
	}

	sort(x.begin(), x.end());

	vector<Int> L(M - 1);
	for (Int i = 0; i < M-1; i++) {
		L[i] = x[i + 1] - x[i];
	}

	sort(L.begin(), L.end());

	if (N >= M) {
		cout << 0 << endl;
		return 0;
	}

	if (N == 1) {
		cout << x[M - 1] - x[0];
		return 0;
	}

	Int res = 0;
	Int ans = 0;
	for (Int i = M-2; i >=M-N; i--) {
		res += L[i];
		ans = x[M - 1] - x[0] - res;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
N, M = map(int, input().split())
H = [0] + list(map(int, input().split()))

T = [-1 for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())

    T[a] = max(T[a], H[b])
    T[b] = max(T[b], H[a])

cnt = 0

for i in range(1, N + 1):
    if H[i] > T[i]:
        cnt += 1

print(cnt)


Measured memory_bytes: 19996
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int h = sc.nextInt();
		int[] a = new int[n];
		Integer[] b = new Integer[n];
		for(int i = 0 ; i < n ; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(b, Comparator.reverseOrder());
		for(int i = 0 ; i < n ; i++) {
			if(a[n - 1] > b[i]) {
				System.out.println(i + (h + a[n - 1] - 1) / a[n - 1]);
				return;
			}
			h -= b[i];
			if(h <= 0) {
				System.out.println(i + 1);
				return;
			}
			if(i == n - 1) {
				int cnt = (h + a[n - 1] - 1) / a[n - 1];
				System.out.println(n + cnt);
				return;
			}
		}
	}

}


Measured memory_bytes: 85116
# https://atcoder.jp/contests/abc085/tasks/abc085_b

"""
上のほうが餅が小さくなるように重ねる
→ 同じサイズの餅は使えない

同じサイズの餅は1つだけ使って（重複を排除して）
大きいものから重ねていけばいい

何段重ねられるか
= 何種類のサイズの餅があるか
"""

n = int(input())
mochi_set = set()
for i in range(n):
    size = int(input())
    mochi_set.add(size)

print(len(mochi_set))


Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
#define ll long
 
// ll knapsack1(int n, int W){
    
//     ll mat[n][2] = {};
//     for(int i = 0; i < n; i++){
//         cin >> mat[i][0] >> mat[i][1];
//     }
    
    
//     // ll** dp = new ll*[n+1];
//     // for(int i = 0; i < n+1; ++i)
//     //     dp[i] = new ll[W+1];
    
//     ll dp[n+1][W+1] = {};
//     for(int i = 1; i < n+1; i++){
//         int w = mat[i-1][0];
//         ll value = mat[i-1][1];
//         for(int j = 1; j < W+1; j++){
            
//             if(j < w) dp[i][j] = dp[i-1][j];
//             else{
//                 dp[i][j] = max(dp[i-1][j], value + dp[i-1][j-w]);
//             }
//         }
//     }
//     return dp[n][W];
// }
 
 
const ll INF = 1e18L + 5; 
 
int main(){
    int n,W ; cin >> n >> W;
    vector<int> value(n), weight(n);
    
    for(int i = 0; i < n; i++) cin >> weight[i] >> value[i] ;
    int val_sum = 0;
    for(int x : value) val_sum += x;
    
    vector<ll> dp(val_sum+1,INF);
    dp[0] = 0;
    
    for(int i = 0; i < n; i++){
        for(int j = val_sum; j >= value[i]; j--){
            dp[j] = min( dp[j], (dp[j-value[i]]+weight[i]) );
            // if(i==0) cout << j<< "-" << dp[j] << " ";
        }
    }
    
    ll ans = 0;
    for(int i = 0; i <= val_sum; i++){
        if(dp[i] <=W) ans = max(ans,(ll)i);
    }
    
    cout << ans ;
    return 0;
}

Measured memory_bytes: 4024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define ll long long 
using namespace std;
ll n,mi[18],ans,lst;
int main()
{
	scanf("%lld",&n);
	mi[0]=1;
	for(int i=1;i<18;i++)
		mi[i]=mi[i-1]*10;
	ans=lst=0;	
	for(int i=17;i;i--)
	{
		int t=(n/mi[i-1])%10;
		//\cout<<t<<endl;
		if(t>0) ans=max(ans,lst+t-1+(i-1)*9),lst+=t;
	}
	ans=max(ans,lst);
	printf("%lld",ans);
	return 0;
}



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

int main()
{
    size_t N;
    std::cin >> N;
    int64_t v = 0;
    for (size_t n = 1; n <= N; ++n)
    {
        v += (N - 1) / n;
    }

    std::cout << v << std::endl;

    return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#include<queue>
#define RREP(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
typedef long long ll;
using namespace std;


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int A,B,C;
  cin>>A>>B>>C;
  if(C>B&& C>A){
    cout<<"No";
  }else if(C<B&& C<A){
    cout<<"No";
  }else {
    cout<<"Yes";
  }




  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define prique priority_queue
#define Fi first
#define Se second
signed main(){
    int n,x,ans=0;
    cin>>n>>x;
    int a[200000];
    rep(i,n)cin>>a[i];
    for(int i=1;i<n;i++){
        if(a[i-1]+a[i]>x){
            ans+=a[i-1]+a[i]-x;
            a[i]=max((int)(0),x-a[i-1]);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
from collections import deque


def solve(K):
    s = 1
    q = deque()
    q.append(s)
    dists = {}
    dists[s] = 1
    while len(q) > 0:
        n = q.pop()
        if n == 0:
            break
        m = (n*10)%K
        if m not in dists:
            dists[m] = dists[n]
            q.append(m)
        elif dists[m] > dists[n]:
            dists[m] = dists[n]
            q.append(m)
        if n % 10 != 9:
            m = (n+1)%K
            if m not in dists:
                dists[m] = dists[n] + 1
                q.appendleft(m)
            elif dists[m] > dists[n] + 1:
                dists[m] = dists[n] + 1
                q.appendleft(m)
    return dists[0]


def main():
    K = int(input())
    print(solve(K))


if __name__ == '__main__':
    main()


Measured memory_bytes: 15588
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>

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

typedef long long ll;

using namespace std;

ll N;

bool chk(ll target)
{
	if (target == 1) return false;
	ll temp = N;

	while (temp % target == 0) temp /= target;
	if (temp % target == 1) return true;
	return false;
}

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

	scanf("%lld", &N);

	ll ans = 0LL;

	for (ll i = 1; i * i <= N; ++i)
	{
		if (N % i == 0)
		{
			if(chk(i)) ans++;
			if (i != N / i && chk(N / i)) ans++;
		}
	}

	for (ll i = 1; i * i <= N - 1; ++i)
	{
		if ((N - 1) % i == 0)
		{
			if (chk(i)) ans++;
			if (i != (N - 1) / i && chk((N - 1) / i)) ans++;
		}
	}

	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int n,m,p,X,Y,Z,res,b[9][9][9];
int dx[] = {1,0,0,1,1,0,-1,-1, 0,1, 1, 1,-1};
int dy[] = {0,1,0,1,0,1, 1, 0,-1,1, 1,-1, 1};
int dz[] = {0,0,1,0,1,1, 0, 1, 1,1,-1, 1, 1};

int check(void){
  rep(i,n)rep(j,n)rep(k,n){
    if(b[i][j][k]>=0){
      rep(t,13){
	int c=0,tx=i,ty=j,tz=k;
	while(c<m && 0<=tx && tx<n && 0<=ty && ty<n && 0<=tz && tz<n){
	  if(b[tx][ty][tz] == b[i][j][k])c++;
	  else break;
	  tx += dx[t]; ty += dy[t]; tz += dz[t];
	}
	if(c==m)return b[i][j][k];
      }
    }
  }
  return -1;
}

void print(void){
  rep(k,n){
    rep(i,n){
      rep(j,n)cout << b[i][j][k] << " ";
      cout << endl;
    }
    cout << endl;
  }
}

int main(){
  while(cin >> n >> m >> p,n+m+p){
    rep(i,n)rep(j,n)rep(k,n)b[i][j][k] = -1;

    bool f = true;
    rep(i,p){
      cin >> X >> Y; X--; Y--;Z=0;
      while(b[X][Y][Z]>=0)Z++;
      b[X][Y][Z] = i&1;
      //print();
      if(f){
	res = check();
	if(res==0){
	  cout << "Black " << i+1 << endl;
	  f = false;
	}else if(res==1){
	  cout << "White " << i+1 << endl;
	  f = false;
	}
      }
    }
    if(f)cout << "Draw\n";
  }
}

Measured memory_bytes: 1164
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) > (b) ? (b) : (a))
#define abs(x) ((x) > 0 ? (x) : -(x))
#define MOD (ll)1000000007 //10^9 + 7
#define endl printf("\n")
typedef long long ll;
#define MAX_N (1 << 17)

int
main(int argc, char *argv[])
{
  ll k;
  scanf("%lld", &k);

  ll n = (ll)50;
  ll a = k / n;
  ll b = k % n;

  printf("50\n");
  for (ll i = 0; i < b; i++) {
    printf("%lld ", n - i + a);
  }
  for (ll i = 0; i < n - b; i++) {
    printf("%lld ", n - b - 1 - i + a);
  } endl;

  return 0;
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

int main()
{
    int M; cin >> M;
    ll D = 0, S = 0;        // 桁数Dと各桁の和S
    rep(i,M){
        ll di, ci; cin >> di >> ci;
        D += ci;
        S += di*ci;
    }
    ll ans = (D-1)+(S-1)/9;
    cout << ans << endl;
}

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

int main(){
	string s;
	cin>>s;
	int a=0,z=s.size()-1;
	while(s.at(a)!='A')++a;
	while(s.at(z)!='Z')--z;
	cout<<z-a+1<<"\n"s;
}

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

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

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace B
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var n = double.Parse(Console.ReadLine());
            var ai = Console.ReadLine().Trim().Split(' ').Select(double.Parse).ToArray();
            var sum = 0.0;
            for (var i = 0; i < ai.Length; i++)
            {
                sum += 1 / ai[i];
            }
            Console.WriteLine(1 / sum);
        }
    }
}


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




int main()
{
  int64_t X,Y;
  cin >> X >> Y;
  int ans = 1;
  while(true)
  {
    X *= 2;
    if (Y >= X)
    {
      ans++;
    }
    else
    {
      cout << ans << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
h,w,d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
q=int(input())
b=[list(map(int, input().split())) for i in range(q)]
import collections
from collections import defaultdict
x=defaultdict(int)



for i in range(h):
    for j in range(w):
        x[i,j]=a[i][j]
x1=sorted(x.items(),key=lambda x:x[1])

ans=[[0]*(-(h*w//-d)) for i in range(d)]


for i in range(d):
    count=0
    for j in range(1,-(h*w//-d)):
        if i+j*d>=h*w:
            continue
        count+=abs(x1[i+(j-1)*d][0][0]-x1[i+j*d][0][0])
        count+=abs(x1[i+(j-1)*d][0][1]-x1[i+j*d][0][1])
        ans[i][j]+=count

for i in range(q):
    u=(b[i][0]-1)%d
    u1=(b[i][0]-1-u)//d
    v=(b[i][1]-b[i][0])//d

    print(ans[u][u1+v]-ans[u][u1])

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

using namespace std;

typedef long long ll;
const double eps=1e-6,pi=acos(-1);
const int N=1e5+5,M=1e9+7,SEGM=4*N,OO=0x3f3f3f3f;
int t,n,m,k;
int arr[N];

int main(){
    //freopen("myfile.txt","w",stdout);
    scanf("%d",&n);
    if(n) printf("0");
    else printf("1");
    return 0;
}


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

int main() {
  int N; cin >> N;
  using P = pair<int, int>;
  vector<int> X(N), Y(N);
  rep(i, 0, N) cin >> X[i] >> Y[i];
  map<P, int> ma;
  rep(i, 0, N) ma[P(X[i], Y[i])]++;
  int ans = N;
  rep(i, 0, N-1) rep(j, i+1, N) {
    int dx = X[i] - X[j];
    int dy = Y[i] - Y[j];
    int cnt = N;
    rep(k, 0, N) if(ma[P(X[k] + dx, Y[k] + dy)]) cnt--;
    ans = min(ans, cnt);
  }
  if(N == 1) ans = 1;
  cout << ans << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

const int mod=1000000007;
const ll oo=1e18;
int dx[8]={1,-1,0,0,1,-1,1,-1};
int dy[8]={0,0,1,-1,1,-1,-1,1};
const int N=102050;
bool srt(pair<int,int>a,pair<int,int>b){
    return a.first!=b.first?a.first>b.first:a.second<b.second;
}

int main(){
    int n;
    cin>>n;
    if(n<=999)puts("ABC");
    else puts("ABD");
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	int N, num = 0, max, temp;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		if (i == 0) {
			max = temp;
			num++;
		}
		else if (max <= temp) {
			max = temp;
			num++;
		}
		else;
	}
	cout << num << endl;
}


Measured memory_bytes: 256
package main

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

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	m := scanInt()
	x := scanInts(m)

	sort.Ints(x)

	arr := make([]int, m-1)
	for i := 0; i < m-1; i++ {
		arr[i] = x[i+1] - x[i]
	}

	sort.Ints(arr)

	ans := 0
	for i := 0; i < m-n; i++ {
		ans += arr[i]
	}

	fmt.Fprintln(wr, ans)
}


Measured memory_bytes: 2944
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <numeric>

#define INF 10000000000;
using namespace std;

int main(void){
   int N,K;
   cin>>N>>K;
   long h[N];
   for(int i=0;i<N;i++){
       cin>>h[i];
   }
   long dp[100100];
   for(int i=0;i<100100;i++){
       dp[i]=INF;
   }
   dp[0]=0;
   for(int i=0;i<N;i++){
       for(int j=1;j<=K;j++){
          dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
       }
   }
   cout<<dp[N-1]<<endl;
   return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>

int main(void){

    int n;
    int k;
    int max,min;
    int amari;
    int ans;

    scanf("%d%d",&n,&k);
    min=1;
    amari=n-k;
    max=1+amari;
    ans=max-min;
    if(k==1||k==0){
        ans=0;
    }
    printf("%d",ans);
    

    


    
    



    return 0;
}

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

  const int MOD = 1000000007;

  //long long
  using ll = long long;

  //出力系
  #define print(x) cout << x << endl
  #define yes cout << "Yes" << endl
  #define YES cout << "YES" << endl
  #define no cout << "No" << endl
  #define NO cout << "NO" << endl
  
  // begin() end()
  #define all(x) (x).begin(),(x).end()

  //for
  #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

  //最大公約数（ll）
  ll gcd(ll x, ll y) { return y ? gcd(y,x%y) : x;}

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


int main()
{
    ll N;
    cin >> N;
    if(N % 2 != 0){
        print(0);
        return 0;
    }
    ll d = 5;
    ll ans = 0;
    while(d <= N){
        ans += N / (d * 2);
        d *= 5;
    }
print(ans);
}

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



int main()
{
    int x[5] = { 99 };
    cin >> x[0] >> x[1] >> x[2] >> x[3] >> x[4];
    for (int i = 0; i < 5; i++) {
        if (x[i] == 0)
            cout << i + 1 << endl;
    }
}

Measured memory_bytes: 3188
#include <iostream>

using namespace std;

int main(){
	long long N;
	cin >> N;
	
	// h <= n <= w
	for (long long h = 1; h < 3501; h++) {
		// 4/N - 1/h - 1/n = 1/w
		// (4hn - Nn - Nh)/(Nhn) = 1/w
		// (Nhn) / (4hn - Nn - Nh) = w (int)
		for (long long n = h; n < 3501; n++) {
			long long a = N*h*n;
			long long b = 4*h*n - N*n - N*h;
			if (b <= 0) continue;
			if ( a % b != 0 ) continue;
			long long w = (N*h*n) / (4*h*n - N*n - N*h);
			
			if (w <= 0) continue;
			cout << h << " " << n << " " << w << endl;
			return 0;
		}
	}


	return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
		if((a+b)%2==0)
			printf("%d\n",(a+b)/2);
			else
				printf("%d\n",(a+b)/2+1);
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long int
#define INF INT_MAX
#define mod
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
int main()
{
	chutiyaap;
	ll n,k;cin>>n>>k;
	if(k==1)cout<<"0";
	else cout<<n-k;
}


Measured memory_bytes: 256
'use strict'
function Main(input) {
    input = input.trim().split(/\n/)
    input.shift()
    input = input.map(elem => {
      return elem.split(' ')
    })

    input = input.map((elem, index) => {
      return [
         index+1,
         elem[0], // 都市名
         parseInt(elem[1], 10) // 点数
      ]
    })
  
    input.sort((a, b) => {
      if(a[1] !== b[1]) {
        return a[1].localeCompare(b[1])
      } else{
        return b[2] - a[2]
      }
    })

    input.forEach(elem => {
        console.log(elem[0])
    })

}
Main(require("fs").readFileSync("/dev/stdin", "utf8"))

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

signed main(){
    int a,b;
    cin >>a>>b;
    int k=0,t=1,ans=0;
    while(t<=b)t*=2;
    t/=2;
   // cerr <<t;
   if(t>=2){
    if(a>=t){
        if((b-a)%2==0)ans+=t;
    }else{
        if((b-t)%2==0)ans+=t;
    }
    t/=2;
   }
   
    while(t>=2){
        k=0;
        if(b%(2*t)>=t)k+=b%(2*t)-t+1;
        if(a%(2*t)>=t)k+=2*t-(a%(2*t));
        if(k%2==1)ans+=t;
        t/=2;
    }
    if((((b+1)/2)*2-(a/2)*2)%4!=0)ans+=1;
    cout <<ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int A,B,K;
  cin >> K;
  cin >> A >> B;
  
  if(A%K==0){
   cout << "OK" << endl;

  }else if(A/K<B/K){
   cout << "OK" << endl; 
  }else
    cout << "NG"<<endl;
  
 return 0; 
}

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

#define INF (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define N 100005
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795

ll no_of_div(ll a)
{
  ll cnt=0,i;
  if (a==2)return 1;
  for(i=2;i*i<a;i++)
  {
if(a%i==0)cnt+=2;
  }
  if(i*i==a)cnt++;
  return cnt;
}

//vl a(1001);

ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }

return ans;
}





int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string a,b,c;
    cin>>a>>b>>c;

  if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0])cout<<"YES"<<"\n";
  else cout<<"NO"<<"\n";


  return 0;


}

Measured memory_bytes: 256
n,k = gets.split.map(&:to_i)
p1=[]
n.times { p1 << gets[0] }
pp = p1.group_by{|x|x}.map{|x,y|[x,y.size]}

res=0
loop do
  pp.reject!{|x,y| y==0}
  pp.sort_by!{|x,y|-y}
  break if pp.size < k
  pp[0,k] = pp[0,k].map{|x,y| [x,y-1]}
  res += 1
end
puts res


Measured memory_bytes: 3836
#include<bits/stdc++.h>
using namespace std;
int N,M;
int W[50],B[50],R[50];

int f(int x,int y,int A[50]){
  int sum=0;
  for(int i=x;i<y;i++)
    sum+=A[i];
  return sum;
}

int main(){
  cin>>N>>M;
  for(int i=0;i<N;i++){
    string s;
    cin>>s;
    for(int j=0;j<M;j++){
      if(s[j]=='W')W[i]++;
      if(s[j]=='B')B[i]++;
      if(s[j]=='R')R[i]++;
    }
  }
  int ans=0;
  for(int i=1;i<N-1;i++)
    for(int j=i+1;j<N;j++)
      ans=max(ans,f(0,i,W)+f(i,j,B)+f(j,N,R));
  cout<<N*M-ans<<endl;
  return 0;
}

Measured memory_bytes: 1204
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    s = input()
    k = s[0]
    ans = 1
    for i in range(1,n):
        if k != s[i]:
            ans += 1
            k = s[i]
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 41072
import java.util.*;

class Main{
	static long mod = 1000000007;
	static ArrayDeque<pair> st = new ArrayDeque<>();

	public static void insert(line l1) {
		if (st.isEmpty()) {
			st.add(new pair(l1, 0L));

		} else {
			while (st.size() > 0) {
				line tl = st.peekLast().l;
				long pt = st.peekLast().xo;
				long newpt = intersectionpt(tl, l1);
				if (newpt <= pt) {
					st.pollLast();
				} else {
					break;
				}
			}
			st.add(new pair(l1, intersectionpt(l1, st.peekLast().l)));
		}

	}

	public static long query(long x) {
		while(st.size() > 1) {
			pair p1=st.pollFirst();
			pair p2=st.pollFirst();
			if(p2.xo<=x){
				st.addFirst(p2);
			}else{
				st.addFirst(p2);
				st.addFirst(p1);
				break;
			}
		}
		return value(st.peekFirst().l, x);

	}

	public static long value(line l1, long x) {
		return l1.slope * x + l1.intcep;
	}

	public static class pair {
		line l;
		long xo;

		pair(line l1, long b) {
			l = l1;
			xo = b;
		}
	}

	public static class line {
		long slope;
		long intcep;

		line(long a, long b) {
			slope = a;
			intcep = b;
		}
	}

	public static long intersectionpt(line l1, line l2) {
		return (long) Math.ceil(1.0 * (l2.intcep - l1.intcep) / (l1.slope - l2.slope));
	}

	public static void main(String args[]) {
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		long c = scn.nextLong();
		long h[] = new long[n];
		for (int i = 0; i < n; i++) {
			h[i] = scn.nextLong();
		}
		long dp[]=new long[n];
		dp[0]=0L;
	     insert(new line(-2*h[0],h[0]*h[0]));
	     for(int i=1;i<n;i++){
	    	 dp[i]=h[i]*h[i]+c+query(h[i]);
	    	 insert(new line(-2*h[i],h[i]*h[i]+dp[i]));
	     }
	     System.out.println(dp[n-1]);

	}

}

Measured memory_bytes: 93932
D, N = map(int, input().split())

n = 0
count = 0
while True:
    n += 100**D
    target = n
    count_div = 0
    while True:
        if target % 100 == 0:
            count_div += 1
            target //= 100
        else:
            break
    if count_div == D:
        count += 1

    if count == N:
        print(n)
        exit()



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+5, M = 5e5+5, OO = 0x3f3f3f3f;
typedef long long ll;
#define PI 3.14159265358979323846
#define MOD 1000000007
bool prime[100005];
void seive(){
    memset(prime,1,sizeof prime);
    for (ll i=2; i*i<=100005; ++i){
        if (prime[i]){
            for (ll j=i*i; j<=100005; j+=i){
                prime[j]=0;
            }
        }
    }
}
int main()
{
    seive();
    int n; cin>>n;
    for (int i=n; i<=100005; ++i) if (prime[i]) return cout<<i,0;
   return 0;
}

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

using namespace std;
typedef long long ll;

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

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  ll N; cin >> N;
  vector<ll> x(N), y(N), h(N); rep(i, N) cin >> x[i] >> y[i] >> h[i];
  
  ll cx, cy, H;
  
  rep(i, 101) {
    rep(j, 101) {
      ll H1 = -1;
      rep(k, N) {
	if(h[k] != 0) {
	  H1 = abs(x[k] - i) + abs(y[k] - j) + h[k];
	}
      }
      //      cerr << "[" << i << "," << j << "] " << H1 << endl;
      
      rep(k, N) {
	ll lh = max(H1 - abs(x[k] - i) - abs(y[k] - j), 0LL);
	if(lh != h[k]) {
	  H1 = -1;
	  break;
	}
      }
      if(H1 > 0) {
	cx = i;
	cy = j;
	H = H1;
      }
    }
  }
  
  cout << cx << " " << cy << " " << H << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N; cin >> N;
	string S; cin >> S;
	vi WC (N);
	WC[0] = S[0] == 'W';
	FOR(i, 1, N) WC[i] = WC[i-1] + (S[i] == 'W');

	int best = WC[N-1];
	int RC = 0;
	ROF(i, 1, N) {
		RC += S[i] == 'R';
		int swap = min(WC[i-1], RC);
		best = min(best, WC[i-1] + RC - swap);
	}
	best = min(best, RC);
	print(best);
}

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

int main(){
  int n,cnt=0;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
    cnt+=a[i];
  }
  sort(a,a+n);
  if(cnt%10==0){
    bool c = 0;
  	for(int i=0;i<n;i++){
    	if(a[i]%10!=0){
      	c = 1;
      	cnt-=a[i];
      	break;
    	}
  	}
    if(!c) cout << 0 << endl;
    else cout << cnt << endl;
  }
 else cout << cnt << endl;
}


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

int main() {
    ll n,i,c=0,l,j; cin>>n; map<ll,ll>m;
    while(n%2==0) {m[2]++; n/=2;}
    for(i=3;i*i<=n;)
    {
        while(n%i==0) 
        {
            m[i]++; n/=i;
        }
        i+=2;
    }
    if (n>2) {m[n]++;}
    for(auto it=m.begin(); it!=m.end();it++)
    {
        for(i=1;i<101;i++)
        {
            if ((i*(i+1))/2>it->second) {break;}
        }
        c+=i-1;
    } cout<<c;
    return 0;
}

Measured memory_bytes: 3640
N = int(input())
S = input()
a = S.count('(')
b = S.count(')')
ans = ''

cnt = 0
for i in range(N):
    if S[i] == '(':
        cnt += 1
    else:
        cnt -= 1
    if cnt < 0:
        ans += '('
        cnt += 1

ans += S + ')' * cnt
print(ans)

Measured memory_bytes: 3064
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
ll=[[None,None] for i in range(m)]
for i in range(m):
  b,c=map(int,input().split())
  ll[i][1]=b
  ll[i][0]=c
ll.sort(reverse=True)
cnt=0
l=[]
j=0
for j in range(m):
  for i in range(min(n,ll[j][1])):
    l.append(ll[j][0])
  cnt+=min(n,ll[j][1])
  if cnt>=n:
    break
a+=l
a.sort(reverse=True)
print(sum(a[:n]))

Measured memory_bytes: 84632
#include<iostream>

using namespace std;

int main(){
	int A, B, T;
  	cin >> A >> B >> T;
  	
  	int sumA=0;
  	int num_gen=0;
  	for (int i=0; sumA <= T; i++){
      sumA += A;
      if (sumA <= T){
	     num_gen += 1;
      }
    }
  
  	int num_bis=0;
  	num_bis = num_gen * B;
  
  	cout << num_bis << endl;

	return 0;
}

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

int main(int argc, char** argv)
{
	std::string s;
	std::getline(std::cin, s);

	std::string p;
	std::getline(std::cin, p);

	for (int si = 0; si < (int)s.size(); ++si)
	{
		if (s[si] == p[0])
		{
			bool match = true;
			for (int pi = 0; pi < (int)p.size() && match; ++pi)
			{
				match = (s[(si + pi) % (int)s.size()] == p[pi]);
			}
			if (match)
			{
				std::cout << "Yes" << std::endl;
				return 0;
			}
		}
	}

	std::cout << "No" << std::endl;

	return 0;
}


Measured memory_bytes: 3212
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>

using namespace std;

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

static const double eps = 10e-9;

int main(){
	double a,b;
	double eyesight[] = {0.2,0.6,1.1};
	int lFreq[4]={0,0,0,0};
	int rFreq[4]={0,0,0,0};

	while(~scanf("%lf %lf",&a,&b)){
		int idx1 = 3;
		int idx2 = 3;
		for(int i=0;i<3;i++){
			if(a < eyesight[i]){
				idx1 = i;
				break;
			}
		}

		for(int i=0;i<3;i++){
			if(b < eyesight[i]){
				idx2 = i;
				break;
			}
		}

		lFreq[idx1]++;
		rFreq[idx2]++;
	}

	for(int i=3;i>=0;i--){
		printf("%d %d\n",lFreq[i],rFreq[i]);
	}
}

Measured memory_bytes: 3204
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1E9 + 9;
const int INF = 1 << 29;

int main() {
  string S;
  cin >> S;
  int n = S.length();
  vector<int> v(n);
  int op;
  rep(i, n) v[i] = int(S.at(i) - '0');
  for (int i = 0; i < (1 << (n - 1)); ++i) {
    int ans = v[0];
    for (int j = 0; j < (n - 1); ++j) {
      if (i & (1 << j)) {
        ans += v[j + 1];
      } else {
        ans -= v[j + 1];
      }
    }
    op = i;
    if (ans == 7) break;
  }
  cout << v[0];
  for (int i = 0; i < (n - 1); i++) {
    if (op & (1 << i)) {
      cout << '+';
    } else {
      cout << '-';
    }
    cout << v[i + 1];
  }
  cout << "=7" << endl;
  return 0;
}

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

int N, X, Y;
int ans[2010];

int main () {
	cin >> N >> X >> Y;
	for(int i=1; i<=N; i++) {
		for(int j=i+1; j<=N; j++) {
			int temp = min(j-i, abs(X-i)+abs(Y-j)+1);
			ans[temp]++;
		}
	}
	for(int i=1; i<N; i++) {
		cout << ans[i] << endl;
	}
}


Measured memory_bytes: 256