akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }

//namespace std {
//    template <>
//    class hash<std::pair<int, int>> {
//    public:
//        size_t operator()(const std::pair<int, int>& x) const {
//            return hash<int>()(x.first) ^ hash<int>()(x.second);
//        }
//    };
//}

struct phash {
    inline size_t operator()(const pair<int, int> & p) const {
        const auto h1 = hash<int>()(p.first);
        const auto h2 = hash<int>()(p.second);
        return h1 ^ (h2 << 1);
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    unordered_map<int, unordered_set<int>> graph(N);
    vint a(N - 1), b(N - 1);
    rep(i, N - 1) {
        cin >> a[i] >> b[i];
        graph[a[i]].insert(b[i]);
        graph[b[i]].insert(a[i]);
    }
    unordered_map<pair<int, int>, int, phash> colors;
    int K = 0;
    REP(i, 1,  N + 1) {
        K = max(int(graph[i].size()), K);
    }

    int colored_num = 0;
    unordered_set<int> master_unused_color;
    REP(i, 1, K + 1) {
        master_unused_color.insert(i);
    }
    deque<pair<int, int>> nodes;
    nodes.push_back(make_pair(1, 0));

    while(1) {
        if (nodes.size() <= 0) break;
        auto nd = nodes.front();
        nodes.pop_front();
        int colored = nd.second;
        int color = 1;
        for (auto &adj : graph[nd.first]) {
            if (colors[make_pair(nd.first, adj)] != 0) continue;
            if (color == colored) color++;
            colors[make_pair(nd.first, adj)] = color;
            colors[make_pair(adj, nd.first)] = color;
            nodes.push_back(make_pair(adj, color));
            color++;
            
        }
       
    }
    cout << K << endl;
    rep(i, N - 1) {
        
        cout << colors[make_pair(a[i], b[i])] << endl;
    }
    
    return 0;
}

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

int main(){
  int N; cin >>N;
  if (N<1000) cout <<"ABC" <<endl;
  else cout <<"ABD" <<endl;
  return 0;
}


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

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

int main() {
    ll n;
    cin >> n;
    string res = "";
    while (n) {
        --n;
        res += (char)('a' + (n % 26));
        n /= 26;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <stdio.h>
#include <cmath>


using namespace std;

int R,C;
int ddata[15][10005];
int f[12];
int fa,num,ans,cnt,mmax;

void solve(){
    for(int i = 0; i < 1 << R; i++){
        for(int j = 0; j < R; j++){
            f[j] = i >> j & 1;
        }

        num = 0;

        for(int k = 0; k < C; k++){
            cnt = 0;
            for(int l = 0; l < R; l++){
                cnt += abs(f[l] - ddata[l][k]);
            }

            num += max(cnt,R-cnt);
        }

        ans = max(num,ans);
    }

    cout << ans << endl;
}

int main(){

    while(~scanf("%d %d",&R,&C)){

        if(R == 0 && C == 0){
            break;
        }

        for(int i = 0; i < R; i++){
            for(int j = 0; j < C; j++){
                scanf("%d",&ddata[i][j]);
            }
        }

        solve();
    }

    return 0;
}


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

using namespace std;

const int MOD = 1e9 + 7;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> pref(k+1), dp(k+1);
  dp[0] = 1;
  for(int kid = 1;kid<=n;kid++){
    int c;
    cin >> c;
    pref[0] = dp[0];
    dp[0] = 0;
    for(int i = 1;i<=k;i++){
      pref[i] = (pref[i-1] + dp[i]) % MOD;
    }
    for(int i = 0;i<=k;i++){
      dp[i] = (pref[i] - (i-c>=0 ? pref[i-c-1] : 0)) % MOD;
    }
  }

  int ans = dp[k];
  if(ans < 0) ans += MOD; 
  printf("%d\n",ans);

  return 0;
}


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

const int MOD = 1000000007;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

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

    int c[10][10];
    rep(i, 10) rep(j, 10) c[i][j] = 0;
    
    for (int i = 1; i <= N; i++) {
        string s = to_string(i);
        c[s[0] - '0'][s[s.size()-1] - '0']++;
    }

    lint res = 0;

    rep(i, 10) {
        rep(j, 10) {
            res += c[i][j] * c[j][i];
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
MAX = 100000
isPrime = [True]*(MAX+1)
isPrime[0] = False
isPrime[1] = False
for i in range(2,int((MAX)**0.5)):
    if isPrime[i]:
        for j in range(i*i, MAX+1, i):
            isPrime[j] = False

primes = [x for x in range(MAX+1) if isPrime[x]]

while True:
    m, a, b = map(int, input().split())
    if m == 0:
        break
    p=2
    q=2
    for x in primes:
        for y in primes:
            if x < y or x*y > m:
                break
            if a*x <= b*y and x*y > p*q:
                p = y
                q = x
    print(p,q)
            


Measured memory_bytes: 6780
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    int N;cin>>N;
    vector<int>d(N);
    ll ans=0;
    rep(i,N){
        cin>>d.at(i);
    }
    for(int i=0;i<N-1;i++){
        for(int j=i+1;j<N;j++){
            ans+=d.at(i)*d.at(j);
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 3604
N,M=map(int,input().split())
A=set([int(input()) for _ in range(M)])
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
	dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
	if i in A:
		dp[i]=0
print(dp[N])

Measured memory_bytes: 13216
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
using namespace std; using ll = long long;
using vl = vector<ll>; using vll = vector<vl>;
ll MOD = 998244353;
int main() {
	ll N, S;
	cin >> N >> S;
	vl A(N);
	for (ll i = 0; i < N; i++) cin >> A[i];
	vll dp(N + 1, vl(S + 1, 0));
	// 「0個目まで見て和が0」のみ1
	dp[0][0] = 1;
	for (ll i = 0; i < N; i++) {
		for (ll j = 0; j <= S; j++) {
			// 遷移【1】：i+1番目の数を使わない場合
			(dp[i + 1][j] += dp[i][j] * 2) %= MOD;
			// 遷移【2】：i+1番目の数を使う場合
			if (j + A[i] <= S) (dp[i + 1][j + A[i]] += dp[i][j]) %= MOD;
		}
	}
	cout << dp[N][S] << endl;
}

Measured memory_bytes: 73680
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const double dINF = 1e30;

double myabs(double a) {
    return a > 0 ? a : -a;
}

int main() {
    int N;
    cin >> N;
    std::vector<int> b;
    std::vector<int> p;
    std::vector<int> w;
    for (int i = 0; i < N; ++i) {
        int temp1, temp2, temp3;
        cin >> temp1 >> temp2 >> temp3;
        b.push_back(temp1);
        p.push_back(temp2);
        w.push_back(temp3 * 20);
    }

    vector<vector<double> > dp(1 << N, vector<double>(N, dINF));
    vector<vector<int> > dp_i(1 << N, vector<int>(N, 0));
    vector<vector<int> > dp_j(1 << N, vector<int>(N, 0));

    for(int i = 0; i < N; i++) {
        dp[1 << i][i] = 0;
    }

    for (int i = 1; i < 1 << N; ++i) {
        double sumw = 0;
        for (int j = 0; j < N; ++j) {
            if (i >> j & 1) {
                sumw += w[j];
            }
        }

        for (int j = 0; j < N; ++j) {
            if (!(i >> j & 1)) continue;
            for (int k = 0; k < N; ++k) {
                if (i >> k & 1) continue;
                double dist = ((70 + sumw) * myabs(p[j] - p[k]) / 2000);
                if (dp[i | (1 << k)][k] > dp[i][j] + dist) {
                    dp[i | (1 << k)][k] = dp[i][j] + dist;
                    dp_i[i | (1 << k)][k] = i;
                    dp_j[i | (1 << k)][k] = j;
                }
            }
        }
    }

    double min_dist = dINF;
    int min_j;
    for(int j = 0; j < N; j++) {
        if (dp[(1 << N) - 1][j] < min_dist) {
            min_dist = dp[(1 << N) - 1][j];
            min_j = j;
        }
    }

    int min_i = (1 << N) - 1;
    std::vector<int> ans_j;
    for (int i = 0; i < N; ++i) {
        ans_j.push_back(min_j);
        int min_i_next = dp_i[min_i][min_j];
        int min_j_next = dp_j[min_i][min_j];
        min_i = min_i_next;
        min_j = min_j_next;
    }

    std::reverse(ans_j.begin(), ans_j.end());

    for (int i = 0; i < N; ++i)
    {
        cout << b[ans_j[i]];
        if (i != N - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 12620
n = int(input())
A = []
B = []
C = []

for _ in range(n):
    a, b, c = map(int, input().split(" "))
    A.append(a)
    B.append(b)
    C.append(c)

dp_a = [None for _ in range(n)]
dp_b = [None for _ in range(n)]
dp_c = [None for _ in range(n)]

dp_a[0] = A[0]
dp_b[0] = B[0]
dp_c[0] = C[0]

for i in range(1, n):
    dp_a[i] = max([dp_b[i-1]+A[i], dp_c[i-1]+A[i]])
    dp_b[i] = max([dp_a[i-1]+B[i], dp_c[i-1]+B[i]])
    dp_c[i] = max([dp_a[i-1]+C[i], dp_b[i-1]+C[i]])

print(max(dp_a[n-1], dp_b[n-1], dp_c[n-1]))

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

int main() {
    int N;
    cin >> N;
    priority_queue< double, vector< double >, greater< double > > V;
    rep(i, N) {
        double v;
        cin >> v;
        V.push(v);
    }

    rep(i, N - 1) {
        double v1, v2;
        v1 = V.top();
        V.pop();
        v2 = V.top();
        V.pop();
        V.push((v1 + v2) / 2.0);
    }
    printf("%lf\n", V.top());
}

Measured memory_bytes: 256
#include <stdio.h>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
	int64_t N;
	std::cin >> N;

	int64_t AC = 0, WA = 0, TLE = 0, RE = 0;
	for (size_t n = 0; n < N; ++n)
	{
		std::string S;
		std::cin >> S;
		if (S == "AC") ++AC;
		if (S == "WA") ++WA;
		if (S == "TLE") ++TLE;
		if (S == "RE") ++RE;
	}

	std::cout << "AC x " << AC << std::endl;
	std::cout << "WA x " << WA << std::endl;
	std::cout << "TLE x " << TLE << std::endl;
	std::cout << "RE x " << RE << std::endl;

	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <math.h>

using namespace std;

void solve()
{
	double n;
	while(cin >> n, n)
	{
		int ans = 0;
		int k = sqrt(n);
		for(int a = 1; a <= k; ++a)
		{
			if(a * a > n)
			{
				break;
			}
			if(a * a == n)
			{
				++ans;
			}
			for(int b = a; b <= k; ++b)
			{
				if(a * a + b * b > n)
				{
					break;
				}
				if(a * a + b * b == n)
				{
					++ans;
				}
				for(int c = b; c <= k; ++c)
				{
					if(a * a + b * b + c * c > n)
					{
						break;
					}
					if(a * a + b * b + c * c == n)
					{
						++ans;
					}
					for(int d = c; d <= k; ++d)
					{
						if(a * a + b * b + c * c + d * d > n)
						{
							break;
						}
						if(a * a + b * b + c * c + d * d == n)
						{
							++ans;
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
}

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

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

using namespace std;

typedef long long LL;

int main() {
    string s;
    cin >> s;
    string r = s;
    reverse(r.begin(), r.end());
    if (s == r) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

#define FOR(i,a,b)    for (int i=(a)  ;i<(b) ;i++)
#define RFOR(i,a,b)   for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)      for (int i=0    ;i<(n) ;i++)
#define RREP(i,n)     for (int i=(n)-1;i>=0  ;i--)
#define EACH(i,a,b)   for (int i=(a)  ;i<=(b);i++)
#define REACH(i,a,b)  for (int i=(b)  ;i>=(a);i--)
#define ALL(a)        (a).begin(),  (a).end()
#define RALL(a)       (a).rbegin(), (a).rend()
#define YES()         printf("YES\n")
#define NO()          printf("NO\n")
#define Yes()         printf("Yes\n")
#define No()          printf("No\n")
#define in(a,x,b)     ((a) <= (x) && (x) < (b))

const int MOD = 1e9 + 7;
const int INF = 1 << 29;
const double EPS = 1e-10;

using ll = long long;
using P = pair<int,int>;
using V = vector<int>;
using Vll = vector<ll>;
using Vstr = vector<string>;

template<class T> bool inline chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool inline chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T = int> T inline input() { T x; cin >> x; return (x); }
template<class T> void inline print(T& x) { cout << x << '\n'; }
#define debug(x) cerr << #x << ": " << x << endl;

const int dxs[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
const int dys[] = { 0, -1, 0, 1, 1, -1, -1, 1 };
const int perm[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };

bool isOK(V v, int index, int key) {
  if (v[index] >= key) return true;
  else return false;
}

int binary_search(V v, int key) {
  int left = -1;
  int right = (int)v.size();

  while (right - left > 1) {
    int mid = left + (right - left) / 2;

    if (isOK(v, mid, key)) right = mid;
    else left = mid;
  }

  return right;
}

/*
int prime[1001001];
bool is_prime[1001001];

int sieve(int n) {
  int p = 0;
  for (int i = 0; i < n; i++) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i < n; i++){
    if (is_prime[i]){
      prime[p++] = i;
      for (int j = 2*i; j < n; j+=i) is_prime[j] = false;
    }
  }
  return p;
}
*/

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(16);

  int N;
  cin >> N;
  V X(N),Y(N);
  REP(i,N) cin >> X[i] >> Y[i];

  V sum1(N),sum2(N),sum3(N),sum4(N);
  REP(i,N) {
    sum1[i] = X[i] + Y[i];
    sum2[i] = -X[i] + Y[i];
    sum3[i] = -X[i] - Y[i];
    sum4[i] = X[i] - Y[i];
  }
  sort(ALL(sum1));
  sort(ALL(sum2));
  sort(ALL(sum3));
  sort(ALL(sum4));
  int ans = 0;
  chmax(ans, sum1[N-1] - sum1[0]);
  chmax(ans, sum2[N-1] - sum2[0]);
  chmax(ans, sum3[N-1] - sum3[0]);
  chmax(ans, sum4[N-1] - sum4[0]);
  print(ans);
}


Measured memory_bytes: 7944
import std;
import core.bitop;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "x", long, "g");
alias PQueue(T, alias less = "a>b") = BinaryHeap!(Array!T, less);

void main()
{
    auto n = lread();
    auto a = aryread();
    auto b = aryread();
    if (iota(n).filter!(i => a[i] > b[i])
            .map!(j => a[j] - b[j])
            .sum() <= (b.sum() - a.sum()) && iota(n).filter!(i => a[i] < b[i])
            .map!(j => (b[j] - a[j] + 1) / 2)
            .sum() <= (b.sum() - a.sum()))
        writeln("Yes");
    else
        writeln("No");
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 4272
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
a=rs()
if a==a.lower():
    print("a")
else:
    print("A")

Measured memory_bytes: 61916
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.List;
import java.util.regex.Pattern;

public class Main {
    public void solve(Stdin stdin, PrintWriter stdout) throws NumberFormatException, IOException {
        int w = stdin.nextInt();
        int h = stdin.nextInt();
        long[] p = new long[w];
        long[] q = new long[h];
        for (int i = 0; i < w; i++) p[i] = stdin.nextLong();
        for (int i = 0; i < h; i++) q[i] = stdin.nextLong();

        List<Tuple> tuples = new ArrayList<>();
        for (int i = 0; i < w; i++) tuples.add(new Tuple(p[i], 0));
        for (int i = 0; i < h; i++) tuples.add(new Tuple(q[i], 1));
        Collections.sort(tuples, Comparator.comparingLong(t -> t.x));

        long a = w + 1;
        long b = h + 1;
        long ans = 0;
        for (Tuple tuple : tuples) {
            if (tuple.y == 0) {
                ans += tuple.x * b;
                a--;
            } else {
                ans += tuple.x * a;
                b--;
            }
        }
        stdout.println(ans);
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        Stdin stdin = new Stdin();
        PrintWriter stdout = new PrintWriter(System.out, false);
        new Main().solve(stdin, stdout);
        stdout.flush();
    }

    public static class Stdin {
        private Deque<String> queue;
        private BufferedReader stdin;
        private Pattern delimiter;

        public Stdin() {
            queue = new ArrayDeque<>();
            stdin = new BufferedReader(new InputStreamReader(System.in));
            delimiter = Pattern.compile(" ");
        }

        public String next() throws IOException {
            if (queue.isEmpty()) {
                delimiter.splitAsStream(stdin.readLine()).forEach(queue::addLast);
            }
            return queue.removeFirst();
        }

        public int nextInt() throws NumberFormatException, IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws NumberFormatException, IOException {
            return Long.parseLong(next());
        }
    }

    private static class Tuple {
        private long x;
        private int y;
        public Tuple(long x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}


Measured memory_bytes: 61184
import java.util.Scanner;

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

        int n = sc.nextInt();
        int[] a = new int[n];

        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }
        for(int i = n-1; i >= 1; i --){
            System.out.print(a[i] + " ");
        }
        System.out.println(a[0]);

    }
}


Measured memory_bytes: 26264
#include<cstdio>
#define _USE_MATH_DEFINES
#include<cmath>
struct Point{double x, y;};

void koch(int n, Point a, Point b){
    if(n==0) return;
    Point s, t, u;
    double th = M_PI * 60. / 180.0;// 度からラジアンへの単位を変換

    s.x = (2.0 * a.x + 1.0*b.x)/3.0; // 2:1の重みづけ(普通の分割)
    s.y = (2.0 * a.y + 1.0*b.y)/3.0;
    t.x = (1.0 * a.x + 2.0*b.x)/3.0;
    t.y = (1.0 * a.y + 2.0*b.y)/3.0;
    u.x = (t.x-s.x) * cos(th) - (t.y -s.y) * sin(th) +s.x;
    u.y = (t.x-s.x) * sin(th) + (t.y -s.y) * cos(th) +s.y;

    koch(n-1, a, s);
    printf("%.8f %.8f\n", s.x, s.y);
    koch(n-1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);
    koch(n-1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);
    koch(n-1, t, b);
}
int main(){
    int n;
    Point a,b;

    scanf("%d", &n);    

    a.x = 0;
    a.y = 0;
    b.x = 100;
    b.y = 0;

    printf("%.8f %.8f\n", a.x, a.y);
    koch(n,a,b);
    printf("%.8f %.8f\n", b.x, b.y);
    
    return 0;
}


Measured memory_bytes: 2696
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
    int n, m;  cin >> n >> m;
    V A(n);
    
    int point_sum = 0;
    REP(i, n){  cin >> A[i];  point_sum += A[i];  }

    int count = 0;
    REP(i, n)
      if(A[i] * 4*m >= point_sum)  count++;

    cout << ((count >= m) ? "Yes" : "No") << endl;
	return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>
#include<boost/operators.hpp>
#include<boost/dynamic_bitset.hpp>
namespace adaptor = boost::adaptors;
template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<>>;

void Main()
{
	int N, M;
	std::cin >> N >> M;
	std::vector<std::set<int>> edge(N);
	for (int i : boost::irange(0, M))
	{
		int u, v;
		std::cin >> u >> v;
		--u; --v;
		edge[u].emplace(v);
	}
	int s, t;
	std::cin >> s >> t;
	--s; --t;
	boost::multi_array<bool, 2> flag(boost::extents[N][3]);
	struct data_t
	{
		int v;
		int c;
		int d;
	};
	std::queue<data_t> queue;
	queue.emplace(data_t{ s,0,0 });
	while (queue.size())
	{
		auto top = queue.front();
		queue.pop();
		if (flag[top.v][top.c])
		{
			continue;
		}
		else if (top.v == t && top.c == 0)
		{
			std::cout << top.d / 3 << std::endl;
			return;
		}
		flag[top.v][top.c] = true;
		for (int i : edge[top.v])
		{
			queue.emplace(data_t{ i,(top.c + 1) % 3,top.d + 1 });
		}
	}
	std::cout << -1 << std::endl;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}

Measured memory_bytes: 9984
# 087 B
A = int(input())
B = int(input())
C = int(input())
X = int(input())
n = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if X == (500*i + 100*j + 50*k):
                n += 1
print(n)


Measured memory_bytes: 67444
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
bool check(int n) {
    bool test[3] = {};
    while(n > 0) {
        test[((n%10)/2)-1] = 1;
        n /= 10;
    }
    return (test[0] + test[1] + test[2]) == 3;

}
void dfs(int depth, int cur, vector<int>& ans) {
    if (depth == 9)
        return;
    for(int num: {3, 5, 7}) {
        int nxt = cur*10 + num;
        if (check(nxt))
            ans.push_back(nxt);
        dfs(depth+1, nxt, ans);
    }
}
int main() {
    int N;
    cin >> N;
    vector<int> ans;
    dfs(0, 0, ans);
    sort(ans.begin(), ans.end());
    auto it = upper_bound(ans.begin(), ans.end(), N);
    cout << distance(ans.begin(), it) << endl;
    return 0;
}




Measured memory_bytes: 512
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			double a=sc.nextDouble();
			double b=sc.nextDouble();
			System.out.printf("%.0f %.0f\n",GCD(a,b),LCM(a,b));
		}
	}
	static double GCD(double x,double y){
		double g=0;
		if(y==0){
			g=x;
		}else{
			g=GCD(y,x%y);
		}
		return g;
	}
	static double LCM(double x,double y){
		return x*y/GCD(x,y);
	}
	
}

Measured memory_bytes: 28316
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    N, A, B = map(int, input().split())
    print(min(A, B), max(0, (A + B) - N))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3948
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>
#include <new>

//#include "All.h"

using namespace std;

#define EPS (1e-9)
#define INF (1e9)
#define MOD (ll)(1e9 + 7)
#define PI (acos(-1))
#define REP(i,a,n) for(int i=a;i<n;i++)
#define rep(i, n) REP(i,0,n)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" ; "IMPOSSIBLE")

using ll = long long int;

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

ll beki(ll a, ll b) {
    ll tmp = 1;
    rep(i, b) tmp *= a;
    return tmp;
}

int N, M;
vector<int> v[100010];
int depth[100010];
int ans[100010] = {};

void bfs();

int main() {
    
    cin >> N >> M;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        //双方向にvectorでグラフを表現
    }

    bfs();

    cout << "Yes" << endl;
    REP(i, 2, N + 1) {
        cout << ans[i] << endl;
    }
}

void bfs() {
    queue<int> q;
    //全てをINFで初期化
    rep(i, 100010) depth[i] = INF;
    q.push(1);
    depth[1] = 0;

    //キューが空になるまでループ
    while (q.size()) {
        //キューの先頭を取り出す
        int a = q.front(); q.pop();
        //移動先をループ
        rep(i, (int)v[a].size()) {
            //移動した後の部屋をbとする
            int b = v[a][i];
            if (depth[b] > depth[a] + 1) {
                q.push(b);
                depth[b] = depth[a] + 1;
                ans[b] = a;
            }
        }
    }
}

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

int in_gcd(int a, int b) {
	return b != 0 ? in_gcd(b, a % b) : a;
}
int gcd(int a, int b) {
	return a > b ? in_gcd(a, b) : in_gcd(b, a);
}

int main() {

	int N;
	cin >> N;
	int A;
	cin >> A;
	for(int i = 1; i < N; i++) {
		int B;
		cin >> B;
		A = gcd(A, B);
	}

	cout << A << endl;
}


Measured memory_bytes: 888
let split str delim =
  let open String in
  let rec doit s acc =
    match
      try Some (rindex s delim) with _ -> None
    with
    | None -> s :: acc
    | Some i -> doit (sub s 0 i) (sub s (i + 1) (length s - i - 1) :: acc) in
  doit str []

let () =
  let open Hashtbl in
  let n = read_int () in
  let tbl = create ~random:true n in
  let rec doit i =
    if i < n then begin
      begin match split (read_line ()) ' ' with
      | ["insert"; x] -> add tbl x true
      | ["find"; x] -> print_endline (if mem tbl x then "yes" else "no")
      | _ -> exit 1
      end;
      doit (i + 1)
    end in
  doit 0

Measured memory_bytes: 43836
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

 int main(){
   int x, y, z;
   cin >> x >> y >> z;

   int num = x / (y + z);

   while(num >= 0){
     if(x >= y * num + z * (num + 1)){
       cout << num << endl;
       break;
     }
     num--;
   }
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MD 1000000007
#define INF 1ll<<60
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main(){
    int n,k,q;
    cin>>n>>k>>q;
    vector<int> v(n+3);
    for(int i=0;i<q;i++){
        int tmp;
        cin>>tmp;
        v[tmp]++;
    }
    for(int i=1;i<=n;i++){
        if(k-(q-v[i])>0) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 1024
import heapq
Q = int(input())

lefts, rights = [], []  # lefts:aの左半分（中央値含む, 降順） rights:aの右半分
diff = 0    # aの中央値からの差の絶対値
bsum = 0    # bの累計

for i in range(Q):
    query = list(map(int, input().split()))
    if query[0] == 1:   # 更新クエリ(1)の処理
        a = query[1]
        bsum += query[2]
        if len(lefts) == 0:
            heapq.heappush(lefts, -a)   # 最初はleftsに降順に格納（中央値）
        else:
            if a <= -lefts[0]:
                heapq.heappush(lefts, -a)   # 現在の中央値以下ならleftsに降順にpush
                diff -= a + lefts[0]        # 現在の中央値(-lefts[0])との差
            else:
                heapq.heappush(rights, a)   # 現在の中央値より大きいならrightsにpush
                diff += a + lefts[0]        # 現在の中央値(-lefts[0])との差
        # lefts が rights と同数か1多い状態をキープするため、ずれたら移動
        if len(lefts) < len(rights):    # 偶数状態からrightsにpushされ、rightsが1件多い、奇数状態
            med = heapq.heappop(rights) # 新しい中央値をrightsからpop
            diff -= med + lefts[0]      # 奇数なので、rightsの1件以外相殺されるから、新中央値と旧中央値の差を加える
            heapq.heappush(lefts, -med) # 新しい中央値をleftsにpush
        elif len(lefts) > len(rights) + 1:  # 奇数状態からleftsにpushされ、leftsが2件多い、偶数状態
            med = -heapq.heappop(lefts)      # これまでの中央値をleftsからpop（-1倍）
            # 偶数なので、中央値がずれても相殺されるから、diffは修正不要
            heapq.heappush(rights, med)     # これまでの中央値をrightsにpush
    else:   # 求値クエリ(2)の処理
        x = -lefts[0]       # 中央値がx
        fx = diff + bsum    # 中央値からの差の絶対値(diff)とbの累計(bsum)の和
        print(x, fx)

Measured memory_bytes: 11176
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

constexpr int mod = int(1e9) + 7;

int add(int a, int b) {
	a += b;
	if(a >= mod)
		a -= mod;
	return a;
}

int mult(int a, int b) {
	return int(a * LL(b) % mod);
}

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

	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for(int &ai : a)
		cin >> ai;
	debug(n, k, a);

	int answer = 0;
	REP(i, n)
		FOR(j, i + 1, n - 1)
			if(a[i] > a[j])
				++answer;
	answer = mult(answer, k);
	debug(answer);

	REP(i, n) {
		int lesser = 0;
		REP(j, n)
			if(a[i] > a[j])
				++lesser;
		debug(i, lesser);
		answer = add(answer, mult(lesser, int((k * LL(k - 1) / 2) % mod)));
	}

	cout << answer << '\n';
}


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

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

  int ans=0;
  for (int i = 1; i <= n; i+=2)
  {
    int cnt = 0;
    for (int j = 1; j <= i; j++)
    {
      if(i%j==0)cnt++;
    }
    if(cnt==8) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
using ll = long long;

int main()
{
	int n;
	cin >> n;
	ll ans = 0;
	for(ll i = 1;i<=n;i++)
	{
		for(ll j = i;j<=n;j++)
		{
			if(i*j>=n)break;

			if(i==j)ans ++;
			else ans += 2;

		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i, n) for (int i = 0; i < ((int)(n)); i++) // 0-indexed昇順

int main()
{
    string S;
    cin >> S;
    for (int i = 0; i < (int)S.size(); i++)
    {
        if (S.at(i) == ',')
        {
            cout << ' ';
        }
        else
        {
            cout << S.at(i);
        }
    }
    cout << endl;
}

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

 
int main() {
   double W,H,x,y;
   cin>>W>>H>>x>>y;

   if(x==W/2&&y==H/2)cout<<W*H/2<<" "<<1<<endl;
   else cout<<W*H/2<<" "<<0<<endl;
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> l(n);
    long long sum = 0;
    int mx = 0;
    for(int i = 0; i < n; i++) {
        cin >> l[i];
        mx = max(mx, l[i]);
        sum += l[i];
    }
    if(mx < sum - mx) {
        cout << "Yes\n";
        return 0;
    }
    cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template <typename E>
struct SegmentTree{
  using H = function<E(E,E)>;
  int n,height;
  H h;
  E ei;
  vector<E> laz;

  SegmentTree(H h,E ei):h(h),ei(ei){}

  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    laz.assign(2*n,ei);
  }

  inline void propagate(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    laz[k]=ei;
  }

  inline void thrust(int k){
    for(int i=height;i;i--) propagate(k>>i);
  }

  void update(int a,int b,E x){
    if(a>=b) return;
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
  }

  E get_val(int a){
    thrust(a+=n);
    return laz[a];
  }

  void set_val(int a,E x){
    thrust(a+=n);
    laz[a]=x;
  }
};

//INSERT ABOVE HERE
signed main(){
  auto h=[](int a,int b){return a+b;};
  SegmentTree<int> seg(h,0);

  int n,m;
  cin>>n>>m;
  vector<int> ls(n),rs(n);
  for(int i=0;i<n;i++) cin>>ls[i]>>rs[i];

  seg.init(m+1);
  vector< vector<int> > G(m+1);
  for(int i=0;i<n;i++){
    rs[i]++;
    seg.update(ls[i],rs[i],1);
    G[rs[i]-ls[i]].emplace_back(i);
  }

  int cnt=0;
  vector<int> ans;
  for(int l=m;l>0;l--){
    for(int i:G[l]){
      seg.update(ls[i],rs[i],-1);
      cnt++;
    }
    int res=cnt;
    for(int i=0;i<=m;i+=l) res+=seg.get_val(i);
    ans.emplace_back(res);
  }
  reverse(ans.begin(),ans.end());
  for(int a:ans) cout<<a<<endl;
  return 0;
}


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

using namespace std;

int c[10][10], A[222][222];

int main()
{
	int H, W, r = 0;
	cin >> H >> W;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			cin >> c[i][j];
	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> A[i][j];
	for (int h = 0; h < H; h++) {
		for (int w = 0; w < W; w++) {
			if (A[h][w] < 0) continue;
			int d[10] = {};
			d[A[h][w]] = 1;
			set<pair<int, int>> q;
			q.insert(make_pair(1, A[h][w]));
			while (q.begin()->second != 1) {
				int u = q.begin()->second;
				q.erase(q.begin());
				for (int v = 0; v < 10; v++) {
					if (u == v) continue;
					int l = c[u][v];
					if (d[v] && d[v] <= d[u] + l)
						continue;
					auto it = q.find(make_pair(d[v], v));
					if (it != q.end())
						q.erase(it);
					d[v] = d[u] + l;
					q.insert(make_pair(d[v], v));
				}
			}
			r += d[1] - 1;
		}
	}
	cout << r << endl;
	return 0;
}


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

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

#define loop(i, n) for(int i = 0;i < n;i++)
#define INF 1000000000

int n, m, x;

int ans = INF;


void dfs(int i, vector<int> c, vector<vector<int>> a, int total, vector<int> check){
    bool ok = true;
    loop(j, m){
        if(check[j] < x) ok = false;
    }
    if(ok) ans = min(ans, total);

    if(i == n) return;

    dfs(i+1, c, a, total, check);

    loop(j, m){
        check[j] += a[i][j];
    }
    total += c[i];
    dfs(i+1, c, a, total, check);

    
}

int main(void){

    cin >> n >> m >> x;

    vector<int> c(n);
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> check(m);
    loop(i, n){
        cin >> c[i];
        loop(j, m){
            cin >> a[i][j];
        }
    }

    dfs(0, c, a, 0, check);

    if(ans == INF){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3596
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
typedef long long ll;
typedef unsigned long long ull;
typedef long double LD;
using namespace std;
const int INF = 2147483647;
const int INF2 = 0x3f3f3f3f;
const ll INF64 = 1e18;
const double INFD = 1e30;
const double EPS = 1e-6;
const double PI = 3.14159265;
const ll MOD = 1e9 + 7;
template <typename T>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    return w ? -X : X;
}
const int MAXN = 15;
int n, m, k;
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int dr2[8] = {1, 1, 1, -1, -1, -1, 0, 0};
int dc2[8] = {1, 0, -1, 1, 0, -1, 1, -1};
int CASE = 1;

int arr[MAXN];
int arr2[MAXN];
int base[MAXN];
int tot;
char text[MAXN];

int main() {
#ifdef LOCALLL
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr2[i]);
        base[i] = i + 1;
    }
    int cnt = 0;
    int sA = 0, sB = 0;
    do {
        cnt++;
        if (equal(base, base + n, arr)) {
            sA = cnt;
        }
        if (equal(base, base + n, arr2)) {
            sB = cnt;
        }
    } while (next_permutation(base, base + n));
    printf("%d", abs(sA - sB));
    return 0;
}

Measured memory_bytes: 256
L, R = map(int, input().split())
l = L % 2019
r = R % 2019
if R - L >= 2019 or l > r:
    print(0)
elif r - l == 1:
    print((l * r) % 2019)
else:
    mod2019 = []
    for i in range(l, r + 1):
        for j in range(i + 1, r + 1):
            mod2019.append((i * j) % 2019)
    mod2019 = sorted(mod2019)
    print(mod2019[0])

Measured memory_bytes: 97512
#include <iostream>
#include <queue>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdarg>
#include <set>
#include <limits>
#include <iomanip>

using namespace std;
#define INF 2e9 + 9
#define MOD 1000000007
#define ALL(v) v.begin() , v.end()
#define Int int64_t
#define pll pair<Int,Int>
template<class T> using pql = priority_queue<T, vector<T>>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;
#define ll(n) Int n; cin >> n;
#define LL(...) Int __VA_ARGS___; cin >> __VA_ARGS___;
#define OUT(...) cout << __VA_ARGS___;
#define RP(n, i, s) for(Int i = s ;i < n ;i++)
#define REP(n, i) for (Int i = 0; i < n; i++)
#define REPe(n, i) for (Int i = 1; i <= n; i++)
#define RPe(n, i, s) for (Int i = s; i <= n; i++)
#define upd_max(maxer, updater) if (maxer < updater) maxer = updater;
#define upd_min(miner, updater) if (miner > updater) miner = updater;

void ansYes(bool flag) {
    if (flag) cout << "Yes" << endl; else cout << "No" << endl;
}

void ansYES(bool flag) {
    if (flag) cout << "YES" << endl; else cout << "NO" << endl;
}

struct node {
    Int to;
    Int length;
};


vector<Int> divisor(Int n) {
    vector<Int> ret;
    for (Int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    return (ret);
}

/*
vector<vector<int>> to;
vector<int> flag;
vector<int> c;


Int dfs(int from, int mae) {
    flag[from] = 1;
    Int mini = 0;
    for (auto next : to[from]) {
        if (next == mae) continue;
        if (flag[next] == 1) {
            return -1;
        } else {
            mini = min(mini, dfs(next, from));
        }
    }
    return mini;
}*/

int dx8[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

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

struct datas {
    Int max;
    Int size;
};

class ContainChecker {
protected:
    Int minx, miny, maxx, maxy;
public:
    ContainChecker(Int minx, Int miny, Int maxx, Int maxy) : minx(minx), miny(miny), maxx(maxx), maxy(maxy) {};

    bool in(Int x, Int y) {
        return (minx <= x && miny <= y && x <= maxx && y <= maxy);
    }
};

Int getHead(Int n) {
    while(n / 10 > 0){
        n /= 10;
    }
    n %= 10;
    return n;
}

int main(void) {
    Int n, l;
    cin >> n >> l;
    vector<Int> a(n);
    REP(n,i){
        cin >> a.at(i);
    }
    Int point = -1;
    REP(n-1,i){
        if (a.at(i) + a.at(i+ 1 ) >= l) {
            point = i;
        }
    }
    if (point == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    cout << "Possible" << endl;
    REP(point,i){
        cout << i + 1 << endl;
    }
    for (int i = n -2;i >= point;i--){
        cout << i + 1 << endl;
    }
}




Measured memory_bytes: 1664
N,K = [int(x) for x in input().split()]
S = input()

DP = [0]
ans = 0
l = 0

for index,x in enumerate(S):
    if(index==0):
        if(x=='0'):
            DP.append(0)
            DP.append(1)
        else:
            DP.append(1)
    else:
        if(S[index-1]!=x):
            DP.append(DP[-1]+1)
        else:
            DP[-1]+=1
    if(index==N-1):
        if(x=='1'):
            DP.append(DP[-1])
        DP.append(DP[-1])

l=0
i = min(int((len(DP))/2)-1,K)
while(1+2*i+l<len(DP)):
    ans = max(DP[2*i+1+l]-DP[l],ans)
    l+=2

if(not '0' in S):
    ans = len(S)
elif(not '1' in S):
    ans = len(S)

print(ans)


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

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(){

    ll n; cin >> n;
    vector<ll> s(n+5,0);
    ll tmp;
    map<ll,ll> mp;
    mp[0]++;
    rep(i,n){
        // s[i+1] : A_iまでの和
        cin >> tmp;
        s[i+1] = s[i] + tmp;
        mp[s[i+1]] ++;
    }

    ll ans=0;
    for(auto itr : mp){
        // cout << itr.first << " " << itr.second <<  endl;
        tmp = itr.second;
        ans += tmp*(tmp-1)/2;
    }

    cout << ans << endl;




    return 0;
}

Measured memory_bytes: 14336
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
A = [0] * N
B = [0] * N
l = []

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

l.sort()
sum = 0
flag = 0

for i in range(N):
	sum += l[i][1]
	if sum > l[i][0]:
		flag = 1
		
if flag == 1:
	print('No')
else:
	print('Yes')
	

Measured memory_bytes: 63820
#include <bits/stdc++.h>
using namespace std;
const int MAX = (int)3e5;
const int MOD = (int)1e9 + 7;

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

void BinomialCoefficientInitialization() {
    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 int BinomialCoefficientCalculation(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 MultiplicationMOD(long long int a, long long int b) {
    return ((a % MOD) * (b % MOD) % MOD);
}

vector<pair<long long, long long> > primeFactorization(long long int a) {
    vector<pair<long long, long long> > returnVector;
    for (long long int i = 2; i * 1 <= a; ++i) {
        if (a % i != 0) continue;
        int number = 0;
        while (a % i == 0) { ++number; a /= i; }
        returnVector.emplace_back(i, number);
    }
    if (a != 1) returnVector.emplace_back(a, 1);
    return returnVector;
}

int main() {
    int N, M;
    cin >> N >> M;
    BinomialCoefficientInitialization();
    auto primePower = primeFactorization(M);
    long long int answer = 1;
    for (auto &i : primePower) {
        answer = MultiplicationMOD(answer, BinomialCoefficientCalculation(static_cast<int>(i.second + N - 1), N - 1));
    }
    cout << answer << endl;
}

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

int main() {
  int n;
  cin >>n;
  vector<int> a(n);
  rep(i,n) {
    cin>>a.at(i);
  }
  long double now=0;
  rep(i,n){
    now+=1.0/a[i];
  }
  long double ans=1.0/now;
  cout<<fixed<<setprecision(10);
  cout<<ans<<endl;
}

Measured memory_bytes: 3840
a,b,c,x = [int(input()) for i in range(4)]
cnt = 0
for ai in range(a+1):
  for bi in range(b+1):
    for ci in range(c+1):
      sumcoin = ai*500 + bi*100 + ci*50
      if sumcoin==x:
        cnt+=1
print(cnt)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Text;

namespace AtCoder
{
  class Program
  {
    static void Main(string[] args)
    {
      int N = int.Parse(Console.ReadLine());
      long p = 1;
      for(int i = 0; i < N; i++)
      {
        p *= (i + 1);
        p = p % (1000000007);
      }

      Console.WriteLine(p % (1000000007));
      Console.ReadLine();
    }

  }
}

Measured memory_bytes: 27208
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String s[] = new String[N];
		int t[] = new int[N];
		for (int i=0;i<N;i++) {
			s[i] = sc.next();
			t[i]= sc.nextInt();
		}
		String X = sc.next();
		int i;
		for (i=0;i<N;i++) {
			if(X.equals(s[i])) {
				break;
			}
		}
		int count =0;
		for (i=i+1;i<N;i++) {
			count+=t[i];
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 36160
//ITNOA
#include<iostream>
#include<cstdio>
using namespace std;
#define F first
#define S second
typedef long long ll;
const ll INF=1e18,MAX=3000,MOD=1e9+7;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
piii e[MAX];
ll d[MAX];
bool relax(int v){
	if(d[e[v].F.F]+e[v].S<d[e[v].F.S]&&d[e[v].F.F]!=INF){
		d[e[v].F.S]=d[e[v].F.F]+e[v].S;
		return 1;
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=0;i<m;i++)
		cin>>e[i].F.F>>e[i].F.S>>e[i].S;
	fill(d,d+n,INF);
	d[s]=0;
	for(int i=0;i<n-1;i++){
		for(int j=0;j<m;j++)
			relax(j);
	}
	bool t=0;
	for(int i=0;i<m;i++){
		if(relax(i))
			t=1;
	}
	if(t)	
		cout<<"NEGATIVE CYCLE\n";
	else{
		for(int i=0;i<=n-1;i++){
			if(d[i]==INF)
				cout<<"INF\n";
			else
				cout<<d[i]<<"\n";
		}
	}
	return 0;
}

Measured memory_bytes: 3296