akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_ll.hpp>
//typedef boost::multiprecision::cpp_ll ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E18;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define endl "\n"
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);


int main(){fastio
    ll n;cin>>n;
    ll a[n];rep(i,0,n-1)cin>>a[i];
    ll ans=inf;
    rep(i,-100,100){
        ll h=0;
        rep(j,0,n-1){
            h+=powl(i-a[j],2);
        }
        ans=min(ans,h);
    }
    cout<<ans<<endl;
    
}





Measured memory_bytes: 3628
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int main(){

    int A(0),B(0),K(0),a(0),b(0);

    cin >> A >> B >> K;

    for(int i(0);i < K;i++){

        a = A;
        b = B;
        if(i%2 == 0){
            if(a%2 == 1){
            
                B += (a - 1)/2;
                A = (a - 1)/2;
            }
            else if(a%2 == 0){
                B += a/2;
                A = a/2;
            }
        }
        else if(i%2 == 1){
            if(b%2 == 1){
                A += (b - 1)/2;
                B = (b - 1)/2;
            }    
            else if(b%2 == 0){
                A += b/2;
                B = b/2;
            }
        }
        

    }
    cout << A << " " << B << endl;
}

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

#define rep(i, N) for(int i = 0;i < N;i++)
typedef long long ll;

using namespace std;

int extgcd(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1; y = 0;
		return a;
	}
	else {
		int d = extgcd(b, a % b, x, y);
		int x_ = x, y_ = y;
		x = y_;
		y = x_ - a / b * y_;
		return d;
	}
}

int main(void) {
	int K; cin >> K;
	int ans = 0;
	int x, y;

	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = 1; k <= K; k++) {
				ans += extgcd(i, extgcd(j, k, x, y), x, y);
			}
		}
	}

	cout << ans << endl;

	return 0;
}

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

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

template<typename F> long long discrete_binary_search(long long ok, long long ng, F is_ok) {
    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
}

int N, K;
int A[220000];
signed main() {
    cin >> N >> K;
    rep(i, N) { cin >> A[i]; }
    sort(A, A + N);
    cout << discrete_binary_search(LLONG_MAX / 2, LLONG_MIN / 2, [&](int x) {
        int sum = 0;
        rep(i, N) {
            if (A[i] >= 0) {
                sum += discrete_binary_search(i, N, [&](int j) {
                    return A[i] * A[j] <= x;
                }) - i;
            } else {
                sum += N - discrete_binary_search(N, i, [&](int j) {
                    return A[i] * A[j] <= x;
                });
            }
        }
        return K <= sum;
    }) << endl;
}

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

using namespace std;

typedef long long ll;

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

  int l, r;
  cin >> l >> r;
  int mod = 2019, ans = (1 << 30);

  for (int i = l; i <= min(r, l + 2 * mod); i++) {
    for (int j = i + 1; j <= min(r, l + 2 * mod); j++) {
      int prod = (i % mod) * (j % mod) % mod;
      ans = min(ans, prod);
    }
  }

  cout << ans << "\n";


  return 0;
}


Measured memory_bytes: 256
//2018年  3月 23日 金曜日 03:33:36 JST
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
set<pi> I; // (r, l)
int at[MAX_N];
int A[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) {
		cin >> A[i];
		at[A[i]] = i;
	}
	I.insert(pi(N - 1, 0));
	ll res = 0;
	rep(i, 1, N + 1) {
		int a = at[i];
		auto it = I.lower_bound(pi(a, -1));
		pi p = (*it);
		int l = p.sec, r = p.fst;
		res += 1LL * i * (a - l + 1) * (r - a + 1);
		I.erase(it);
		if(l <= a - 1) I.insert(pi(a - 1, l));
		if(a + 1 <= r) I.insert(pi(r, a + 1));
	}
	cout << res << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 4224
import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('is_ok', '(u8[:],u8[:],u8,u8)')
    def is_ok(A, F, x, k):
        tmp = 0
        for a, f in zip(A, F):
            y = a * f
            if y > x:
                tmp += a - x // f
        return tmp <= k

    cc.compile()
    exit()

from my_module import is_ok

n, k = map(int, input().split())
A = np.array(input().split(), dtype="u8")
F = np.array(input().split(), dtype="u8")

A = np.sort(A)
F = np.sort(F)[::-1]

ok = 10 ** 12
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(A, F, mid, k):
        ok = mid
    else:
        ng = mid

print(ok)


Measured memory_bytes: 52268
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author dyominov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AInfiniteCoins solver = new AInfiniteCoins();
        solver.solve(1, in, out);
        out.close();
    }

    static class AInfiniteCoins {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int a = in.nextInt();
            int b = n / 500;
            out.print(a >= n - b * 500 ? "Yes" : "No");
        }

    }

    static class InputReader implements AutoCloseable {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public void close() {
        }

    }
}



Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define fs first
#define sc second
#define INF 1000000000
#define MOD 1000000007
#define EPS 0.00000001


