akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
#define MAX 100000
typedef long long llong;

int n, k;
llong T[MAX];

int check(llong P) {
  int i = 0;
  for (int j = 0; j < k; j++) {
    llong s = 0;
    while (s + T[i] <= P) {
      s += T[i];
      i++;
      if (i == n) {
        return n;
      }
    }
  }
  return i;
}

int solve() {
  llong left = 0;
  llong right = 10000000000;
  llong mid;
  while (right - left > 1) {
    mid = (left + right) / 2;
    int v = check(mid);
    if (v >= n) {
      right = mid;
    } else {
      left = mid;
    }
  }

  return right;
}

int main() {
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> T[i];
  }

  llong ans = solve();
  cout << ans << endl;
}



Measured memory_bytes: 3876
#include<bits/stdc++.h>
#define int   long long int  
#define pb push_back
#define BOOST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debugL(i)  cout<<"line no-> "<<i<<" working"<<endl
#define debugVL(i,l)  cout<<"val at line no."<<i<< " ->"<<l<<endl
const int M=1e9 + 7;
using namespace std;
int N=100000+1;
int32_t main() {
    //int q;cin>>q;
    int n;cin>>n;
    //long double x,y;cin>>x>>y;
    long double ans=0;
    long double* a=new long double[n];
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    ans=(a[0]+a[1])/2;
    //debugVL(18,ans);
    for(int i=2;i<n;i++)
    {
    	
    	ans=(ans+a[i])/2;
	}
	cout<<std::setprecision(9)<<ans<<endl;
    return 0;
}













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

typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;
typedef vector< vector< vector<ll> > > vvvint;
typedef vector<string> vstring;
typedef vector< vector<string> > vvstring;
typedef vector<char> vchar;
typedef vector< vector<char> > vvchar;
typedef vector<long double> vdouble;
typedef vector< vector<long double> > vvdouble;
typedef vector< vector< vector<long double> > > vvvdouble;
typedef pair<ll,ll> pint;
typedef vector<pint> vpint;
typedef vector<bool> vbool;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define ALL(obj) (obj).begin(), (obj).end()
// #define LLONG_MAX 9223372036854775806
#define MOD 1000000007
const double PI=3.14159265358979323846;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> T Ceil(T a, T b){return (a+b-1)/b;}

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

void printv(vint &v){
    for(auto e:v) cout<<e<<" ";
        cout<<endl;
    }
ll const Cons = 30000;
vint ans;
void solve(ll N){

    ll c1,c2;
    c1 = -1; c2 = -1;

    for(ll m1=1; 2*(3*m1-1)<=Cons; m1++){
        c1 = 3*m1 -1;
        c2 = N - c1;
        if(c2%2==0 && (c1*c2 != 0) && (3*(2*c2-1)) <= Cons){break;}
        else c2 = -1;
    }

    if(c2 == -1){
        for(ll m1=1; 2*3*m1<=Cons; m1++){
            c1 = 3*m1;
            c2 = N - c1;
            if(c2%2==0 && (c1*c2 != 0) && (3*(2*c2-1)) <= Cons){break;}
            else c2 = -1;
        }
    }

    // cout<<c1<<" "<<c2<<endl;
    // if(c1*c2 < 0) cout<<N<<endl;
    // assert(c1*c2 != 0);
    // assert(c2 > 0);
    rep(i,c1) cout<<2*(i+1)<<" ";
    rep(i,c2) cout<<3*(2*i+1)<<" ";
    puts("");
}

int main() {
    cout<<fixed<<setprecision(10);

    ll N; cin>>N;

    if(N==3){
        cout<<"2 5 63"<<endl;
    }else if(N==5){
        cout<<"2 3 4 5 16"<<endl;
    }else{
        solve(N);
    }

    // repf(i,3,N) solve(i);

    // puts("");
    // ll tot = 0;
    // for(auto e:ans)tot+=e;
    // for(auto e:ans){
    //     if(gcd(e, tot-e) == 1){
    //         puts("hage");
    //     }
    // }




    return 0;

}

Measured memory_bytes: 384
#include<stdio.h>
#include<iostream>
using namespace std;

int N;
int main (){
    cin >> N ;
    int ans = 0;
    for(int i=0; i<N; i++){
        int l,r;
        cin >> l >> r;
        ans += r - l + 1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from math import gcd
ans = 0
k = int(input())
D = [0]*201
for a in range(1, k+1):
    for b in range(1, k+1):
        D[gcd(a, b)] += 1
for c in range(1, k+1):
    for g in range(201):
        ans += D[g] * gcd(c, g)
print(ans)

Measured memory_bytes: 9188
#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
	ll n, z=0, ma=0, i;
	
	cin>>n;
	
	vector <ll> a(n+1);
	
	for(i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==1) z++;
			else ma=max(ma,z), z=0;
	}
	
	ma=max(ma,z);
	
	cout<<ma+1<<"\n";
	
}


Measured memory_bytes: 3084
using System;

