akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	map<int, int> cards;
	int c;
	for (int i = 0; i < n; ++i) {
		cin >> c;
		++cards[c];
	}

	auto it = cards.begin();
	auto itr = cards.rbegin();
	int in_hand = n;
	while (it->first != itr->first) {
		if (it->second == 1) {
			++it;
		}
		else if (itr->second == 1) {
			++itr;
		} else {
			--(it->second);
			--(itr->second);
			in_hand -= 2;
		}
	}

	while (it->second > 2) {
		in_hand -= 2;
		it->second -= 2;
	}

	if (it->second > 1) {
		in_hand -= 2;
	}

	cout << in_hand << "\n";

	return 0;

}

Measured memory_bytes: 8188
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

int main() {
    string s; cin >> s;
    if (s == "Sunny") cout << "Cloudy" << endl;
    if (s == "Cloudy") cout << "Rainy" << endl;
    if (s == "Rainy") cout << "Sunny" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    int t,a;
    cin >> t >> a;
    int h[n];
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    int dis;
    int minN = 0;
    int min = a*1000 - (t*1000 - h[0]*6);
    if(min < 0){
        min = -min;
    }

    for(int i=0; i<n; i++){
        dis =(t*1000 - h[i]*6) - a*1000;

        if(dis < 0){
            dis = -dis;
        }

        if(min > dis){
            min = dis;
            minN = i;
        }

    }

    
    cout << minN+1 << endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll X,A;
    cin >> X >> A;
    if(X < A){
        print(0);
    }else{
        print(10);
    }
}

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

int a[100];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", a + i);

    int ans = 0;
    for (int i = 0; i < n;) {
        int j = i + 1;
        while (j < n && a[i] == a[j])
            j++;
        ans += (j - i) / 2;
        i = j;
    }
    
    printf("%d\n", ans);
}


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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long a[] = new long[N];
        long b[] = new long[N];
        long c[] = new long[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            b[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            c[i] = sc.nextInt();
        }

        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        long l = 0;
        long smallA[] = new long[N];
        for (int i = 0; i < N; i++) {
            while (l < N) {
                if (b[i] > a[(int) l]) {
                    l++;
                } else {
                    break;
                }
            }
            smallA[i] = l;
        }
        long r = 0;
        long largeC[] = new long[N];
        for (int i = 0; i < N; i++) {
            while (r < N) {
                if (b[i] >= c[(int) r]) {
                    r++;
                } else {
                    break;
                }
            }
            largeC[i] = N - r;
        }
        long count = 0;
        for (int i = 0; i < N; i++) {
            count += smallA[i] * largeC[i];
        }
        System.out.println(count);

    }

}

Measured memory_bytes: 97996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const int INF=1<<30,MOD=1000000007;
const ll LINF=1ll<<60;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _overload3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPARR(i,v) for(int i=0;i<v.size();++i)
#define all(v) (v).begin(),(v).end()
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define bit(n) (1ll<<(n))
template<class T>bool chmax(T&a,const T&b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T&a,const T&b){if(a>b){a=b;return true;}return false;}
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"":"im")<<"possible"<<endl
#define Poss(n) cout<<((n)?"P":"Imp")<<"ossible"<<endl
template<typename T>ostream&operator<<(ostream&o,const vector<T>&v){for(T i:v)o<<i<<' ';return o;}
template<typename T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<typename T>ostream&operator<<(ostream&o,const set<T>&v){for(T i:v)o<<i<<' ';return o;}
template<typename T,typename U>ostream&operator<<(ostream&o,const pair<T,U>&v){o<<v.first<<' '<<v.second;return o;}