int main() {
    int X, A; cin >> X >> A;
    if(X<A) cout << 0 << endl;
    else cout << 10 << endl;

    
    
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

using namespace std;

int n,a[100100],i,ans;

int main() {
	scanf("%d",&n);
	for (i=0;i<n;i++) scanf("%d",a+i);
	sort(a,a+n);
	for (i=n-1;i;i--) if (a[i] == a[i-1]) {
		if (ans) {
			printf("%lld\n",(long long)a[i] * ans);
			return 0;
		} else ans = a[i];
		i--;
	}
	puts("0");
}

Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

signed main()
{
    int n;
    vector<int> v;

    cin >> n;

    v.resize(n);

    int mx = 0;

    set<int> s;

    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
        mx = max(v[i], mx);
    }

    vector<bool> f(mx + 1, false);

    for (int i = 0; i < n; ++i)
    {
        if (s.count(v[i]))
        {
            f[v[i]] = true;
        }
        else
        {
            s.insert(v[i]);
        }
        for (int k = v[i] * 2; k <= mx; k += v[i])
        {
            f[k] = true;
        }
    }

    int ans = 0;

    for (int i = 0; i < n; ++i)
    {
        if (f[v[i]])
        {
            continue;
        }

        // cout << v[i] << endl;
        ans++;
    }

    cout << ans << endl;
}


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

int main(){
    int N;
    cin >> N;
    map<int, int> check;
    bool flag = true;
    for(int i=0;i<N;i++){
        int A;
        cin >> A;
        if(check[A]) flag = false;
        else check[A] = 1;
    }
    cout << (flag ? "YES" : "NO") << endl;
}

Measured memory_bytes: 9600
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var v=Arr.shift();
   if(v=="0 0")break;
   var NQ=v.split(" ").map(Number);
   var arr=[];
   for(var i=0;i<100;i++)arr[i]=0;
   for(var i=0;i<NQ[0];i++){
      var day=(Arr.shift()).split(" ").map(Number);
      var L=day.shift();
      for(var j=0;j<L;j++){
         arr[day[j]]++;
      }
   }
   var result=0;
   var max=Math.max.apply(null,arr);
   if(max>=NQ[1])NQ[1]=max;
   for(var i=0;i<arr.length;i++){
      if(arr[i]>=NQ[1]){
         result=i;
         break;
      }
   }
   console.log(result);
}

Measured memory_bytes: 12136
{-# LANGUAGE BangPatterns #-}

import Control.DeepSeq
import Data.Function
import Control.Applicative
import Data.List
import Data.Bits

main :: IO ()
main = do
 [h,w] <- map read . words <$> getLine
 let (!s0,!s1,!s2) = intoThree h w
 print $ s2-s0

tupInsert :: Int -> (Int,Int) -> (Int,Int,Int)
tupInsert !z (!x,!y)
  | z < x     = force (z,x,y)
  | z < y     = force (x,z,y)
  | otherwise = force (x,y,z)

intoThree :: Int -> Int -> (Int,Int,Int)
intoThree !h !w = minimumBy (compare `on` (\(!s0,!s1,!s2) -> s2-s0)) $ do
  (!x,!y) <- [(h,w), (w,h)]
  let !xd3 = x `div` 3
  !x0 <- [max 0 $ xd3 - 3 .. min x $ xd3 + 4]
  return $! tupInsert (x0 * y) $ intoTwo (x - x0) y
  
intoTwo :: Int -> Int -> (Int,Int)
intoTwo !h !w
  | h > w     = go h w
  | otherwise = go w h
  where
    go !long !short
      | even short = force (halfarea,halfarea)
      | otherwise  = force (short * halflong, short * (long - halflong))
      where halflong = long `shiftR` 1
            halfarea = (long*short) `shiftR` 1


Measured memory_bytes: 508
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>

int main() {
  uint64_t X = 0;
  std::cin >> X;

  uint64_t value = 100, year = 0;
  while (value < X) {
    value *= 1.01;
    year++;
  }

  std::cout << year << std::endl;

  return 0;
}

Measured memory_bytes: 3596
using System;

namespace AizuOnlineJudge
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = Converter(Console.ReadLine());
            Console.WriteLine(Calc(array));
            Console.ReadLine();
        }

        static int[] Converter(string str)
        {
            var array = str.Split(' ');
            return Array.ConvertAll(array, int.Parse);
        }

        static string Calc(int[] array)
        {
            string symbol;
            var sign = Math.Sign(array[0] - array[1]);
            switch (sign)
            {
                case 1:
                    symbol = ">";
                    break;
                case -1:
                    symbol = "<";
                    break;
                default:
                    symbol = "==";
                    break;
            }
            return "a " + symbol + " b";
        }
    }
}


Measured memory_bytes: 8876
from statistics import mean, median, variance, stdev

N = int(input())
A = list(map(int, input().split()))