public class Hello{
    public static void Main(){
        var n=int.Parse(Console.ReadLine());
        var c=new int[10,10];
        var ans=0;
        for(var i=0;i<10;i++){
            for(var j=0;j<10;j++){
                c[i,j]=0;
            }
        }
        for(var i=1;i<=n;i++){
            var lead=int.Parse(i.ToString().Substring(0,1));
            var end=i%10;
            c[lead,end]++;
        }
        for(var i=0;i<10;i++){
            for(var j=0;j<10;j++){
                ans+=c[i,j]*c[j,i];
            }
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 15308
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = b - 1; i >= a; i--)
#define int ll
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

signed main() {
    int n, k;
    cin >> n >> k;
    int a[n];
    rep(i, 0, n) cin >> a[i];
    rep(i, k, n) {
        if (a[i] > a[i - k]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

Measured memory_bytes: 5144
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
using itn = int;
using namespace std;
static const long double GRATIO=(long double)(1+sqrt(5))/2;
ll GCD(ll a, ll b){
    return b ? GCD(b, a%b) : a;
}
ll LCM(ll a, ll b){
    return a/GCD(a,b)*b;
}
int main(){
    int N;
    cin>>N;
    vector<int> h(N);
    rep(i,N) cin>>h[i];
    int cnt=0;
    rep(i,N){
        if(i==0){ cnt+=h[i]; continue; }
        if(h[i]>h[i-1]){
            cnt+=h[i]-h[i-1];
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int n; cin>>n;
	int a[n]; rep(i,n) cin>>a[i];
	multiset<int> ss;
	int ans=1; ss.insert(a[0]);
	ss.insert(-INF);
	ss.insert(-INF);
	for(int i=1;i<n;i++){
		auto itr=ss.lower_bound(a[i]);
		itr--;
		// cout<<tmp<<endl;
		if(*itr!=-INF){
			ss.erase(itr);
		}else{
			ans++;
		}
		ss.insert(a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct edge{
    int to;
    string lab;
};
 
struct state{
    int node,len;
    string spell;
    bool operator<(const state& r)const{
        return spell>r.spell;
    }
};
 
int main(){
    int N,A,S,G;
    while(cin >> N >> A >> S >> G && N){
        vector<vector<edge>> v(N);
        int x,y;
        string s;
        for(int i=0;i<A;i++){
            cin >> x >> y >> s;
            v[x].push_back({y,s});
        }
        vector<vector<string>> dp(N,vector<string>(510,"{"));
        dp[S][0] = "";
        priority_queue<state> Q;
        Q.push({S,0,""});
        while(!Q.empty()){
            state now = Q.top(); Q.pop();
            if(dp[now.node][now.len]<now.spell) continue;
            if(500<=now.spell.size()) continue;
            for(auto x:v[now.node]){
                state ne = now;
                ne.node = x.to;
                ne.len += x.lab.size();
                ne.spell += x.lab;
                if(dp[ne.node][ne.len]>ne.spell){
                    dp[ne.node][ne.len] = ne.spell;
                    Q.push(ne);
                }
            }
        }
        bool ok = true;
        string ans = "{";
        for(int i=0;i<510;i++){
            if(ans>dp[G][i]){
                ans = dp[G][i];
                if(i>300) ok = false;
            }
        }
        if(ans=="{") ok = false;
        cout << (ok? ans:"NO") << endl;
    }
}


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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int h, w, n;
    cin >> h >> w >> n;
    map<pii, int> mp;
    while(n--) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        for(int i = 0; i < 9; ++i) {
            int nx = b + dx[i];
            int ny = a + dy[i];
            if(1 <= ny && ny <= h-2 && 1 <= nx && nx <= w-2) ++mp[{nx, ny}];
        }
    }
    array<int, 10> cnt = {0};
    ll cnt0 = ll(w - 2) * (h - 2);
    for(auto && p : mp){
        ++cnt[p.second];
        --cnt0;
    }
    cout << cnt0 << "\n";
    for(int i = 1; i <= 9; ++i){
        cout << cnt[i] << "\n";
    }
    return 0;
}

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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    copy_n(istream_iterator<int>(cin), n, A.begin());

    int ans = 0;
    for (int i = 0; i < n; i++){
        if (i % 2 == 0 and A[i] & 1)
            ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3624
//2020-05-02 22:59:23
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int SIZE = 200000;
vector<vector<int>> A;
void make_A(int depth, vector<int> &v, const int MAX, const int MAX_D){
    if (depth == MAX_D) {
        A.push_back(v);
        return;
    }
    for (int i = (*(v.end()-1)); i <= MAX; i++)
    {
        vector<int> vi = v;
        vi.push_back(i);
        make_A(depth+1, vi, MAX, MAX_D);
    }
    
}
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int N, M, Q; cin >> N >> M >> Q;
    struct query
    {
        int a, b, c, d;
        query(int a, int b, int c, int d) : a(a),b(b),c(c),d(d){}
    };
    vector<query> querys;
    for (int i = 0; i < Q; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        querys.push_back(query(a, b, c, d));
    }
    vector<int> v_s;v_s.push_back(1);
    make_A(1, v_s, M, N);
    int ans = 0;
    for (int i = 0; i < A.size(); i++)
    {
        int score = 0;
        for (int j = 0; j < Q; j++)
        {
            if ((A[i][querys[j].b-1] - A[i][querys[j].a-1]) == querys[j].c)
                score += querys[j].d;
        }
        ans = max(ans, score);
    }
    cout << ans << endl;
}

Measured memory_bytes: 6696
from sys import stdin, stdout
from collections import defaultdict

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()

def main():
	n, m, q = (int(x) for x in rll())
	pts = defaultdict(lambda: 0)
	for _ in range(q):
		a, b, c, d = (int(x) for x in rll())
		pts[(a, b, c)] = d

	seq = []
	ans = float('-inf')

	def calcval(s):
		score = 0
		curr = defaultdict(lambda: 0)
		for (a, b, c), d in pts.items():
			if s[b-1] - s[a-1] == c and d > curr[(a, b)]:
				score -= curr[(a,b)]
				curr[(a,b)] = d
				score += d
		return score

	def dfs(i, maxlen, maxdig, prev = None):
		nonlocal ans
		if i == maxlen:
			score = calcval(seq)
			ans = max(ans, score)
			return
		start = 1 if prev is None else prev
		for num in range(start, maxdig + 1):
			seq.append(num)
			dfs(i+1, maxlen, maxdig, num)
			seq.pop()

	dfs(0, n, m)
	stdout.write(str(ans));stdout.write("\n")
	stdout.close()

if __name__ == "__main__":
	main()

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef priority_queue<int> pqb;
typedef priority_queue<int, vi, greater<int> > pqs;

#define iamtheflash         ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod                 1000000007
#define debug1(x)           cout<<"#x: "<<x<<"\n"
#define debug2(x,y)         cout<<"#x: "<<x<<" #y: "<<y<<"\n"
#define debug3(x,y,z)       cout<<"#x: "<<x<<" #y: "<<y<<" #z: "<<z<<"\n"
#define debug4(x,y,z,w)     cout<<"#x: "<<x<<" #y: "<<y<<" #z: "<<z<<" #w: "<<w<<"\n"
#define rep(i,n)            for(int i=0;i<(n);i++)
#define repl(i,n)           for(ll i=0;i<(n);i++)
#define fori(i,a,b)         for(int i=(a);i<=(b);i++)
#define forl(i,a,b)         for(ll i=(a);i<=(b);i++)
#define ford(i,a,b)         for(int i=(a);i>=(b);i--)
#define fordl(i,a,b)        for(ll i=(a);i>=(b);i--)
#define pb                  push_back
#define mp                  make_pair
#define ff                  first
#define ss                  second
#define mid(s,e)            (s+(e-s)/2)
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define ps(x,y)             fixed<<setprecision(y)<<x
#define w(x)                int x; cin>>x; while(x--)
#define in(x)               int x; cin>>x;
#define ins(x)              string x; cin>>x;
#define endl                '\n'
#define infi                INT_MAX
#define infll               LLONG_MAX
#define infim               INT_MIN
#define infllm              LLONG_MIN
#define mk(arr,n,type)      type *arr = new type[n];
#define umap(x,type1,type2) unordered_map<type1, type2 > x;

int solve(int *a, int n) {
	int dp[n + 1];
	dp[1] = 0;
	fori(i, 2, n) {
		int option1 = abs(a[i] - a[i - 1]) + dp[i - 1];
		int option2 = (i == 2) ? infi : abs(a[i] - a[i - 2]) + dp[i - 2];
		dp[i] = min(option1, option2);
	}
	return dp[n];
}

int32_t main() {
	iamtheflash

	in(n);
	mk(a, n + 1, int);

	fori(i, 1, n) cin >> a[i];

	cout << solve(a, n);

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> X(N);
	vector<int> Y(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i];
	}
	int z = abs(X[0] + Y[0]) % 2;
	for (int i = 0; i < N; i++) {
		if (abs(X[i] + Y[i]) % 2 != z) {
			cout << -1 << endl;
			return 0;
		}
	}
	int M;
	if (z == 1) {
		M = 39;
	}
	else {
		M = 40;
	}
	vector<int> D(M);
	int k = (int)1 << 32;
	for (int i = 0; i < M; i++) {
		D[i] = k;
		k = k >> 1;
		if (k == 0)k = 1;
	}
	cout << M << endl;
	for (int i = 0; i < M; i++) {
		if (i > 0)cout << " ";
		cout << D[i];
	}
	cout << endl;
	int dx[4] = { -1,1,0,0 };
	int dy[4] = { 0,0,-1,1 };
	char dir[4] = { 'L','R','D','U' };
	for (int i = 0; i < N; i++) {
		int curX = 0;
		int curY = 0;
		int m = M;
		string res;
		int mn = 0;
		int dd;
		for (int j = 0; j < M; j++) {
			mn = (int)1 << 60;
			for (int k = 0; k < 4; k++) {
				int nx = curX + dx[k] * D[j];
				int ny = curY + dy[k] * D[j];
				if (mn > abs(nx - X[i]) + abs(ny - Y[i])) {
					mn = abs(nx - X[i]) + abs(ny - Y[i]);
					dd = k;
				}
			}
			res.push_back(dir[dd]);
			curX += dx[dd] * D[j];
			curY += dy[dd] * D[j];
		}
		cerr << X[i] - curX << " " << Y[i] - curY << endl;
		cout << res << endl;
	}
}

Measured memory_bytes: 384
import 'dart:io';

extension OnesPlace on int {
  int get onesPlace => this % 10;
}

void main(List<String> arguments) {
  final n = int.parse(stdin.readLineSync());
  print(getCounterBy(n));
}

String getCounterBy(int rawInput) {
  switch (rawInput.onesPlace) {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      return 'hon';
    case 0:
    case 1:
    case 6:
    case 8:
      return 'pon';
    default:
      return 'bon';
  }
}


Measured memory_bytes: 13124
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
using namespace std; //std::の省略のため
using ll = long long;

int main()
{
  int a, b, h;
  cin >> a >> b >> h;

  int ans = (a + b) * h / 2;

  cout << ans << endl;
}


Measured memory_bytes: 3572
s = input()
a = 0
t = ("")

while a < len(s):
    if s[a+0:a+5] == ("dream") and s[a+5+0:a+5+2] != ("er"):
        a += 5

    elif s[a+0:a+5] == ("dream") and s[a+5+0:a+5+2] == ("er"):
        if s[a+7+0:a+7+3] != ("ase"):
            a += 7

        elif s[a+7+0:a+7+3] == ("ase") and s[a+10+0:a+10+1] != ("r"):
            a += 10

        elif s[a+7+0:a+7+3] == ("ase") and s[a+10+0:a+10+1] == ("r"):
            a += 11

    elif s[a+0:a+5] == ("erase") and s[a+5+0:a+5+1] != ("r"):
        a += 5

    elif s[a+0:a+5] == ("erase") and s[a+5+0:a+5+1] == ("r"):
        a += 6

    else:
        break

if a == len(s):
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3316
#include<bits/stdc++.h>
 
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;
 
#define pb push_back
#define popb pop_back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair 
#define mt make_tuple
#define fi
#define se second
 
#define forz(i,n) for(long long int i=0;i<n;i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0) 
 
using namespace std;

int main()
{
	lli n;
	
	cin >> n;
	lli a[n+1]= {0}, b[n+1] ={0}, s = 0, c[n+1] = {0};
	forz(i , n)
	{
		cin >> a[i];
		b[a[i]]++;
	}
	forz(i, n+1)
	{
		s = s + (b[i]*(b[i]-1))/2; 
	}
	forz(i, n)
	{
		c[i] = s - ((b[a[i]]*(b[a[i]]-1))/2) + ((b[a[i]]-1)*(b[a[i]]-2))/2;
		cout << c[i] << endl;
	}
	return 0;
}


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

const int N = 1005;
long long int n, t, a;
long long int ans = 0;
long long int tWahl, aWahl;

int main() {
	ios_base::sync_with_stdio(false);

	cin >> n;

	tWahl = aWahl = 0;

	for(int i = 0; i < n; i++) {
		cin >> t >> a;
		if(aWahl == 0 || aWahl % a != 0) {
			aWahl += a;
			aWahl -= (aWahl % a);
		}
		if(tWahl == 0 || tWahl % t != 0) {
			tWahl += t;
			tWahl -= (tWahl % t);
		}
		if(tWahl/t > aWahl/a) {
			aWahl = (tWahl/t)*a;
		} else if(tWahl/t < aWahl/a) {
			tWahl = (aWahl/a)*t;
		}
	}

	cout << aWahl + tWahl << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rlcfpoj(x) scanf("%I64d",&x)
#define pi(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define plcfpoj(x) printf("%I64d",x)
#define lfd() printf("\n")
#define sp() printf(" ")
#define inrep(x) int x;scanf("%d",&x);while(x--)
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
int n,u,v;
vector<int> ga[100100];
int cnt[100100];
int pr[100100];
void dfs(int u,int p){
	cnt[u]=1;
	for(int i=0;i<ga[u].size();i++){
		int v=ga[u][i];
		if(v==p)
			continue;
		pr[v]=u;
		dfs(v,u);
		cnt[u]+=cnt[v];
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		ga[u].push_back(v);
		ga[v].push_back(u);
	}
	dfs(1,0);
	int cur=n;
	int sz=0;
	vector<int> path;
	while(cur!=0){
		path.push_back(cnt[cur]-sz);
		sz=cnt[cur];
		cur=pr[cur]; 
	}
	reverse(path.begin(),path.end());
	int f=0,s=path.size()-1;
	int ff=0,ss=0;
	while(f<s){
		ff+=path[f];
		ss+=path[s];
		f++;
		s--;
		if(f==s){
			ff+=path[f];
			break;
		} 
	}
	if(ff>ss)
		cout<<"Fennec"<<endl;
	else
		cout<<"Snuke"<<endl;
	return 0;
}


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

int main() {
  string x;
  cin >> x;

  if (x =="A"|| x=="B"||x=="C"||x=="D"||x=="E"||x=="F"||x=="G"||x=="H"||x=="I"||x=="J"||x=="K"||x=="L"||x=="N"||x=="M"||x=="O"||x=="P"||x=="Q"||x=="R"||x=="S"||x=="T"||x=="U"||x=="V"||x=="W"||x=="X"||x=="Y"||x=="Z") {
    cout << "A" << endl;
  }
  else {
    cout << "a"<< endl;
  }
}



Measured memory_bytes: 3596
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define int long long int
int i,j;
 main()
{
  int n,m;
  cin>>n>>m;
  int a[m]; int s=0;
  for(i=0;i<m;i++) {cin>>a[i];s=s+a[i];}
  if(s<=n) cout<<n-s<<endl;
  else cout<<-1<<endl;
  }



Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (T &x : vec)
        is >> x;
    return is;
}

ll gcd(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    while (m != n)
    {
        if (m > n)
            m = m - n;
        else
            n = n - m;
    }
    return m;
}

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

int ctoi(const char c)
{
    if ('0' <= c && c <= '9')
        return (c - '0');
    return -1;
}

int main(){
    string s;
    cin >> s;

    int cnt=0;

    REP(i,s.size()){
        if(s[i]=='2'){
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

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

typedef long long ll;
typedef vector<ll> v1;
typedef vector<vector<ll>> graph;

const ll INF = 1ll << 50;

ll n;
string s;
ll a[30001];

ll dp1[10];
ll dp2[10][10];
ll dp3[10][10][10];
ll ans = 0;

int main(){
    cin >> n;
    cin >> s;
    for(ll i = 0;i < n;i++) a[i] = s[i]-'0';
    for(ll i = 0;i < n;i++){
        for(ll d1 = 0;d1 < 10;d1++){
            for(ll d2 = 0;d2 < 10;d2++){
                dp3[d1][d2][a[i]] |= dp2[d1][d2];
            }
        }
        for(ll d1 = 0;d1 < 10;d1++){
            dp2[d1][a[i]] |= dp1[d1];
        }
        dp1[a[i]] |= 1;
    }
    for(ll i = 0;i < 10;i++){
        for(ll j = 0;j < 10;j++){
            for(ll k = 0;k < 10;k++){
                ans += dp3[i][j][k];
            }
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int main() {
	long long int n, t;
	cin >> n >> t;
	vector<long long int>s;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		s.push_back(a);
	}
	long long int ans = 0;
	for (int i = 0; i < n; i++) {
		if (i == n - 1) {
			ans = ans + t;
		}
		else {
			if (s[i + 1] - s[i] >= t) {
				ans = ans + t;
			}
			else {
				ans = ans + s[i + 1] - s[i];
			}
		}
	}
	cout << ans;
}


Measured memory_bytes: 2420
import java.util.Scanner;

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

        String line = scan.nextLine();
        String answer="";
        int length=line.length();
        char ch;

        for(int i=0;i<length;i++){
            ch=line.charAt(i);
            if(Character.isLowerCase(ch)){
                ch=Character.toUpperCase(ch);
            }else{
                ch=Character.toLowerCase(ch);
            }
            answer+=ch;
        }

        System.out.println(answer);
    }
}


Measured memory_bytes: 31108
# 初期入力
NN,K = (int(x) for x in input().split())

#K個の和、初項と修項
p =10**9 + 7
seq =[i for i in range(NN+1)] #0-Nまでの数列
ans =[0] *(NN+1)
st =[0]*(NN+1)
fi =[0]*(NN+1)
st[0] =sum(seq[  :K])
fi[0] =sum(seq[-K: ])
ans[0] =fi[0] -st[0] +1
if NN==1 and K==1:
    print(3)
else:
    for i in range(NN -K+1):
        st[i+1] =st[i] +seq[K+i]
        fi[i+1] =fi[i] +seq[-K-i-1]
        ans[i+1] =(fi[i+1] -st[i+1] +1)
    print(sum(ans) %p)

Measured memory_bytes: 48796
#!/usr/bin/env python3
from collections import Counter

prime_factor = []
N = int(input())
for i in range(2,int(N**0.5)+1):
    while N % i == 0:
        prime_factor.append(i)
        N /= i
if N > 1:
    prime_factor.append(N)

c = Counter(prime_factor)

cnt = 0
for k, v in c.items():
    diff = 1
    while v > 0:
        v -= diff
        if v >= 0:
            cnt += 1
        diff += 1

print(cnt)

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


struct treasure{
  int v;
  int w;
};

void thief(int W, int N, vector<treasure>* v, int* retV, int* retW);

int main(void){
  int c=1;
  int W;
  int N;
  while(true){
    cin>>W;
    if(W==0)break;
    cin>>N;
    vector<treasure> v;
    for(int i=0;i<N;i++){
      int _v,w;
      scanf("%d,%d",&_v,&w);
      treasure tmp;
      tmp.v=_v;
      tmp.w=w;
      v.push_back(tmp);
    }

    int retV;
    int retW;
    thief(W,N,&v,&retV,&retW);
    cout<<"Case "<<c<<":"<<endl;
    cout<<retV<<endl;
    cout<<retW<<endl;
    c++;
  }
  return 0;
}



void thief(int W, int N, vector<treasure>* _v, int* retV, int* retW){
  auto v=*_v;
  int table[N][W+1];
  for(int i=0;i<N;i++){
    for(int j=0;j<=W;j++){
      table[i][j]=0;
    }
  }
  for(int j=0;j<=W;j++){
    if(v[0].w>j)continue;
    else{
      table[0][j]=v[0].v;
    }
  }

  for(int i=1;i<N;i++){
    for(int j=0;j<=W;j++){
      if(v[i].w>j){
        table[i][j]=table[i-1][j];
      }
      else{
        table[i][j]=max(table[i-1][j],table[i-1][j-v[i].w]+v[i].v);
      }
    }
  }

  *retV=table[N-1][W];
  for(int j=W;j>=0;j--){
    if(table[N-1][j]==*retV){
      *retW=j;
    }
  }
}



Measured memory_bytes: 7108
N,X = map(int,input().split())
L = list(map(int,input().split()))

curCoord = 0
n = 1

while (curCoord<=X):
    n = n+1
    
    if (n>N+1):
        break
    else:
        curCoord = curCoord+L[n-2]

print(n-1)

Measured memory_bytes: 9140
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
ll N;
  cin>>N;
  vector<pair<ll,ll>> vec(N);
  for(ll i=0;i<N;i++) {
ll x,y;
    cin>>x>>y;
    vec[i]=make_pair(x,y);
  }
  
  vector<ll> s(N);
  for(ll i=0;i<N;i++) {
s[i]=vec[i].first+vec[i].second;
  }
  
  sort(all(s));
  
  vector<ll> w(N);
  for(ll i=0;i<N;i++) {
w[i]=vec[i].first-vec[i].second;
  }
  sort(all(w));
  
  cout<<max(s.back()-s[0],w.back()-w[0])<<endl;
}
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

Measured memory_bytes: 9592
import java.util.*;
import java.io.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		HashMap hs = new HashMap();
		PrintWriter ou = new PrintWriter(System.out);
		long n = Long.parseLong(sc.next());
		if(n == 0) ou.print(0);
		sc.close();
		long che = 1;
		int cou = 0;
		boolean[] ebishu = new boolean[100000];
		while(n != 0){
			che *= -2;
			if(n % Math.abs(che) != 0){
				ebishu[cou] = true;
				n += che / 2;
			}
			cou++;
		}
		for(int i = cou - 1 ; i >= 0 ; i--){
			if(ebishu[i]) ou.print(1);
			else ou.print(0);
		}
		ou.print("\n");
		ou.flush();
	}
}

Measured memory_bytes: 35776
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <iomanip>

using namespace std;

int main(void){
	int n, k;
	cin >> n >> k;
	if(n%k==0){
		cout << "0" << endl;
	}else{
		cout << "1" << endl;
	}
	return 0;
}

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

int getNumber(string& s, int* i) {
    int n = 0;
    while(s[(*i)] != ']') {
        n *= 10;
        n += s[*i]-'0';
        (*i)++;
    }
    return n;
}

int analyze(string& s, int* i) {
    if(s[(*i)] != '[') {
        cerr << "error!" << endl;
        return -1;
    }
    if(s[++(*i)] != '[') {
        return getNumber(s, i)/2 + 1;
    }
    vector<int> a;
    while(s[(*i)] == '[') {
        a.push_back(analyze(s, i));
        (*i)++;
    }
    sort(a.begin(), a.end());
    int ans = 0;
    rep(k, a.size()/2+1) ans += a[k];
    return ans;
}

int main(void){
    int n;
    string s;
    getline(cin, s);
    sscanf(s.c_str(), "%d", &n);
    rep(data, n) {
        getline(cin, s);
        int i = 0;
        cout << analyze(s, &i) << endl;
    }
}

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

using namespace std;

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

int main(){
	int N;
	cin>>N;
	REP(i,N){
		string s1,s2;
		string comp;
		cin>>s1>>s2;
		reverse(s1.begin(),s1.end());
		reverse(s2.begin(),s2.end());
		int n1=s1.size();
		int n2=s2.size();
		int ma=max(n1,n2);
		FOR(j,n1,ma){
			s1+='0';
		}
		FOR(j,n2,ma){
			s2+='0';
		}
		int c=0;
		REP(j,ma){
			int k=c+s1[j]+s2[j]-'0';
			if (k<='9'){
				comp+=k;
				c=0;
			}
			else{
				comp+=k-10;
				c=1;
			}
		}
		if (c==1) comp+='1';
		reverse(comp.begin(),comp.end());
		if (comp.size()>80) cout<<"overflow"<<endl;
		else cout<<comp<<endl;
	}
	return 0;
}

Measured memory_bytes: 1208
//verma_ankit484

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
const int mod = (int) 1e9+7;

using namespace std;
//using namespace __gnu_pbds;

//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


int32_t main() {
  IOS
  #ifdef AV
  freopen("input.txt", "r", stdin);
  #endif
  int n, k;
  cin >> n >> k;
  vector<int> vc(n);
  for (auto &i: vc) {
    cin >> i;
    i--;
  }
  set<int> st;
  int idx = 0;
  int val;
  while (1) {
    if (st.find(idx) != st.end()) {
      val = idx;
      break;
    }
    st.insert(idx);
    idx = vc[idx];
  }
  vector<int> pp;
  idx = vc[0];
  while (idx != val) {
    pp.pb(idx);
    idx = vc[idx];
  }
  if (k <= (int)pp.size()) {
    cout << pp[k - 1] + 1 << endl;
    return 0;
  }
  k -= pp.size();
  pp.clear();
  idx = val;
  while (1) {
    pp.pb(idx);
    idx = vc[idx];
    if (idx == val) break;
  }
  k--;
  k = k % ((int)pp.size());
  cout << pp[k] + 1 << endl;
  return 0;
}


Measured memory_bytes: 16028
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;

int main(){
    int n;
    vector<char> alp;
    rep(i,0,26)alp.pb('a'+i);
    rep(i,0,26)alp.pb('A'+i);
    //alp={'a','b'.......'Y','Z'}
    while(cin>>n){
        if(n==0)break;
        vector<int> v(n);
        rep(i,0,n)cin>>v[i];
        string s;
        cin>>s;
        
        int v_count=0; 
        //v_countはずらす回数を表す数字の配列の添字
        //下に出てくるposは'a'-'Z'までを格納した配列alpの添字
        
        rep(i,0,s.size()){
            if('a'<=s[i]&&s[i]<='z'){
                int pos=s[i]-'a';  //小文字の時、'a'との差がalpの添字
                rep(j,0,v[v_count]){
                    pos--;
                    if(pos==-1)pos=51;
                }
                cout<<alp[pos];
            }else {
                int pos=s[i]-'A'+26; //大文字の時、'A'との差に26を足さないとalpの添字にならない
                rep(j,0,v[v_count]){ 
                    pos--;
                    if(pos==-1)pos=51;
                }
                cout<<alp[pos];
            }
            v_count++;
            if(v_count==n)v_count=0;
        }
        cout<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 3148
#include<iostream>
#include<bits/stdc++.h>
#define LL long long int
using namespace std;
int main()
{
		LL n;
		cin>>n;
		LL a[n];
		map<LL,LL>m;
		LL sum=0;
		for(LL i=0; i<n; i++)
		{
			cin>>a[i];
			sum+=a[i];
			m[a[i]]++;
		}
		LL q;
		cin>>q;
		while(q--)
		{
			LL b,c;
			cin>>b>>c;
			{
				sum-=m[b]*b;
				sum+=m[b]*c;
				m[c]+=m[b];
				m[b]=0;
			}
			cout<<sum<<"\n";
		}
		cout<<'\n';
		
}


Measured memory_bytes: 10188
#include <stdio.h>
#include <stdlib.h>
int main(){
  int i,j,k;
  int l;
  int f=0;
  int n[1000];
  int key;

  //データ長さ入力
  while(1){
    //printf("prease data length\n");
    scanf("%d",&l);
    if((0<l)&&(l<101)){
      break;
    }
    //printf("prease 0<length<101\n");
  }

  //printf("prease inport number\n");
  for(i=0; i<l; i++){
    scanf("%d",&n[i]);
    if((1000<=n[i])||n[i]<=0){
      //printf("prease more low number\n");
      continue;
    }
  }

  for(i=0; i<l; i++){
    printf("%d",n[i]);
    if(i!=l-1)printf(" ");
  }
  printf("\n");

  for(i=1; i<l; i++){
    key = n[i];
    for(j=i-1; j>=0&&n[j]>key; j--){
      n[j+1]=n[j];

    }
    n[j+1]=key;


    for(k=0; k<l; k++){
      printf("%d",n[k]);
      if(k!=l-1)printf(" ");
    }
    printf("\n");
  }
  return 0;
}




Measured memory_bytes: 2084
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a,b,p[10],cnt,ok,ans,dp[10],L;
int main(void){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>a;
        L=0;
        for(int j=0;j<a;j++){
            cin>>b;
            b--;
            L+=(1LL<<b);
        }
        dp[i]=L;
    }
    for(int i=0;i<m;i++){
        cin>>p[i];
    }
    for(int i=0;i<m;i++){
        //cout<<dp[i]<<endl;
    }
    for(ll i=0;i<(1LL<<n);i++){
        ok=1;
        for(int j=0;j<m;j++){
            L=dp[j]&i;
            cnt=0;
            //cout<<"L"<<L<<endl;
            for(ll k=0;k<10;k++){
                cnt+=(L>>k);
            }
            //cout<<cnt<<"cnt"<<endl;
            if(cnt%2!=p[j]){
                ok=0;
                break;
            }
        }
        if(ok){
            ans++;
            //cout<<i<<"i"<<endl;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.math.BigDecimal;
import java.math.RoundingMode;

public class Main {
	public static void main(String[] args) {
		try (java.util.Scanner sc = new java.util.Scanner(System.in)) {
			double r = sc.nextDouble();
			int scale = 6;

			BigDecimal area = new BigDecimal(r * r * Math.PI).setScale(scale, RoundingMode.HALF_EVEN);
			BigDecimal Circumference = new BigDecimal(2 * r * Math.PI).setScale(scale, RoundingMode.HALF_EVEN);

			System.out.println(area + " " + Circumference);
		}
	}
}


Measured memory_bytes: 28444
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define SZ size()
#define FOR(i, a, b) for(int (i) = (a); (i) < (b); (i)++)
#define REP(i, n) FOR((i), 0, (n))
#define GET(a) cin >> (a)
#define GET2(a, b) cin >> (a) >> (b)
#define GET3(a, b, c) cin >> (a) >> (b) >> (c)
#define SHOW(v) cout << (v) << endl
#define SHOW2(a, b) cout << (a) << " " << (b) << endl
#define SHOW3(a, b, c) cout << (a) << " " << (b) << " " << (c) << endl
#define MOD 1000000007
template<class T> void GETV(T &v) { REP(i, v.size()) { GET(v[i]); } }
template<class T> void SHOWV(T &v) { REP(i, v.size()) { SHOW(v[i]); } }

typedef long long ll;

struct xyz {
	double n;
	string s;
};

int main() {
	int n;
	cin >> n;
	
	vector<xyz> v(n);
	for(int i = 0; i < n; i++) {
		cin >> v[i].n >> v[i].s;
	}
	
	int yen = 0;
	double bitCoin = 0;
	for(int i = 0; i < n; i++) {
		if(v[i].s == "JPY") {
			yen += v[i].n;
		}
		else {
			bitCoin += v[i].n;
		}
	}
	
	cout << yen + bitCoin * 380000.0 << endl;
	
    return 0;
}

Measured memory_bytes: 256
n = int(input())
d1 = 9 - 1 + 1
d3 = 999 - 100 + 1
d5 = 99999 - 10000 + 1

n_len = 1
n_copy = n
while n_copy >= 10:
    n_copy = n_copy // 10
    n_len += 1

if n_len == 6:
    print(d1 + d3 + d5)
elif n_len == 5:
    print(d1 + d3 + (n-10000+1))
elif n_len == 4:
    print(d1 + d3)
elif n_len == 3:
    print(d1 + (n-100+1))
elif n_len == 2:
    print(d1)
elif n_len ==1:
    print(n)

Measured memory_bytes: 38384
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A[] = new int[N];
    for(int i=0;i<N;i++){
      A[i]=sc.nextInt();
    }
    Arrays.sort(A);
    for(int i=0;i<N-1;i++){
      if(A[i]==A[i+1]){
        System.out.println("NO");
        return;
      }
    }
    System.out.println("YES");
  }

  
  

  
}

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

int wmax, n;
vector<int> v(1000), w(1000);

int main() {
  int cnt = 0;
  while (cin >> wmax >> n) {
    for (int i = 0; i < n; ++i) {
      string tmp;
      getline(cin, tmp, ',');
      v[i] = atoi(tmp.c_str());
      getline(cin, tmp);
      w[i] = atoi(tmp.c_str());
    }

    vector<vector<int>> res(wmax+1, vector<int>(n));

    for (int c=0; c<n; ++c) {
      for (int r=0; r<wmax+1; ++r) {
        if (c==0) {
          res[r][c] = (r < w[0]) ? 0 : v[0];
        }
        else {
          if (r < w[c]) {
            res[r][c] = res[r][c-1];
          }
          else {
            int v1 = res[r][c-1];
            int v2 = res[r-w[c]][c-1] + v[c];
            res[r][c] = (v1 < v2)? v2 : v1;
          }
        }
      }
    }

    int res_v = 0;
    int res_w = wmax;
    for (int r=0; r<wmax+1; ++r) {
      for (int c=0; c<n; ++c) {
        if (res_v < res[r][c]) {
          res_v = res[r][c];
          res_w = r;
        }
      }
    }

    cout << "Case " << ++cnt << ":" << endl;
    cout << res_v << endl;
    cout << res_w << endl;
  }
  return EXIT_SUCCESS;
}



Measured memory_bytes: 6836
#include <bits/stdc++.h>
//#pragma GCC diagnostic error "-Wconversion"
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
ll digits(ll x){
  ll length = 0;
  while (x > 0){
    x /= 10;
    length++;
  }
  return length;
  if (x == 0) return 0;
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
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;
}

int main(){
  cout << fixed << setprecision(15);

  int n, m; cin >> n >> m;
  vector<int> dices(n);
  rep(i, n) cin >> dices[i];

  double ans = 0;
  //string ans = "";
  
  vector<int> sums(n + 1);
  sums[0] = 0;
  rep(i, n) sums[i + 1] = sums[i] + dices[i];
  rep(i, n - m + 1){
    double temp = sums[i + m] - sums[i];
    ans = max(ans, temp);
  }
  ans = (ans + m) / 2.0;
  
  cout << ans << endl;
  

  return 0;
}

Measured memory_bytes: 1792
# 一日かかった．特に後段の’#’一つのみの特殊ケース？になかなか気づけなかった．

h,w = map(int, input().split())
l = [list(list(input())) for i in range(h)]
W = []
for j in range(w):
    for k in range(h-1):
        if l[k][j] == l[k+1][j] == '.':
            continue
        else:
            break
    else:
        W.append(j)
W = sorted(W, reverse=True) #後で消す列のリスト、降順

H = []
for m in range(h):
    if set(l[m]) == {'.'}:
        H.append(m)
H = sorted(H, reverse=True) #後で消す行のリスト、降順

if l == [['#']]: # なぜか'#'１つのみの場合のみ特殊ケース
    print('#')
else:
    for p in range(len(W)):
        for q in range(h):
            del l[q][W[p]]
    
    for r in H:
        del l[r]
    
    for s in l:
        print(''.join(s))


Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define rrep(i,n) for(int i=(int)n-1;i>=0;--i)
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T& a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

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

    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;

    for (ll i = 0; i < n; ++i) {
        int j = n-1-i;
        ll l = a - j*d + i*c;
        ll r = a - j*c + i*d;
        if (l <= b && b <= r) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}


Measured memory_bytes: 3636
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,k=MI()


	if k%2:
		a=n//k
		b=0
	else:
		a=n//k
		b=n//(k//2)-a

	print(a**3+b**3)








if __name__ == "__main__":
	main()


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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll solve(int N, const vector<ll>& xs)
{
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);

    ll N, A, B;
    cin >> N >> A >> B;

    if (A == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    auto k = N / (A + B);
    auto r = N - k*(A + B);

    auto ans = A*k + min(r, A);

    cout << ans << '\n';

    return 0;
}


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

int main(){
int N,M;
  cin>>N>>M;
  char A[N][N], B[M][M];
  for(int i=0; i<N; i++){
   for(int j=0; j<N; j++){
   cin>>A[i][j];}}
  for(int i=0; i<M; i++){
   for(int j=0; j<M; j++){ 
   cin>>B[i][j];}}
  
  for(int i=0; i+M<=N; i++){
   for(int j=0; j+M<=N; j++){
      bool ans=true;
       for(int x=0; x<M; x++){
        for(int y=0; y<M; y++){
         if(A[i+x][j+y]!=B[x][y]){ans=false;}
        }
       }
      if(ans){cout<<"Yes"; return 0;} 
   }
  }
  
  cout<<"No";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1000000007;
const int INF=1001001001;

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int N;
  cin>>N;
  vector<int64_t>A(N);
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  int64_t ans=0;
  for(int s=0;s<60;s++){
    int64_t ONE=0,ZERO=0;
    for(int i=0;i<N;i++){
      if((A[i]>>s)&1){ONE++;}
    }
    ZERO=N-ONE;
    int64_t t=ONE*ZERO;
    t%=mod;
    for(int i=0;i<s;i++){
      t*=2;
      t%=mod;
    }
    ans+=t;
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 5644
import sys 
try:
	sys.stdin = open('input.txt', 'r') 
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
for tt in range(1):
	n,k = map(int,input().split())
	l = list(map(int,input().split()))
	cycle = []
	s = set()
	pos = 0
	while True:
		pos = l[pos]-1
		if pos in s:
			start = cycle.index(pos+1)
			break
		cycle.append(pos+1)
		s.add(pos)
	new = cycle[start:]
	size = len(cycle) - len(new)

	if k<=size:
		print(cycle[k-1])
	else:
		k-=size
		print(new[(k-1)%len(new)])

Measured memory_bytes: 124692
#include <bits/stdc++.h>
using namespace std;
int x,y;
long long a,b,c,d;
long long maxn = -1100000000000000000;
int main()
{
	cin >> a >> b >> c >> d;
	if(a * c > maxn)
		maxn = a * c;
	if(a * d > maxn)
		maxn = a * d;
	if(b * c > maxn)
		maxn = b * c;
	if(b * d > maxn)
		maxn = b * d;
	cout << maxn << endl;
}

Measured memory_bytes: 3612