int main(){
    int n;
    cin>>n;
    vl a(n),b(n);
    vl overs;
    ll lesses=0;
    cin>>a>>b;
    ll ans=0;
    REP(i,n){
        if(a[i]>b[i]){
            overs.push_back(a[i]-b[i]);
        }else if(a[i]<b[i]){
            ans++;
            lesses+=b[i]-a[i];
        }
    }
    cerr<<ans<<endl;
    sort(all(overs),greater<ll>());
    
    for(ll ov:overs){
        if(lesses<=0)break;
        lesses-=ov;
        ans++;
    }
    if(lesses>0)ans=-1;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2428
a = int(input())
b = int(input())
c = int(input())
x = int(input())

ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i*500+j*100+k*50==x:
                ans+=1

print(ans)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if (H == 0 && W == 0) {
				break;
			} else {
				for (int i = 0; i < H - 2; i++) {
					if (i == 0) {
						for (int j = 0; j < W; j++) {
							System.out.print("#");
						}
						System.out.println("");
					}
					for (int j = 0; j < W; j++) {
						if (j == 0) {
							System.out.print("#");
						}
						if (j < W - 2) {
							System.out.print(".");
						}
						if (j == W - 2)
							System.out.print("#");
					}
					System.out.println("");
					if (i == H-3)
						for (int j = 0; j < W; j++) {
							System.out.print("#");
						}
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}


Measured memory_bytes: 33564
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[25],b[25],c[25],s=0,i;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
     for(i=0;i<n;i++)
    {
        cin>>b[i];
        s=s+b[i];
    }
     for(i=1;i<n;i++)
    {
        cin>>c[i];
    }
    for(i=0;i<n-1;i++)
    {
        if(a[i]+1==a[i+1])
            s+=c[a[i]];
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here

        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();

        if(n % 10 == 7 || (n / 10) % 10 == 7  || (n / 100) == 7)
            out.println("Yes");
        else out.println("No");
        out.close();
    }
}


Measured memory_bytes: 35900
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)(b); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    int a[n];
    rep(i, 0, n) cin >> a[i];
    ll ans = 0;
    rep(i, 1, n) {
        int d = a[i - 1] - a[i];
        if (d > 0) {
            ans += d;
            a[i] += d;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4320
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.1415;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

//////////////////////////////////

vector<vector<int>> bingo(3, vector<int>(3));
vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;

	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

ll getGcd(ll a, ll b) {
	if (a < b) {
		ll temp = b;
		b = a;
		a = temp;
	}

	ll r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}

int main() {
	int N, M; cin >> N >> M;
	map<int, ll>height;
	for (int i = 0; i < N;++i) {
		int h; cin >> h;
		height[i] = h;
	}
	vector<int>heightest(N, 0);
	for (int i = 0; i < M;++i) {
		int a, b; cin >> a >> b; --a; --b;
		//a
		int currentAHeightest = heightest[a];
		if (currentAHeightest < height[b])heightest[a] = height[b];
		//b
		if (heightest[b] < height[a])heightest[b] = height[a];
	}
	int ans = 0;
	for (int i = 0; i < N;++i) {
		if (heightest[i] < height[i])ans++;
	}
	cout << ans << endl;
}



Measured memory_bytes: 12240
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	int a[200001];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == cnt + 1)
		{
			cnt++;
		}
	}
	if (cnt == 0)
		cout << -1 << endl;
	else
		cout << n - cnt << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
    int n; cin >> n;
    vector<int> l(n);
    REP(i, n) cin >> l[i];

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

    ll ans = 0;
    REP(i, n)FOR(j, i + 1, n) {
        int s = l[i] + l[j];
        int k = lower_bound(l.begin(), l.end(), s) - l.begin();
    
        ans += (k - 1) - j;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dfs(ll n){
	if(n==1)return 1;
	return (1+2*dfs(n/2));
}
int main()
{
	ll n;
	scanf("%lld",&n);
	printf("%lld\n",dfs(n));
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
#define int long long

template <typename T>
struct Edge { int src, dst; T cost;
    Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { }
    Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { }
};
template <typename T> using Edges = vector<Edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
template <typename T> using Matrix = vector<vector<T>>;

int P;
template <typename T>
pair<vector<T>, vector<int>> bellman_ford(Edges<T> &edges, int V, int s, int MA) {
    const T INF = numeric_limits<T>::max();
    vector<T> dist(V, INF); dist[s] = 0;
    vector<int> cnt(V, 0); cnt[s] = 0;
    vector<T> memo(MA);
    vector<int> memo_c(MA);
    vector<int> prev(V, -1);
    for (int i = 0; i < MA; i++) {
        for (auto &e: edges) if (dist[e.src] != INF) {
            if (dist[e.dst] > dist[e.src] + e.cost) {
                dist[e.dst] = dist[e.src] + e.cost;
                cnt[e.dst] = cnt[e.src] + 1;
                prev[e.dst] = e.src;
            }
        }
        memo[i] = dist[V - 1];
        memo_c[i] = cnt[V - 1];
    }
    return {memo, prev};
}

signed main() {
    int N, M; cin >> N >> M >> P;
    Edges<long long> es;
    while (M--) {
        int s, t, d; cin >> s >> t >> d; s--, t--;
        es.emplace_back(s, t, -d + P);
    }
    auto res1 = bellman_ford(es, N, 0, 2 * N);
    long long ans1 = -res1.first[N - 2];
    long long ans2 = -res1.first[2 * N - 1];
    if (ans1 < ans2) {
        cout << -1 << endl;
    } else {
        cout << max(0LL, ans1) << endl;
    }
    return 0;
}

Measured memory_bytes: 576
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <complex>
#include <functional>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define dump(n) cout<<"# "<<#n<<"="<<(n)<<endl
#define debug(n) cout<<__FILE__<<","<<__LINE__<<": #"<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define tr(c,i) for(iter(c) i=(c).begin();i!=(c).end();i++)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int search(int i,int j,vector<string>& field)
{
    int r=field.size(),c=field[0].size();
    if(i<0 || r<=i || j<0 || c<=j)
        return 0;
    if(field[i][j]=='#')
        return 0;
    field[i][j]='#';
    int di[]={-1,1,0,0};
    int dj[]={0,0,-1,1};
    int sum=1;
    rep(k,4)
        sum+=search(i+di[k],j+dj[k],field);
    return sum;
}

int main()
{
	for(int c,r;cin>>c>>r,c|r;){
        vector<string> field(r);
        rep(i,r)
            cin>>field[i];
        rep(i,r)
            rep(j,c)
                if(field[i][j]=='@')
                    cout<<search(i,j,field)<<endl;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>

using namespace std;

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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long mod = 1000000007;

    vector<long long> b(a);
    for (int i = 0; i < n - 1; i++) {
        b[i + 1] += b[i];
        b[i + 1] %= mod;
    }

    long long res = 0;
    for (int i = 0; i < n - 1; i++) {
        res += a[i] * (b[n - 1] - b[i] + mod);
        res %= mod;
    }

    cout << res << endl;
}


Measured memory_bytes: 6364
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>


#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int64_t a, b, c; cin >> a >> b >> c;
	if (c <= (a + b)) {
		cout << "No" << endl;
		return 0;
	}

	if (4 * a * b < (c - (a + b)) * (c - (a + b))) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 256
use std::io;
use std::vec::Vec;
use std::str::FromStr;
use std::collections::HashSet;
fn main() {
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
    line.pop();
    let numbers: Vec<i32> = line.split(' ').map(|s| {
        i32::from_str(&s).unwrap()
    }).collect();
    let mut hash = HashSet::new();
    hash.insert(numbers[0]);
    hash.insert(numbers[1]);
    hash.insert(numbers[2]);
    if hash.len() == 2 {
        println!("Yes");
    } else {
        println!("No");
    }
}

Measured memory_bytes: 4352
#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N,K = map(int,input().split())
p = list(map(int,input().split()))

p.sort()

print(sum(p[0:K]))



Measured memory_bytes: 27140
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[][] A = new int[2][N];

        for(int i = 0; i < 2; i++){
            for(int j = 0; j < N; j++){
                A[i][j] = in.nextInt();
            }
        }
        int max = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j <= i; j++){
                int sum = 0;    
                for(int k = 0;k < N; k++){
                    if (k <= j){
                        sum += A[0][k];
                        if(k == j){
                            sum += A[1][k];
                        }
                    } else{
                        sum += A[1][k];
                    }
                }
                if (sum > max){

                    max = sum;
                }
            }
        }
        System.out.println(max);
        
        in.close();
    }
}