A2 = [a-(idx+1) for idx, a in enumerate(A)]
# print(A2, sum(A2), median(A2))

center = median(A2)

ans = 0
for a in A2:
    ans += abs(a-center)
print(int(ans))

Measured memory_bytes: 27244
#include <stdio.h>
#include <ctype.h>

int main(void)
{
    enum { S = 11 };
    char s1[S], s2[S], s3[S];
    scanf("%s %s %s", s1, s2, s3);
    printf("%c%c%c\n", toupper(s1[0]), toupper(s2[0]), toupper(s3[0]));
    return 0;
}


Measured memory_bytes: 128
import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

s = arr_data[0][0]

print(s.replace(","," "))


Measured memory_bytes: 3060
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
template<class Read>void in(Read &x){
    x=0;
    int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        f|=(ch=='-');
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x=f?-x:x;
    return;
}
int n,a[100005],b[100005],c[100005],f[100005][10];
int main(){
	in(n);
    for(int i=1;i<=n;i++)in(a[i]),in(b[i]),in(c[i]);
    for(int i=1;i<=n;i++){
        f[i][1]=max(f[i-1][2],f[i-1][3])+a[i];
        f[i][2]=max(f[i-1][1],f[i-1][3])+b[i];
        f[i][3]=max(f[i-1][1],f[i-1][2])+c[i];
    }
    printf("%d\n",max(f[n][1],max(f[n][2],f[n][3])));
	return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define ull unsigned ll
#define pb push_back
#define popb pop_back
#define mt make_tuple
#define eb emplace_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair <int,int>
#define piii pair <pii,int>
#define piiii pair <pii,pii>
#define pll pair <ll,ll>
#define plll pair <pair <ll, ll>, ll>
#define rep0(i,n) for(ll i=0;i<(ll)n;i++)
#define rep1(i,n) for(ll i=1;i<=(ll)n;i++)
#define rep(i,x,y) for(ll i=(ll)x;i<=(ll)y;i++)
#define reprev(i,n) for(ll i=(ll)n;i>=0;i--)
#define all(c) c.begin(),c.end()
#define print(a) rep0(i,a.size()) cout << a[i] << " "
#define hi() cout << "\nHello, I am error. Can you find me? :):):)\n"
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_eppoch().count())
 
using namespace __gnu_pbds;
using namespace std;
using ordered_set =  tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>;

// FOR DEBUGGING
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", ";
	else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifndef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

const int mod = 1e9+7;
const long double PI = acos(-1);

ll power(ll x, ll y){
	x %= mod;
	ll ans = 1;
	while(y){
		if(y&1) ans = (ans*x)%mod;
		y /= 2;
		x = (x*x)%mod;
	}
	return ans;
}

void solve(){

	int n;
	cin >> n;
	vector <ll> a(n);
	rep0(i,n) cin >> a[i];
	sort(all(a));

	ll ans = 0, j = n-1;
	rep0(i,n){
		if(!i) continue;
		if(i%2==0) ans += a[j];
		else{
			ans += a[j];
			j--;
		}
	}
	cout << ans;

	return;
}
	
int main(){

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

	int TC = 1,t = 0;
	// cin >> TC;
	while(t++ < TC){
		// cout << "Case #" << t << ": ";
		solve();
		// cout << "\;
	}

	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";

	return 0; 
}

Measured memory_bytes: 4780
# https://misteer.hatenablog.com/entry/AGC011-B
def solve(n, a):
    a.sort()

    res = 0
    sum_ = 0
    for i in range(n):
        if sum_ * 2 < a[i]:
            res = 0
            # a[i-1]までの累積和がa[i]を吸収できないとき、
            # a[i]までの累積和の生き物の色候補は、i一色だけとなる（res+=1で表現）
        sum_ += a[i]
        res += 1
    return res


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))

# 自身の2倍以下の大きさの生き物を吸収できる
# 「残れるかどうか」は、生き物の大きさについて単調性が成り立つ
# ある生き物が残れるなら、それより大きい生き物はすべて残れる

# a[i]までの累積和の生き物の色を考える
# i色は必ず使える
# a[i]以下の生き物をa[i]ベースで吸収すればいいから
# a[i-1]までの累積和がa[i]を吸収できるなら、
# a[i-1]までの累積和の生き物の色が使える


Measured memory_bytes: 14304
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = sorted(LIR(n), key=lambda x:x[1])
ret = 0
for i in range(n):
    ret += L[i][0]
    if ret > L[i][1]:
        print('No')
        break
else:
    print('Yes')

Measured memory_bytes: 85468
#include<stdio.h>
int main()
{
    int r,g,b, result;
    scanf("%d %d %d",&r ,&g, &b);
    result = 100*r + 10*g +b;
    if( result%4==0 )
    {
         printf("YES");
    }
    else
    {
         printf("NO");
    }
    return 0;
}

Measured memory_bytes: 2112
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

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

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

	int N;
	
	cin >> N;

	int A[N];

	map<int, int> cards;

	rep(i, N)
	{
		cin >> A[i];
		if (cards.find(A[i]) == cards.end())
		{
			cards[A[i]] = 1;
		}
		else
		{
			cards[A[i]]++;
		}
	}

	map<int, int>::iterator it;
	int count = 0;
	for (it = cards.begin(); it != cards.end(); it++)
	{
		while(it->second>=3)
		{
			it->second -= 2;
		}

		if (it->second >= 2)
		{
			count++;
		}
	}

	if (count % 2)
	{
		cout << cards.size() - 1 << endl;
	}
	else
	{
		cout << cards.size() << endl;
	}


	
	return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
// #include <boost/lexical_cast.hpp>
using namespace std;

#define ll long long int
#define vll vector<ll>
#define vllv vector<vector<ll>> 
#define vpii vector<pair<ll,ll>>
#define pll  pair<ll,ll>
#define sz size()
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll MOD=1000000000+7;
ll ceil1(ll n,ll m){if(n%m==0){return n/m;}return n/m +1;}
ll factor(ll n){
    vll ans;
	if(n==2)ans.pb(2);
	else
    {for(ll i=2;i*i<=n;i++){if(n%i==0 && n%i!=i){ans.pb(i);if(n/i!=i)ans.pb(n/i);}}ans.pb(n);}
    return ans.sz+1;
}
ll fact(ll n){ll res = 1;for (ll i = 2; i <= n; i++)res = res * i; 
    return res; } 
  
ll nCr(ll n, ll r){ return fact(n) / (fact(r) * fact(n - r)); } 
  
void dfs(vllv &v,ll k,vll &par,vll &dis,ll p)
{
    par[k]=p;
    dis[k]=dis[p]+1;
    for(ll i=0;i<v[k].sz;i++){
        if(v[k][i]!=p){
            dfs(v,v[k][i],par,dis,k);
        }
    }
}
bool sortbysec(const pair<string,int> &a,const pair<string,int> &b){return (a.second<b.second);} 

ll pow2(ll n,ll k){ll ans=1;
    while(k>0){
        if(k%2==1)ans=ans*n;n=n*n;k/=2;
    }return ans;}
bool prime(int n){
    int i,j;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

void solve()
{
	ll n;
	cin>>n;
	vll a(n);
	for(ll i=0;i<n;i++)
		cin>>a[i];
	ll c1=0,c2=0,c3=0,c4=0,c5=0,c6=0,c7=0,c8=0,c9=0;
	for(ll i=0;i<n;i++)
	{
		if(a[i]<=399)
			c1++;
		else if(a[i]<=799)
			c2++;
		else if(a[i]<=1199)
			c3++;
		else if(a[i]<=1599)
			c4++;
		else if(a[i]<=1999)
			c5++;
		else if(a[i]<=2399)
			c6++;
		else if(a[i]<=2799)
			c7++;
		else if(a[i]<=3199)
			c8++;
		else
			c9++;
	}
	ll mx=min(1ll,c1)+min(1ll,c2)+min(1ll,c3)+min(1ll,c4)+min(1ll,c5)+min(1ll,c6)+min(1ll,c7)+min(1ll,c8);
	if(mx==0  && c9>1)
		cout<<1<<" "<<mx+c9;
	else
		cout<<mx<<" "<<mx+c9;
	return;
}            
int main()
{
	fast;
    ll q;
    q=1;
    // cin>>q;
    while(q--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

  ll R = input();

  output(3.1415*2*R);

  return 0;
}


Measured memory_bytes: 3784
using System;
class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int k = int.Parse(Console.ReadLine());
        int r = 1;
        for (int i = 0; i < n; i++)
        {
            r = Math.Min(r * 2,r + k);
        }
        Console.WriteLine(r);
    }
}

Measured memory_bytes: 11092
#include <algorithm>
#include <iostream>

using namespace std;

int Sum(int x) {
  int s = 0;
  while (x) {
    s += x % 10;
    x /= 10;
  }
  return s;
}

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

  int N;
  cin >> N;
  if (N % 10 == 0)
    cout << 10 << endl;
  else
    cout << Sum(N) << endl;

  return 0;
}


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

int F[102][102];
int xg,yg,ok;

void Maze(int X,int Y,int C){
	if(F[X][Y]!=C)
		return;

	

	if(X==xg&&Y==yg){
		cout << "OK"<<endl;
		ok++;
	}

	F[X][Y]='.';

	Maze(X-1,Y  ,C);
	Maze(X  ,Y+1,C);
	Maze(X+1,Y  ,C);
	Maze(X  ,Y-1,C);
	
}