Measured memory_bytes: 25684
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define initdp(a, b)  for (int i = 0; i <= a; i++)   for (int j = 0; j <= b; j++) dp[i][j] = -1;
#define pb push_back
#define mpr make_pair
#define pii pair<int, int>
#define ll long long
#define pll pair<ll, ll>
#define all(arr) arr.begin(), arr.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repd(i, n) for (int i = n - 1; i >= 0; i--)
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define INF 1000000001
#define inf1 1000000000000000001
#define mod 1000000007
#define pie 3.14159265358979323846264338327950L
#define N 1000005
#define mid(l, r) l + (r - l) / 2
#define vec vector<int>
#define vecl vector<ll>
#define umap unordered_map<ll,ll>
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define endl "\n"
using namespace std;


 
 
 
 
 
void solve(){
 
   ll X;
    cin >> X;
 
    ll money=100;
    int year=0;
    while(true){
        if(money >= X) break;
        money+=money/100;
        year++;
    }
 
    cout << year << endl;
    
 
 
}
 
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(20);
    int t = 1;
   //  cin >> t;
    while (t--)
    {
        solve();
    }
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    string s;
    cin >> s;
    ll n = s.size();
    ll up = 0;
    ll down = 0;
    ll ans = 0;
    vector<ll> numberup(n+1);
    vector<ll> numberdown(n+1);
    for (ll i = 0; i < n; i++) {
        if (s.at(i) == '<') {
            up++;
            numberup.at(i+1) = up;
        } else {
            up = 0;
            numberup.at(i+1) = up;
        }
    }

    for (ll i = n - 1; i >= 0; i--) {
        if (s.at(i) == '>') {
            down++;
            numberdown.at(i) = down;
        } else {
            down = 0;
            numberdown.at(i) = down;
        }
    }

    for (ll i = 0; i <= n; i++) {
        if (numberup.at(i) < numberdown.at(i)) {
            numberup.at(i) = numberdown.at(i);
        }
        ans += numberup.at(i);
    }
    cout << ans << endl;
    return 0;
}

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

int main(void){
    int n;
    cin >> n;
    
    vector<int> a(n);
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        a[i] = x;
    }
    
    vector<double> ainv(n);
    for(int i=0; i<n; i++){
        ainv[i] = 1.0/a[i];
    }
    
    double ans = 1/(accumulate(ainv.begin(), ainv.end(), 0.0));

    cout << setprecision(15) << ans << endl;

    return 0;
}