int main(){	
	while(1){
		ok=0;

		int w,h,xs,ys,n,c,d,x,y;

		cin >>w>>h;
		if(w==0&&h==0)
			return 0;

		cin >>xs>>ys;
		cin >>xg>>yg;
		cin >>n;


		for(int i=1; i<=w; i++)
			for(int j=1; j<=h; j++)
				F[j][i]=0;

		for(int i=1; i<=w;i++){
				F[w+1][i]=6;
				F[0][i]=6;
		}
		for(int i=1; i<=h;i++){
				F[i][h+1]=6;
				F[i][0]=6;
		}

		int N=0;
		while(N<n){
			cin >>c>>d>>x>>y;

			if(d){
				for(int i=x; i<x+2; i++)
					for(int j=y; j<y+4; j++){
						F[i][j]=c;
				}
			}else{
				for(int i=x; i<x+4; i++)
					for(int j=y; j<y+2; j++){
						F[i][j]=c;
					}
			}

			N++;
		}
		
		Maze(xs,ys,F[xs][ys]);

		if(ok==0)
			cout <<"NG"<<endl;

	}

}

Measured memory_bytes: 1220
using System;
using System.Linq;

namespace ABC144
{
    class D
    {
        static void Main(string[] args)
        {
            double[] input = Console.ReadLine().Split().Select(double.Parse).ToArray();
            double a = input[0];
            double b = input[1];
            double x = input[2];

            var S = x / a;

            if (a * b / 2 < S)
            {
                var h = (a * b - S) * 2 / a;
                var deg = Math.Atan2(a, h) * 180 / Math.PI;
                Console.WriteLine(90 - deg);
            }
            else
            {
                var w = 2 * S / b;
                var deg = Math.Atan2(w, b) * 180 / Math.PI;
                Console.WriteLine(90 - deg);
            }
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>

using namespace std;

int main()
{
	int l, m, n, tmp, tmp2;
	
	while(1){
		cin >> l;
		if(l == 0){
			break;
		}
		tmp = tmp2 = 0;
		for(int i = 1, f = 0; i <= 12; i++){
			cin >> m >> n;
			tmp += (m-n);
			if(tmp >= l && f == 0){
				tmp2 = i;
				f = 1;
			} else if(tmp < l && f == 1){
				tmp2 = 0;
				f = 0;
			}
		}
		
		if(tmp2 == 0){
			cout << "NA" << endl;
		} else {
			cout << tmp2 << endl;
		}
	}
	
	
	return 0;
}

Measured memory_bytes: 0
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
#define all(x) (x).begin(),(x).end()

int main() {
  int n, m;
  cin >> n >> m;
  vector<ll> a[3];
  for(int i=0; i<n; i++){
    for(int j=0; j<3; j++){
      ll num; cin >> num;
      a[j].push_back(num);
    }
  }
  ll res = 0;
  for(int bit=0; bit<(1<<3); bit++){
    //各条件ごとのケーキの貢献度を調べ、貪欲に食べる
    vector<ll> score;
    for(int i=0; i<n; i++){
      ll num = 0;
      for(int j=0; j<3; j++){
        if(bit & (1<<j)) num += a[j][i];
        else num -= a[j][i];
      }
      score.push_back(num);
    }
    sort(all(score), greater<ll>());
    ll sum = 0;
    for(int i=0; i<m; i++){
      sum += score[i];
    }
    res = max(res, sum);
  }
    cout << res << ln;
  }


Measured memory_bytes: 256
#include <string>
#include <iostream>
using namespace std;
int main(){
  char a[6];
  cin >> a[0];
  if(a[0] == 'S'){
    cout << "Cloudy" << endl;
  }else if(a[0] == 'C'){
    cout << "Rainy" << endl;
  }else if(a[0] == 'R'){
    cout << "Sunny" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, K = map(int, input().split())
A = list(map(int, input().split()))

max_dig = 40
K_bin = format(K,'b').zfill(max_dig)
A_bin = []
greed = [0] * max_dig
score0 = [0] * max_dig
score1 = [0] * max_dig

for i in range(N):
	A_bin.append(format(A[i], 'b').zfill(max_dig))

for i in range(max_dig):
	c_one = 0
	c_zero = 0
	for j in range(N):
		if A_bin[j][i] == '1':
			c_one += 1
		else:
			c_zero += 1
		
	if c_zero > c_one:
		greed[i] = '1'
	else:
		greed[i] = '0'
		
	score0[i] = c_one * (2 ** (max_dig - i - 1))
	score1[i] = c_zero * (2 ** (max_dig - i - 1))

greed = ''.join(greed)
ans = 0

for i in range(max_dig):
	ans_list = ''
	if K_bin[i] == '1':
		ans_list = K_bin[:i] + '0' + greed[i + 1:]
		tmp = 0
		for j in range(max_dig):
			if ans_list[j] == '1':
				tmp += score1[j]
			else:
				tmp += score0[j]
				
		if tmp > ans:
			ans = tmp
			
ans_list = K_bin
tmp = 0
for j in range(max_dig):
	if ans_list[j] == '1':
		tmp += score1[j]
	else:
		tmp += score0[j]
		
if tmp > ans:
	ans = tmp

print(ans)

Measured memory_bytes: 86232
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int MOD = 1e9 + 7;
#define INF ((1<<30)-1)
#define LINF (1LL<<30)


bool dp[110000];
int a[110];
int n, k;

int main() {
    cin >> n >> k;
    for(int i = 0; i < n; i++)cin >> a[i];
    for(int i = 0; i <= k; i++){
        dp[i] = false;
        for(int j = 0; j < n; j++){
            if(i-a[j] >= 0) dp[i] |= !dp[i-a[j]];
        }

    }
    if (dp[k]) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
    
}

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

int main()
{
	int n;
	double ans = 0.0 , a;
	cin >> n;
	for (int i = 1; i <= n ; i++)
	{
		cin >> a;
		ans += 1.0 / a;
	}
	ans = 1/ans;
	cout <<  setprecision(16) << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007


int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int x;
    cin>>x;
    int sum=0;
    int ans=0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                sum = 500*i+100*j+50*k;
                if(sum==x){
                    ans++;
                }
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			String cards = sc.next();
			if(cards.equals("-")) {
				break;
			}
			int m = sc.nextInt();
for(int i=0;i<m;i++) {
	int count=sc.nextInt();
	String move=cards.substring(0,count);
	String move2=cards.substring(count);
	cards=move2+move;
}
System.out.println(cards);
		}
	}
}



Measured memory_bytes: 26352
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

from heapq import heappop,heappush
from collections import defaultdict
f=defaultdict(int)
pq=[]

def push(a,b,c):
    if f[(a,b,c)]==0 and a<X and b<Y and c<Z:
        heappush(pq,(-(A[a]+B[b]+C[c]),a,b,c))
        f[(a,b,c)]=1

push(0,0,0)

for i in range(K):
    d,a,b,c=heappop(pq)
    print(-d)
    push(a+1,b,c)
    push(a,b+1,c)
    push(a,b,c+1)



Measured memory_bytes: 54744
#include <stdio.h>

/**
 * 現在の配列を出力する
 */
void trace(int A[], int N)
{
	int i;
	for (int i = 0; i < N; i++)
	{
		if(i > 0) printf(" ");
		printf("%d", A[i]);
	}
	printf("\n");
}

/**
 * 挿入ソート
 */
void insertionSort(int A[], int N)
{
	int j, i, v;
	for (int i = 1; i < N; i++) // 先頭はソート済みとみなして、1のインデックスからスタートする
	{
		v = A[i]; // 一時変数vに保存
		j = i - 1; //挿入位置を探す変数
		while( j >= 0 && A[j] > v ){ // 一つずつ先頭に向かっていって、vより大きいならインデックスを1つ後ろにずらした位置にいれて行く
			A[j + 1] = A[j];
			j--;
		}
		A[j + 1] = v;
		trace(A, N);
	}
}

int main()
{
	int N, i, j; // N...数列の長さ
	int A[100]; // 配列の長さを制約上限で確保

	scanf("%d", &N); // 標準入力
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
	}
	trace(A, N);
	insertionSort(A, N);
	return 0;
}


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

bool sosu[200000] = {false};
long long int ans[200000] = {0};

int main() {

  vector<long long int> num;

  for ( long long int i = 2; i < 200000; i++ ) {
    ans[i] = ans[i-1];
    if ( sosu[i] == false ) {
      ans[i] += i;
      num.push_back(i);
      for ( long long int j = i*2; j < 200000; j+=i ) {
	sosu[j] = true;
      }
    }
  }

  int n;

  while(true) {

    cin >> n;
    if ( n == 0 ) break;

    cout << ans[num[n-1]] << endl;

  }

  return 0;

}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i < n; i++)
#define repv(i,n) for(int i = n-1; i >= 0; i--)
#define fi first
#define sc second
#define pb push_back
using namespace std;
typedef long long ll;

char BUF[3500000];
inline void I(int&a){scanf("%d",&a);}
inline void I(int&a,int&b){scanf("%d%d",&a,&b);}
inline void I(int&a,int&b,int&c){scanf("%d%d%d",&a,&b,&c);}
inline void I(int&a,int&b,int&c,int&d){scanf("%d%d%d%d",&a,&b,&c,&d);}
inline void L(ll&a){scanf("%lld",&a);}
inline void L(ll&a,ll&b){scanf("%lld%lld",&a,&b);}
inline void L(ll&a,ll&b,ll&c){scanf("%lld%lld%lld",&a,&b,&c);}
inline void L(ll&a,ll&b,ll&c,ll&d){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);}
inline void S(string&str){str.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)str.pb(BUF[i]);}
inline void SV(vector<int>&v){v.clear();scanf("%s",BUF);int s=strlen(BUF);rep(i,s)if('a'<=BUF[i]&&BUF[i]<='z')v.pb(BUF[i]-'a');else v.pb(BUF[i]-'A');}

const auto EPS = 1e-10;
const auto INF = 100000000;
const auto MOD = 1000000007;
typedef pair<ll,ll> P;

int n;
int a[200000], b[200000];
ll dp[4001][4001];
ll kai[10001];

ll mod_pow(ll x, ll y){
    ll ret = 1;
    while(y) {
        if(y&1) ret = ret*x%MOD;
        x = x*x%MOD;
        y /= 2;
    }
    return ret;
}

ll conb(ll x, ll y) {
    ll X = kai[x], Y = kai[y], Z = kai[x-y];
    ll ret = X * mod_pow(Y, MOD-2)%MOD;
    return ret * mod_pow(Z, MOD-2) % MOD;
}

int main() {
    cin >> n;
    kai[0] = 1;
    for(ll i = 1; i <= 10000; i++) kai[i] = kai[i-1]*i%MOD;
    rep(i,n) I(a[i],b[i]);
    rep(i,n) {
        dp[2000-a[i]][2000-b[i]]++;
    }
    rep(i,4001) rep(j,4001) {
        if(i != 4000) dp[i+1][j] = (dp[i+1][j]+dp[i][j])%MOD;
        if(j != 4000) dp[i][j+1] = (dp[i][j+1]+dp[i][j])%MOD;
    }
    ll ans = 0;
    rep(i,n) {
        ans = (ans+dp[2000+a[i]][2000+b[i]])%MOD;
        ans = (ans-conb((a[i]+b[i])*2, a[i]*2)+MOD)%MOD;
    }
    ans = ans * mod_pow(2, MOD-2) % MOD;
    cout << ans << endl;
}