Measured memory_bytes: 256
### constant

INF = 1 << 30

DXYS = [[1, 0], [0, 1], [-1, 0], [0, -1]]

C_STRAIGHT = 0
C_RIGHT = 1
C_BACK = 2
C_LEFT = 3
C_HALT = 4

### main

loop do
  w, h = gets.split.map(&:to_i)
  break if (w | h) == 0

  brds = h.times.map{gets.split.map(&:to_i)}
  costs = gets.split.map(&:to_i)
  #p brds
  #p costs

  dists = h.times.map{w.times.map{4.times.map{INF}}}
  dists[0][0][0] = 0
  q = [[0, 0, 0]]

  min_cost = INF
  gx = w - 1
  gy = h - 1

  while ! q.empty?
    u = q.min{|a, b| dists[a[1]][a[0]][a[2]] <=> dists[b[1]][b[0]][b[2]]}
    q.delete(u)

    ux, uy, ud = u
    distu = dists[uy][ux][ud]
    brdu = brds[uy][ux]

    if ux == gx && uy == gy
      min_cost = distu if min_cost > distu
      next
    end

    for cmd in (0..3)
      vd = (ud + cmd) & 3
      dx, dy = DXYS[vd]
      vx = ux + dx
      vy = uy + dy

      if vx >= 0 && vx < w && vy >= 0 && vy < h
        cost = (brdu == cmd) ? 0 : costs[cmd]
        distv = dists[vy][vx][vd]
        ndistv = distu + cost

        if distv > ndistv
          q << [vx, vy, vd] if distv >= INF
          dists[vy][vx][vd] = ndistv
        end
      end
    end
  end

  puts min_cost
end

Measured memory_bytes: 6240
#include <bits/stdc++.h>
using namespace std;
int main()
{
    string S;
    cin >> S;
    int mm = (S[5] - '0') * 10 + (S[6] - '0');
    int dd = (S[8] - '0') * 10 + (S[9] - '0');
    if (mm < 4)
    {
        cout << "Heisei" << endl;
    }
    else if (mm == 4 && dd <= 30)
    {
        cout << "Heisei" << endl;
    }
    else
    {
        cout << "TBD" << endl;
    }
}

Measured memory_bytes: 256
n,k,l=map(int,input().split())

#Union-Find
par=[-1 for i in range(n+1)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])
def f(a):
    if road[a]<0:
        return a
    else:
        return f(road[a])
def f2(a):
    if rail[a]<0:
        return a
    else:
        return f2(rail[a])
def size(a):
    return -par[root(a)]
def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(k):
    a=[int(j) for j in input().split()]
    if root(a[0])!=root(a[1]):
        connect(a[0],a[1])
import copy
road=copy.deepcopy(par)

par=[-1 for i in range(n+1)]

for i in range(l):
    r,s=[int(j) for j in input().split()]
    if root(r)!=root(s):
        connect(r,s)
import copy
rail=copy.deepcopy(par)
l=[(f(i),f2(i)) for i in range(1,1+n)]
from collections import Counter
c=Counter(l)
print(*(c[i] for i in l))







Measured memory_bytes: 139988
#include<bits/stdc++.h>
#define two(a) (1<<(a))
#define LINF (1ll<<61)
#define EPS (1e-14)
#define Lshift(a,b) ((a)<<(b))
#define Rshift(a,b) ((a)>>(b))
#define rep(a,b) for(a=0 ; a<b ; a++)
#define xrep(a,b,c) for(a=b ; a<c ; a++)
#define INF (1<<29)
#define sz(a) int(a.size())
#define swap(a,b) ( (a^=b) , (b^=a) , (a^=b) )
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5]|=1<<(x&31))
#define maxL (10000000>>5)+1
#define mod 1000000007
#define vi vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define si set<int>
#define pb push_back
typedef long long ll;
using namespace std;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll a, b, n;
    cin >> a >> b >> n;
    ll f;
    if (n <= b) { f = min(b-1, n); }
    else {
        ll w = (n+1) / b;
        w = w * b - 1;
        f = w;
    }
    cout << a * f / b - a * (f / b) << endl;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;

int main(){
  int n, m; cin >> n >> m;
  map<int, int> mp[n+1];
  int p[m+1], y[m+1];

  REP(i, m){
    cin >> p[i] >> y[i];
    mp[p[i]][y[i]]++;
  }

  FOR(i, 1, n+1){
    int cnt = 1;
    for(auto& x: mp[i]){
      x.second = cnt++;
    }
  }

  REP(i, m){
    printf("%06d%06d\n", p[i], mp[p[i]][y[i]]);
  }

  return 0;
}


Measured memory_bytes: 11648
#include <bits/extc++.h>

int main() {
  using namespace std;
  cin.tie(nullptr)->sync_with_stdio(false);
  int64_t a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << max({a * c, a * d, b * c, b * d}) << '\n';
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[200005];
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    ll sub = 0;
    ll ans = 1e16;
    for (int i = 0; i < n - 1; i++) {
        sub += a[i];
        ll temp = sum - sub * 2;
        if (temp < 0) {
            temp *= -1;
        }
        ans = min(ans, temp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
n,W=map(int,input().split())
w=[0]*n
v=[0]*n
for i in range(n):
    w[i],v[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(1,W+1):
        if j<w[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
print(dp[-1][-1])

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

long long MOD=998244353;

int main(){
    long long N,S;
    cin >> N >> S;
    long long aa;
    vector<long long> A;
    long long i,j;
    for(i=0; i<N; i++){
        cin >> aa;
        A.push_back(aa);
    }
    long long dp[N+1][S+1];
    for(j=0; j<=S; j++){
        dp[0][j]=0;
    }
    dp[0][0]=1;
    for(i=1; i<=N; i++){
        dp[i][0]=(2*dp[i-1][0])%MOD;
    }
    for(i=1; i<=N; i++){
        for(j=1; j<=S; j++){
            if(j<A[i-1]){
                dp[i][j]=(2*dp[i-1][j])%MOD;
            }else{
                dp[i][j]=(2*dp[i-1][j]+dp[i-1][j-A[i-1]])%MOD;
            }
        }
    }
    cout << dp[N][S] << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 73984
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define vi vector<ll>
#define vb vector<bool>
#define pii pair<ll,ll>
#define mod 1000000007
#define pll pair<ll,ll>
#define rep(i,n) for(ll i=0;i<n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define per1(i,n) for(ll i=n;i>0;i--)
#define prll(a,n) for(ll i=0;i<n;i++){ cout<<a[i]<<" "; }
#define ain(a) for(auto &i:a) cin>>i
#define mms(a) memset(a,0,sizeof(a))
// cout << fixed << setprecision(0) << pi <<" "<<npi<<endl; 


ll max_ll(ll a,ll b,ll c){
	return max(a,max(b,c));
}

ll min_ll(ll a,ll b,ll c){
	return min(a,min(b,c));
}


bool sortBySec(pair<ll,ll> a,pair<ll,ll> b){
    if(a.second==b.second)
		return a.first<b.first;
    return (a.second < b.second); 
}

long long binexpmod(long long a, long long b){
    long long res =1;
    while(b>0){
        if(b&1){
            res = res * a % mod;
        }
        a = a * a % mod;
        b>>=1;
    }
    return(res);
}


ll lcm(ll a,ll b){
	ll x=__gcd(a,b);
	a/=x;
	b/=x;
	ll sum=a*b*x;
	return sum;
}
void solve(){
    ll n,res=0;
	cin>>n;
    ll w;
    cin>>w;
    vi a(n),b(n);
    rep(i,n){
        cin>>a[i]>>b[i];
    }
    ll dp[n+1][w+1];
    memset(dp,0,sizeof(dp));
    rep1(i,n){
        rep1(j,w){
            if(a[i-1]<=j){
                dp[i][j] = max(dp[i-1][j-a[i-1]]+b[i-1], dp[i-1][j]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

	cout<<dp[n][w]<<endl;
	return;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 79232
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int main(void){
  double x[4],y[4];
  int i;
  int flag;

  while(scanf("%lf %lf ",&x[0],&y[0])!=EOF){
    for(i=1;i<4;i++)scanf("%lf %lf ",&x[i],&y[i]);

    flag = 1;
    if(x[3] < x[0] || x[1] < x[2])flag = 0;
    if(y[3] < y[0] || y[1] < y[2])flag = 0;

    if(flag)printf("YES\n");
    else printf("NO\n");
  }    
  return 0;
}

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

signed main(){
    int n;
    cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    vector<int> a = p;
    sort(a.begin(), a.end());
    if(a == p){
        cout << "YES" << endl;
        return 0;
    }
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            swap(p[i], p[j]);
            if(a == p){
                cout << "YES" << endl;
                return 0;
            }
            swap(p[i], p[j]);
        }
    }
    cout << "NO" << endl;
}

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

#define loop(n, i) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define HERE cout << "HERE: " << __LINE__ << endl;
#define INSP(v) cout << v << " at " << __LINE__ << endl;

using namespace std;
typedef long long ll;


int main()
{
    int n;
    while (cin >> n, n) {
        vector<pair<string, double>> crops;
        loop (n, i) {
            string name;
            int p, a, b, c, d, e, f, s, m;
            cin >> name >> p >> a >> b >> c >> d >> e >> f >> s >> m;
            int time = 0, gain = -p;
            time = a + b + c;
            loop(m, j) {
                time += d + e;
                gain += f * s;
            }
            crops.push_back(make_pair(name, (double)gain/time));
        }

        sort(all(crops),
                [](pair<string, double> p1, pair<string, double> p2) -> int {
                    if (islessgreater(p1.second, p2.second)) {
                        return isgreater(p1.second, p2.second);
                    } else {
                        return p1.first < p2.first;
                    }
                });
        for (auto m : crops) {
            cout << m.first << endl;
        }

        cout << '#' << endl;
    }
}

Measured memory_bytes: 3208
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 HW = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var H = HW[0];
            var W = HW[1];
            var counts = new int[H][];
            var grid = new string[H];
            for (var i = 0; i < H; i++)
            {
                counts[i] = new int[W];
                grid[i] = Console.ReadLine();
            }
            for (var i = 0; i < H; i++)
            {
                for (var j = 0; j < W; j++)
                {
                    if (grid[i][j] == '#')
                    {
                        counts[i][j] = -1;
                        continue;
                    }
                    if (i - 1 >= 0)
                    {
                        if (j - 1 >= 0 && grid[i - 1][j - 1] == '#') counts[i][j]++;
                        if (grid[i - 1][j] == '#') counts[i][j]++;
                        if (j + 1 < W && grid[i - 1][j + 1] == '#') counts[i][j]++;
                    }
                    if (i + 1 < H)
                    {
                        if (j - 1 >= 0 && grid[i + 1][j - 1] == '#') counts[i][j]++;
                        if (grid[i + 1][j] == '#') counts[i][j]++;
                        if (j + 1 < W && grid[i + 1][j + 1] == '#') counts[i][j]++;
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == '#') counts[i][j]++;
                    if (j + 1 < W && grid[i][j + 1] == '#') counts[i][j]++;
                }
            }
            Console.WriteLine(string.Join("\n", counts.Select(x => string.Join("", x).Replace("-1", "#"))));
        }
    }
}


Measured memory_bytes: 28412
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    result = 0
    for i in range(N):
        result += 1 / A[i]

    if N == 1:
        print(A[0])
    else:
        print(float(1 / result))

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int main() {
  string S;
  while (cin >> S) {
    int a = (S[0] - '0') * 10 + (S[1] - '0');
    int b = (S[2] - '0') * 10 + (S[3] - '0');
    bool aa = 0 < a && a <= 12;
    bool bb = 0 < b && b <= 12;
    if (aa) {
      if (bb) {
	cout << "AMBIGUOUS" << endl;
      } else {
	cout << "MMYY" << endl;
      }
    } else {
      if (bb) {
	cout << "YYMM" << endl;
      } else {
	cout << "NA" << endl;
      }
    }
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
using namespace std;


int main()
{
	string str;
	cin>>str;
	for(int i = 0;i < str.length(); i++){
		if(str[i] == '1'){
			str[i] = '9';
		}else if(str[i] == '9'){
			str[i] = '1';
		}
	}
	cout<<str<<endl;
	return 0;
}




Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long gcd(long long a, long long b) {
	if (b == 0) return a;
	else return gcd(b, a%b);
}

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

	long long g;
	cin >> g;
	long long ans = g;
	for (int i = 1; i < N;i++) {
		long long tmp;
		cin >> tmp;
		g = gcd(ans,tmp);
		ans *= tmp / g;
	}


	cout << ans << 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++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define mrep(i,from,n) for(int i = from; i < n; i++)
#define mreps(i,from,n) for(int i = from; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
typedef long long ll;
typedef pair<ll, ll> P;
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; }
ll MOD = 1000000007;

void solve()
{	
	int n; cin >> n;
	vector<int> x(n);
	rep(i, n) cin >> x[i];
	int ans=1001001000;
	reps(i,100)
	{
		int tmp=0;
		rep(j,n)
		{
			tmp+=(i-x[j])*(i-x[j]);
		}
		chmin(ans,tmp);
	}
	cout << ans << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll  long long
#define mod 1000000007
#define ve vector
#define pi pair<int,int>
#define pb push_back
#define F first
#define S second
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define all(v) v.begin(),v.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int inf=1e9+5;
vector<ll>A,B;


ll power(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b/=2;
	}
	return res;
}

void path(ll a,int state)
{
 for(ll i=2;i*i<=a;i++)
 {
  if(a%i==0)
  {
    if(state==0)A.push_back(a/i);
     else B.push_back(a/i);
      path(a/i,state);
      return ;
  }
 }
}

void solve()
{ 
 ll n,k,i;
    cin>>n>>k;
    vector<ll>a(n),p(n);
    for(ll &x:a)cin>>x;
    for(ll &x:p)cin>>x;
    ll res=-1e18;
    for(i=0;i<n;i++)
    {
     unordered_map<int,int>mp;
        vector<ll>temp;
        ll start=i;
        ll ans=0;
        while(!mp[start])
        {
            mp[start]++;
         start=a[start]-1;
           ans+=p[start]; 
            temp.push_back(ans);
        }
       // cout<<temp.size()<<" ";
        ll div=k/(int)temp.size();
        ll rem=k%(int)temp.size();
        if(div){
            for(ll x:temp)res=max({res,x,ans*(div-1)+x});
        }
            for(ll j=0;j<rem;j++)
            res=max(res,ans*div+temp[j]);
        
    }
    cout<<res<<endl;
    
}

signed main()
{
//#ifndef ONLINE_JUDGE
    //  freopen("input.txt","r",stdin);
    //  freopen("output.txt","w",stdout);
//#endif
    FAST;
   
    
     int t=1;
    //cin>>t;
     while(t--)
    	solve();
    return 0;
}



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

int arr[200005], n, k, m, x, l, r;

bool cek(int x){
	int ret=0;
	for(int i=1; i<=n; i++){
		if(arr[i]>x){
			ret+=(arr[i]+x-1)/x-1;
		}
	}
	return ret<=k;
}

int main () {
	cin>>n>>k;
	
	for(int i=1; i<=n; i++) cin>>arr[i];
	
	l=0;
	r=1e9+5;
	
	while(l+1<r){
		m=(l+r)/2;
		
		if(cek(m)){
			r=m;
		}
		else{
			l=m;
		}
	}
	cout<<r<<endl;
}


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

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e5 + 10;

ll qmi(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}


ll n, k;
ll cnt[N]; 

int main()
{
	scanf("%lld%lld", &n, &k);
	ll ans = 0;
//	ll cnt = 1;
	for (ll i = k; i >= 1; i --)
	{
		ll tmp = k / i;
		cnt[i] = qmi(tmp, n);
		for (ll j = i + i; j <= k; j += i)
		{
			cnt[i] = (cnt[i] - cnt[j] + mod) % mod;
		}
		ans = (ans + cnt[i] * i % mod) % mod;
	}	
	cout << ans << endl;
}

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

map<ll,ll> dp[4001];
map<ll,P> p[4001];

int main() {
  int n;
  cin >> n;
  ll a[n];
  for(int i=0; i<n; i++) cin >> a[i];
  dp[0][-(1LL<<50)]=0;
  p[0][-(1LL<<50)]=P(-1,-1);
  ll d=0;
  for(int i=0; i<n; i++) {
    d+=a[i];
    vector<P> v;
    ll c=0;
    for(int j=i; j>=0; j--) {
      c+=a[j];
      v.push_back(P(c,j));
    }
    sort(v.begin(),v.end());
    ll z=-(1LL<<60);
    for(int j=0; j<v.size(); j++) {
      ll M=-1,x;
      for(map<ll,ll>::iterator it=dp[v[j].second].begin(); it!=dp[v[j].second].end(); it++) {
        if(it->first>=v[j].first) break;
        if(z<it->second) {
          if(M<it->second) {
            M=it->second;
            x=it->first;
          }
        }
      }
      if(M==-1) continue;
      if(!dp[i+1].count(v[j].first)||dp[i+1][v[j].first]<M+1) {
        dp[i+1][v[j].first]=M+1;
        p[i+1][v[j].first]=P(v[j].second,x);
      }
      z=M;
    }
  }
  ll ans=-1;
  P q;
  for(map<ll,ll>::iterator it=dp[n].begin(); it!=dp[n].end(); it++) {
    if(ans<it->second) {
      ans=it->second;
      q=p[n][it->first];
    }
  }
  vector<int> v;
  while(q!=P(-1,-1)) {
    v.push_back(q.first);
    q=p[q.first][q.second];
  }
  reverse(v.begin(),v.end());
  cout << ans << endl;
  for(int i=1; i<v.size(); i++) {
    if(i!=1) cout << " ";
    cout << v[i];
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 19488
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string S;
  cin >> S;
  int Q;
  cin >> Q;
 
  vector<vector<string>> vec(Q, vector<string>(3));
  for (int i = 0; i < Q; i++) {
    for (int j = 0; j < 3; j++) {
        cin >> vec.at(i).at(j);
        if (vec.at(i).at(0)=="1") break;
    }
  }

  int count=0;
  for (int i = 0; i < Q; i++) {
    if (vec.at(i).at(0)=="1"){
       if (count==0) count=1;
       else count=0;
    }
    else{
      int N;
      N=S.size();
      if(vec.at(i).at(1)=="1"){
         if (count==0) S.insert(0,vec.at(i).at(2));
         else S.insert(N,vec.at(i).at(2));
      }
      else{
         if (count==0) S.insert(N,vec.at(i).at(2));
         else S.insert(0,vec.at(i).at(2));
      }
    }
  }

  if (count==1) reverse(S.begin(), S.end());

  cout << S << endl;
}

Measured memory_bytes: 40064
#pragma GCC optimize(2)
//Happy TLE and WA every day!
#include<bits/stdc++.h>
#define mp			make_pair
#define rep(i,n)	for(int i = 0; i < n; i++)
#define BINF		0x7fffffff
#define INF			0x3f3f3f3f
#define LINF		3223372036854775807
#define END(s)		{cout<<s; return 0;}
#define CON(s)		{cout<<s; continue;}
#define BRE(s)		{cout<<s; break;}
#define my			int
#define pb			push_back
#define int			long long
#define All(a)		a.begin(), a.end()  //with A in CAPITAL!!!
#define sz(a)		(int)a.size()
#define F			first
#define S			second
my rp = 666666;
const bool debug = 1;
const bool files = 0;
using namespace std;

int a[200200];
int sum[200200];

int binary(int ll, int rr){
	int l = ll, r = rr;
	while(l+1 < r){
		int mid = (l+r) / 2;
//		cout << l << " " << r << " " << mid << endl;
		int sum1 = sum[mid+1] - sum[ll], sum2 = sum[rr+1] - sum[mid+1];
//		cout << sum1 << " " << sum2 << endl;
		if(sum1 > sum2){
			r = mid;
		} else if(sum1 < sum2) {
			l = mid;
		} else{
			return ((sum[rr+1] - sum[ll]) / 2);
		}
	}
	int ans1 = sum[l+1] - sum[ll]; int ans3 = abs((sum[rr+1] - sum[ll]) - ans1);
	int ans2 = sum[l+2] - sum[ll]; int ans4 = abs((sum[rr+1] - sum[ll]) - ans2);
	if(abs(ans1 - ans3) < abs(ans2 - ans4)) return ans1;
	else return ans2;
}

signed main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	rep(i, n){
		cin >> a[i];
		if(!i) sum[i] = 0;
		else sum[i] = a[i-1] + sum[i-1];
	}
	sum[n] = sum[n-1] + a[n-1];
	int mn = LINF;
	for(int i = 1; i < (n-2); i++){
		int ss1 = sum[i+1], ss2 = sum[n] - sum[i+1];
		int s[4];
		s[0] = binary(0, i), s[2] = binary(i+1, n-1);
		s[1] = ss1 - s[0], s[3] = ss2 - s[2];
//		printf("s1=%d s2=%d s3=%d s4=%d\n", s[0], s[1], s[2], s[3]);
		sort(s, s+4);
//		printf("s1=%d s2=%d s3=%d s4=%d\n", s[0], s[1], s[2], s[3]);
		mn = min(mn, s[3] - s[0]);
	}
	cout << mn << endl;
	return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
 
using namespace std;
 
int main(){
	long long n,p;
	cin >> n >> p;
	map<long long ,long long> mp;
	
	if(p==1){
		cout << "1" << endl;
		return 0;
	}
	
	if(n==1){
		cout << p << endl;
		return 0;
	}
 
	long long num=p;
	for(long long i=2;i*i<=num;i++){
        if(num%i!=0)continue;
		while(num%i==0){
			mp[i]++;
			num /=i;
		}
	}
  
	long long ans=1;
	for(auto p:mp){
		long long x = p.first;
		long long y = p.second;
		if(y==0)continue;
		if(y>=n)ans*=pow(x,(y/n));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
MOD = 10 ** 9 + 7

n = int(input())
alst = list(map(int, input().split()))
bin_s = [2 ** i for i in range(60)]
cnt = [0 for _ in range(60)]

for a in alst:
    for j in range(60):
        if bin_s[j] & a:
            cnt[j] += 1

ans = 0
for i in range(60):
    ans += bin_s[i] * cnt[i] * (n - cnt[i])
    ans %= MOD
print(ans)

Measured memory_bytes: 124572
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-04-12 11:51:18
*/

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

#define all(x) (x).begin(),(x).end()
#define rev(x) greater<x>()
#define MOD 1000000007
#define INF 1000000000

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

LL modpower(LL n, LL m, LL mod)
{
    if (m == 0) {
        return 1;
    } else if (m % 2 == 0) {
        LL p = modpower(n, m/2, mod);
        return p*p % mod;
    } else {
        return n*modpower(n, m-1, mod) % mod;
    }
}

LL modinv(LL n, LL mod)
{
    return modpower(n, mod-2, mod);
}

LL modcombination(LL n, LL r, LL mod)
{
    LL ret = 1;

    for (int i = 0; i < r; i++) {
        ret *= (n-i);
        ret %= mod;
        ret *= modinv(i+1, mod);
        ret % mod;
    }

    return ret % mod;
}

int gcd(int k, int l)
{
    if (l > 0) return gcd(l, k%l);
    else return k;
}

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n) {
        for (int i = 0; i < n; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

    sort(all(s));
    sort(all(t), rev(char));

    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 256