Measured memory_bytes: 127232
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef pair <int,int> pii;
typedef vector <pii> vpii;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef long long int lli;
typedef vector <lli> vlli;
typedef vector <vlli> vvlli;
typedef vector <string> vs;
typedef vector <bool> vb;

#define rep(i, n) for( i = 0; i < (n); ++i)
#define repA(i, a, n) for( i = a; i <= (n); ++i)
#define repD(i, a, n) for( i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sortr(x) sort(x.begin(),x.end(),greater <int> ())
#define mod 1000000007
#define ff first
#define ss second
#define fill(a,c)  memset(a, c, sizeof (a))
#define formap(i,v) for(auto &i: v)
#define dbg(x) cout << #x << " = " << x << '\n'
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl(v) cout<<#v<<" = \n"; { int c=0; formap(it,v) \
cout<<"    "<<#v<<"["<< ++c <<"] = "<<it<<endl;} cerr<<endl
#define dbgstlp(v) cout<<#v<<" = \n"; { int c=0; formap(it,v) \
cout<<"    "<<#v<<"["<< ++c <<"] = "<<it.first<<" , "<<it.second<<endl;} cerr<<endl
#define PI  3.14159265358979323846
#define pb push_back




int main() {
     cin.sync_with_stdio(0);cin.tie(0);
     cin.exceptions(cin.failbit);
    
    
    int i,j,n,k,ans,b,val;
    cin>>n;
    k= n/100; val=n%100;
    if (val>k*5)ans=0;
    else ans=1;
    cout<<ans<<endl;
    
     
     
     
     
     
     
     
     
     
   
   
	return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn=500005,mod=1e9+7;
typedef long long ll;

int read()
{
	int f=0; char c=getchar();
	while(c>'9' || c<'0') c=getchar();
	while(c<='9' && c>='0') {f=f*10+c-'0'; c=getchar();}
	return f;
}

ll n,k;
ll ans;

int main()
{
 	cin>>n>>k;
 	for(ll i=k;i<=n+1;i++)
 	{
		ans=(ans+((n)+(n-i+1))*i/2%mod-(i-1)*i/2%mod+1)%mod;
		//cout<<ans<<endl;
		ans=(ans+mod)%mod;
 	}
 	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)

using namespace std;

void putseq(int seq[],int n)
{
  REP(i,n)
  {
    if(i) cout<<' ';
    cout<<seq[i];
  }
  cout<<endl;
}

int main()
{
  int N;
  cin>>N;
  int seq[N];
  REP(i,N) cin>>seq[i];
  putseq(seq,N);

  int key,j;
  for(int i=1;i<N;i++)
  {
    key=seq[i];
    j = i - 1;
    while(j>=0 && seq[j] > key)
    {
      seq[j+1] = seq[j];
      j--;
    }
    seq[j+1] = key;
    putseq(seq,N);
  }
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (1<<29)
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int p){
	for(int i=2;i<=sqrt(p);i++){
		if(!p%i)return false;
	}
	return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b==1)return a%MOD;
    if(b%2)return modpow(a,b-1)*a%MOD;
    else return modpow(a,b/2)*modpow(a,b/2)%MOD;
}
int comb(int a,int b){
    if(b==0||a==b)return 1;
    if(b==1)return a%MOD;
    return (comb(a-1,b-1)+comb(a-1,b))%MOD;
}
int n,k,a[100000];
signed main(){
    cin>>n>>k;
    rep(i,n)cin>>a[i];
    sort(a,a+n);
    int g=a[0];
    for(int i=1;i<n;i++)g=gcd(a[i],g);
    if(k>a[n-1]||k%g)cout<<"IM";
    cout<<"POSSIBLE"<<endl;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
    using namespace std;
    int main() {
        string week[7] = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};
        string s;
        cin>>s;
        for(int i=0;i<7;i++){
            if(s==week[i]){
                cout<<7-i;
            }
        }



        return 0;
    }



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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=1010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  int n;cin>>n;
  ll dp[n+10][5]={};
  for(int i=0;i<n;i++){
    ll a,b,c;cin>>a>>b>>c;
    dp[i+1][0]=max(dp[i+1][0],max(dp[i][1]+a,dp[i][2]+a));
    dp[i+1][1]=max(dp[i+1][1],max(dp[i][0]+b,dp[i][2]+b));
    dp[i+1][2]=max(dp[i+1][2],max(dp[i][1]+c,dp[i][0]+c));
  }
  cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<endl;
  return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
#define int long long
#define ld long double
//#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define gr vector<vector<pii>>
#define fi first
#define se second
using namespace std;
vvi g;
int n, m, k, c;
vi col;
void dfs(int v, int c)
{
    col[v] = c;
    for (int to : g[v])
        if (!col[to])
            dfs(to, c);
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    g.assign(n, vector<int>());
    col.resize(n);
    vi res(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        res[u]--;
        res[v]--;
    }
    int c = 1;
    for (int i = 0; i < n; i++)
        if (!col[i])
            dfs(i, c++);
    vi sz(n);
    for (int i = 0; i < n; i++)
        sz[col[i]]++;
    for (int i = 0; i < n; i++)
        res[i] += sz[col[i]] - 1;
    for (int i = 0; i < k; i++)
    {
        int u, v;
        cin >> u >> v;
        u--; v--;
        if (col[u] == col[v])
        {
            res[u]--;
            res[v]--;
        }
    }
    for (int i : res)
        cout << i << ' ';
    cout << endl;
    return 0;
}

Measured memory_bytes: 9856
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
signed main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (auto& x : a) cin >> x;
  sort(a.begin(), a.end());
  
  const int mod = 1e9 + 7;
  vector<int> fac(n + 1), inv(n + 1), finv(n + 1);
  fac[0] = fac[1] = 1;
  inv[1] = 1;
  finv[0] = finv[1] = 1;
  for (int i = 2; i <= n; i++) {
    fac[i] = 1LL * fac[i - 1] * i % mod;
    inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
    finv[i] = 1LL * finv[i - 1] * inv[i] % mod;
  }
  auto comb = [&](int n, int k) -> int {
    if (n < k || n < 0 || k < 0) return 0;
    return fac[n] * (1LL * finv[k] * finv[n - k] % mod) % mod;
  };
  
  int min_sum = 0;
  for (int i = 0; i < n; i++) {
    int t = 1LL * a[i] * comb(n - i - 1, k - 1) % mod;
    min_sum = (min_sum + t) % mod;
  }
  
  int max_sum = 0;
  for (int i = 0; i < n; i++) {
    int t = 1LL * a[i] * comb(i, k - 1) % mod;
    max_sum = (max_sum + t) % mod;
  }
  
  cout << (1LL * mod + max_sum - min_sum) % mod << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp make_pair
#define mkt make_tuple
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x > 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2) % mod;
}
/*--------Library Zone!--------*/

int n, m;
int a[2145], b[2145];
int dp[2145][2145];
signed main() {
	cin >> n >> m;
	rep(i, n)cin >> a[i];
	rep(i, m)cin >> b[i];
	rep(i, m + 1)dp[0][i] = 1;
	rep(i, n + 1)dp[i][0] = 1;
	rep(i, n) {
		rep(j, m) {
			if (a[i] == b[j]) {
				dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j];
			}
			else dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j];
			dp[i + 1][j + 1] += mod;
			dp[i + 1][j + 1] %= mod;
		}
	}
	cout << dp[n][m] << endl;
}

Measured memory_bytes: 35072
import sys
sys.setrecursionlimit(10**6)

n = int(input())
t = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int,input().split())
    t[a].append((b,i))
    t[b].append((a,i))
num = max([len(tmp) for tmp in t])
print(num)

ans = [-1]*(n-1)

def dfs(n, before, bcol):
    col = 1
    for i, j in t[n]:
        if i == before:
            continue
        if col == bcol:
            col += 1
        ans[j] = col
        dfs(i, n, col)
        col += 1

dfs(1, 0, -1)
for i in range(n-1):
    print(ans[i])

Measured memory_bytes: 80140