akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        cin = new Scanner();
        new Myon().calc();
        return 0;
    }

    static Scanner cin;

    void calc()
    {
        var X = cin.nextInt();
        var Y = cin.nextInt();
        var Z = cin.nextInt();
        var K = cin.nextInt();
        var A = cin.ArrayLong(X);
        var B = cin.ArrayLong(Y);
        var C = cin.ArrayLong(Z);
        var idx = 0;
        var AB = new long[X * Y];
        foreach(var a in A)
        {
            foreach(var b in B)
            {
                AB[idx] = a + b;
                idx++;
            }
        }

        Array.Sort(AB);
        Array.Reverse(AB);
        Array.Resize(ref AB, K);
        var cnt = Math.Min(C.Length, K);
        var ret = new long[AB.Length * cnt];
        idx = 0;
        for(var i = 0;i < cnt; i++)
        {
            foreach (var ab in AB)
            {
                ret[idx] = ab + C[i];
                idx++;
            }
        }
        Array.Sort(ret);
        Array.Reverse(ret);

        for(var i = 0;i < K; i++)
        {
            Console.WriteLine(ret[i]);
        }
        
    }


    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }
}

Measured memory_bytes: 44896
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double r3 = sqrt(3);

class Point {
  public:
  long double x, y;

  Point(long double x = 0, long double y = 0): x(x), y(y) {}

  Point operator + (Point p) {return Point(x + p.x, y + p.y);}
  Point operator - (Point p) {return Point(x - p.x, y - p.y);}
  Point operator * (long double a) {return Point(a * x, a * y);}
  Point operator / (long double a) {return Point(x / a, y / a);}

  long double abs() {return sqrt(norm());}
  long double norm() {return x * x + y * y;}
};

void print(Point p) {
  cout << setprecision(10) << p.x << " " << p.y << endl;
}

void koch(int n, Point p1, Point p2) {
  if (n == 0) return;
  Point s, t, u;
  s = (p1 * 2 + p2) / 3;
  t = (p1 + p2 * 2) / 3;
  u.x = (t.x - s.x) / 2 - (t.y - s.y) * r3 / 2 + s.x;
  u.y = (t.x - s.x) * r3 / 2 + (t.y - s.y) / 2 + s.y;

  koch(n-1, p1, s);
  print(s);
  koch(n-1, s, u);
  print(u);
  koch(n-1, u, t);
  print(t);
  koch(n-1, t, p2);
}

int main() {
  int n;
  cin >> n;
  Point p1, p2;
  p1.x = 0;
  p1.y = 0;
  p2.x = 100;
  p2.y = 0;
  print(p1);
  koch(n, p1, p2);
  print(p2);

  
  return 0;
}


Measured memory_bytes: 3208
#!/usr/bin/env python3

def main():
    n, k = map(int, input().split())
    used = set()
    for _ in range(k):
        d = int(input())
        a = list(map(int, input().split()))
        used |= set(a)
    ans = n - len(used)
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9180
import java.util.*;
class Main{
	public static void main(String args[]){
		int table[][]=new int[100][100];
		int dp[][]=new int[100][100];
		Scanner s=new Scanner(System.in);
		int count=0;
		for(int i=0;i<100;i++)
			for(int j=0;j<100;j++)
				table[i][j]=dp[i][j]=0;
		
		while(s.hasNext()){
			String str=s.next();
			String[] dat=str.split(",");
			for(int i=0;i<dat.length;i++){
				table[count][i]=Integer.parseInt(dat[i]);
			}
			count++;
		}
		dp[0][0]=table[0][0];
		for(int i=1;i<count;i++){
			for(int j=0;j<count;j++){
				if(i<count/2){
					if(j==0)dp[i][j]=dp[i-1][j]+table[i][j];
					else dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1])+table[i][j];
				}else{
					dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j+1])+table[i][j];
				}
			}
		}
		System.out.println(dp[count-1][0]);
	}
}

Measured memory_bytes: 12000
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
#define N 1000015
const int p=1e9+7;
int n,m,dp[3002][3002],mx[N],s[N];
char ch[N];
inline int ksm(int d,int tk){int ret=1;while(tk){if(tk&1)ret=1ll*ret*d%p;d=1ll*d*d%p;tk>>=1;}return ret;}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",ch+1);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+ch[i]-'0',mx[i]=i;s[n+1]=s[n];
    for(int i=1;i<=m;i++)
    {
    	int l,r;scanf("%d%d",&l,&r);
    	mx[l]=max(mx[l],r);
	}
	for(int i=1;i<=n;i++)mx[i]=max(mx[i],mx[i-1]);mx[n+1]=mx[n];
	dp[0][s[mx[1]]]=1;
	for(int i=0;i<n;i++)for(int j=0;j<=n;j++)
	{
		if(j)(dp[i+1][j+s[mx[i+2]]-s[mx[i+1]]-1]+=dp[i][j])%=p;
		if(mx[i+1]-i-j>0)(dp[i+1][j+s[mx[i+2]]-s[mx[i+1]]]+=dp[i][j])%=p;
	}
	printf("%d\n",dp[n][0]);
}


Measured memory_bytes: 38144
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i ++)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;
const int MAXV = 100005;

int main() {
    int N; scanf("%d",&N);
    vector<P> item(N);
    rep(i,N) scanf("%d %d",&item[i].first,&item[i].second);
    
    int K = (1<<10) - 1;
    vector<vector<int>> dp(K + 1,vector<int>(MAXV,0));
    for (int i = 1;i <= K;i ++) {
        int w = item[i - 1].second,v = item[i - 1].first;
        rep(j,MAXV) {
            if (j >= w) dp[i][j] = max(dp[i >> 1][j],dp[i >> 1][j - w] + v);
            else dp[i][j] = dp[i >> 1][j];
        }
    }
    int Q; scanf("%d",&Q);
    rep(_,Q) {
        int V,L; scanf("%d %d",&V,&L);
        vector<P> items;
        while (V > K) {
            items.push_back(item[V - 1]);
            V >>= 1;
        }
        vector<P> choice;
        choice.push_back(P(0,0));
        for (P p1: items) {
            for (P p2:choice) {
                choice.push_back(P(p1.first + p2.first,p1.second + p2.second));
            }
        }
        int ans = 0;
        for (P p: choice) {
            int w = p.second,v = p.first;
            if (L - w < 0) continue;
            ans = max(ans,dp[V][L - w] + v);
        }
        printf("%d\n",ans);
    }
    return 0;
}

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

int main() {
    int n; cin >> n;
    string s; cin >> s;
    int q; cin >> q;
    auto solve = [&](int k) {
        long long dmc = 0, dm = 0;
        queue<int> ds;
        for (int i = 0, m = 0; i < n; i++) {
            if (s[i] == 'D') ds.emplace(m);
            if (s[i] == 'M') dm += ds.size(), m++;
            if (s[i] == 'C') dmc += dm;
            if (i >= k - 1 && s[i - k + 1] == 'D') {
                dm -= m - ds.front(), ds.pop();
            }
        }
        return dmc;
    };
    while (q--) {
        int k; cin >> k;
        cout << solve(k) << endl;
    }
    return 0;
}


Measured memory_bytes: 5344
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double g = 9.8, EPS = 1e-10;
int N, V, X, Y;
const int maxn = 55;
int L[maxn], B[maxn], R[maxn], T[maxn];
double calc(double vy, double t)
{
    return vy * t - g * t * t / 2;
}
int cmp(double lb, double ub, double a)
{
    if(a - lb < EPS){
        return -1;
    }
    else{
        if(a - ub > -EPS){
            return 1;
        }
        else{
            return 0;
        }
    }
}
bool check(double qx, double qy)
{
    double a = g * g / 4, b = g * qy - V * V, c = qx * qx + qy * qy;
    double D = b * b - 4 * a * c;
    if(D > -EPS && D < 0) D = 0;
    if(D < 0) return false;
    for(int d = -1; d <= 1; d += 2){
        double t2 = (-b + d * sqrt(D)) / (2 * a);
        if(t2 <= 0) continue;
        double t = sqrt(t2);
        double vx = qx / t, vy = (qy + g * t * t / 2) / t;
        double yt = calc(vy, X / vx);
        if(yt < Y - EPS) continue;
        bool ok = true;
        for(int i = 0; i < N; i++){
            if(L[i] >= X) continue;
            if(R[i] >= X && Y <= T[i] && B[i] <= yt) ok = false;
            int yL = cmp(B[i], T[i], calc(vy, L[i] / vx));
            int yR = cmp(B[i], T[i], calc(vy, R[i] / vx));
            int xH = cmp(L[i], R[i], vx * (vy / g));
            int yH = cmp(B[i], T[i], calc(vy, vy / g));
            if(xH == 0 && yH >= 0 && yL < 0) ok = false;
            if(yL * yR <= 0) ok = false;
        }
        if(ok) return true;
    }
    return false;
}
void solve()
{
    for(int i = 0; i < N; i++){
        R[i] = min(R[i], X);
    }
    bool ok = check(X, Y);
    for(int i = 0; i < N; i++){
        ok |= check(L[i], T[i]);
        ok |= check(R[i], T[i]);
    }
    puts(ok ? "Yes" : "No");
}
int main()
{
    scanf("%d%d%d%d", &N, &V, &X, &Y);
    for(int i = 0; i < N; i++){
        scanf("%d%d%d%d", &L[i], &B[i], &R[i], &T[i]);
    }
    solve();
    return 0;
}



Measured memory_bytes: 2688
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (a); i < n; i++)
#define print(x) cout << x << endl;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;

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

    int s[M];
    int c[M];
    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--;
        s[i] = a;
        c[i] = b;

        if (N > 1 && a == 0 && c[i] == 0) {
            cout << -1 << endl;
            return 0;
        }
    }

    int S[N] = {};
    int change[N] = {};

    rep(i, 0, M) {
        if (change[s[i]] && S[s[i]] != c[i]) {
            cout << -1 << endl;
            return 0;
        }
        change[s[i]] = 1;
        S[s[i]] = c[i];
    }

    rep(i, 0, N) {
        if (N > 1 && i == 0 && S[i] == 0) {
            cout << 1;
        }
        else {
            cout << S[i];
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#from math import gcd

from math import factorial as f

from math import ceil,floor,sqrt
import math

import bisect
import re
import heapq


from copy import deepcopy
import itertools
from itertools import permutations

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


yes = "Yes"
no = "No"


def main():
    a,b,h,m = mi()
    h = h*30+m/2
    m = m*6
    c = math.cos(math.radians(abs(h-m)))
    ans = (a**2+b**2-2*b*a*c)**0.5
    print(ans)









main()




Measured memory_bytes: 10344
-- 1_4_C
main = do cs <- getLine
          let [a, op, b] = words cs
          case op of
            "?" -> return()
            op  -> do print $ calc a op b
                      main

calc :: String -> String -> String -> Int
calc a op b
    | op == "+" = (read a::Int) + (read b::Int)
    | op == "-" = (read a::Int) - (read b::Int)
    | op == "*" = (read a::Int) * (read b::Int)
    | op == "/" = (read a::Int) `div` (read b::Int)

Measured memory_bytes: 3872
import sys

n, m, *ab = map(int, sys.stdin.read().split())
graph = [set() for _ in range(n + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].add(b); graph[b].add(a)

def main():
    ans = 'IMPOSSIBLE'
    for x in graph[1]:
        if n in graph[x]:
            ans = 'POSSIBLE'
            break
    print(ans)

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 76048
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define REPR(i, m, n) for (int i = (int)(m); i >= (int)(n); i--)
#define all(v) v.begin(), v.end()
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
typedef long long ll;

int n;
int q;
int a[21];
int dp[21][2100];

int rec(int i, int j){
  if(dp[i][j] != -1) return dp[i][j];

  if(j == 0) return 1;
  if(i == 0) return 0;

  int res = 0;
  if(j >= a[i]) res |= rec(i-1, j-a[i]);
  res |= rec(i-1, j);
  return dp[i][j] = res;
}

int main(){
  cin >> n;
  a[0] = 0;
  REP(i, 1, n) cin >> a[i];

  cin >> q;
  memset(dp, -1, sizeof(dp));
  rep(i, q){
    int m; cin >> m;
    cout << (rec(n, m) ? "yes" : "no") << endl;
  }

  return 0;
}





Measured memory_bytes: 3260
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		FastScanner sc=new FastScanner();
		double R=sc.nextDouble();
		System.out.println(2*R*Math.PI);
	}
	
	void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}
}




class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 33176
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<deque>
#include<math.h>
using namespace std;
#define ll long long
int main(){
    string S;
    ll N,i,j;
    cin >> S;
    N=S.size();
    ll pre[2019],now[2019];
        for(j=0;j<2019;j++){
            pre[j]=0;
            now[j]=0;
        }
    ll ans=0;
    ll t;
    for(i=1;i<=N;i++){
        t=S[i-1]-'0';
        for(j=0;j<2019;j++){
            now[(j*10+t)%2019]=pre[j];
        }
        now[t]+=1;
        ans+=now[0];
        for(j=0;j<2019;j++){
            pre[j]=now[j];
        }
    }
    cout << ans;
    return 0;
}


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

using namespace std;

int main(void){
    char a=0;
    char b=0;

    cin >> a >> b;

    if(a=='H')cout << b << endl;
    if(a=='D'){
        if(b=='H')cout << "D" << endl;
        else cout << "H" << 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;
#define chmax(x,y) x = max(x,y)
typedef long long ll;

int main(){
  int n,t; cin>>n>>t;
  vector<pair<int,int>> p(n);
  int dp[200005];
  rep(i,n) cin>>p[i].first>>p[i].second;
  sort(p.begin(),p.end());
  int ans = 0;
  rep(i,n){
    int a = p[i].first;
    int b = p[i].second;
    for(int j=t-1;j>=0;j--){
      chmax(ans,dp[j]+b);
      chmax(dp[j+a],dp[j]+b);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,v=0;cin>>n;
  lvector A(n),S(n,0);rep(i,n) cin>>A[i];
  sort(ALL(A));
  S[0]+=A[0];rep(i,n-1) S[i+1]=S[i]+A[i+1];
  rep(i,n-1) if(2*S[i]<A[i+1]) v=i+1;
  print(n-v);
  return 0;
}

Measured memory_bytes: 4752
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int MaxN = 1e5;

int main()
{
	long long N,sum,ans,biu,piu,vis;
	while(~scanf("%lld",&N))
	{
		if(N==0||N==1) 
		{
			printf("%lld\n",N);
			continue;
		}
		sum = N; biu = 0; ans = 0; vis = 0;
		while(sum)
		{
			biu++;
			piu = sum;
			sum /= 10;
			if(piu%10 != 9&& sum != 0) vis = 1;
		}
		ans += piu-1;
		for(int i = 1;i < biu;i++) ans += 9;
		if(vis == 0) ans++; 
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int x; cin>>x;
	if(x>=30) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3648
public class Main {
  private static void solve() {
    int n = ni();

    int[][] ret = new int[n][n];
    dfs(0, n, 1, ret);

    for (int i = 0; i < n - 1; i++) {
      StringBuilder sb = new StringBuilder();
      for (int j = i + 1; j < n; j++) {
        sb.append(ret[i][j] + " ");
      }
      out.println(sb.substring(0, sb.length() - 1));
    }
  }

  private static void dfs(int left, int right, int level, int[][] ret) {
    if (left + 1 >= right)
      return;

    int center = (left + right) / 2;

    for (int i = left; i < center; i++) {
      for (int j = center; j < right; j++) {
        ret[i][j] = level;
        ret[j][j] = level;
      }
    }

    dfs(left, center, level + 1, ret);
    dfs(center, right, level + 1, ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

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

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 39256
//
// Created on 2020/08/29.
//


#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;



int main() {
    int n;
    int m;
    cin>>n>>m;
    vector<int>X(m);
    for (int i = 0; i < m; ++i) {
        cin>>X[i];
    }
    if(n >= m){
        cout<<0<<endl;
        return 0;
    }
    sort(all(X));
    priority_queue<pair<int,int>>p_q;//abs,abs = abs(i + 1 -i)のi
    for (int i = 0; i < m - 1; ++i) {
        int d = abs(X[i+1] - X[i]);
        p_q.push({d,i});
    }

    ll ans = X[m-1] - X[0];
    for (int j = 0; j < n - 1; ++j) {
        int index = p_q.top().second;
        p_q.pop();
        ans -= abs(X[index+1] - X[index]);
    }

    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4664
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))

int lcm(int, int);
map<int,int> GetPrimeFactors(int);
bool IsPrime(int);
int Factorial(int);
int npr (int, int);
int ncr (int, int);


const int MAX = 5100000;

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

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

ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

/***** MAIN *****/
void Main() {
  int x, y;
  cin >> x >> y;
  if((x+y) % 3 != 0) {
    cout << 0 << endl;
    return;
  }
  if(2*x < y || 2*y < x) {
    cout << 0 << endl;
    return;
  }
  int n = (2*y - x) / 3;
  int m = (2*x - y) / 3;

  COMinit();
  cout << COM(m+n, n);
  
  cout << "\n";
  return;
}
/***** MAIN *****/

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

int lcm(int a, int b) { return a / __gcd(a,b) * b;}

map<int,int> GetPrimeFactors(int n) {
  map<int,int> mp;
  // dived by 2, 3, 5, ...
  for(int i=2; i*i<=n; i+=2) {
    if(i==4) i = 3;
    while(n%i == 0) {
      ++mp[i];
      n /= i;
    }
  }
  if(n!=1) ++mp[n];

  return mp;
}

bool IsPrime(int a) {
  if(a <= 1) return false;
  if(a == 2) return true;
  if(a%2 == 0) return false;
  for(int i = 3; i*i <= a; i+=2) {
    if(a%i==0) return false;
  }
  return true;
}

int Factorial(int n){
  int ans = 1;
  while(n > 1){
    ans *= n;
    --n;
  }
  return ans;
}

int npr(int n, int r) {
  return Factorial(n)/Factorial(n-r);
}

int ncr (int n, int r){
  return npr(n,r)/Factorial(r);
}


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

using namespace std;

#define ll long long
#define ini(arr, val) memset(arr, (val), sizeof(arr))
#define loop(i,n)  for(ll i=0; i<n; i++)
#define loop1(i,n)  for(ll i=1; i<=n; i++)

#define all(a)      (a).begin(),(a).end()
#define exist(s,e)  (s.find(e)!=s.end())
#define dbg(x)  cout << #x << " = " << x << endl
#define pt(x) cout<<x<<"\n"
#define pts(x) cout<<x<<" "

#define mp make_pair
#define pb push_back
#define F first
#define S second


#define inf (int)1e9
#define infll 1e18
#define eps 1e-9
#define PI 3.1415926535897932384626433832795
#define mod 1000000007


#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test   int t; cin>>t; while(t--)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef set<int> si;

typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pll> vpll;
typedef vector<vl> vvl;
typedef map<ll,ll> mll;
typedef set<ll> sl;


int dirx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int diry[] = { -1, 0, 1, -1, 1, -1, 0, 1 };



//===========================DEBUG======================//
#define XOX 1
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...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

//================================================================//



//////////////////////////////////////////////////////////////////////////////////////////
//                      main starts
//////////////////////////////////////////////////////////////////////////////////////////
int const lmt=1e5+5;


int main(){
   
    ll n,m;
    cin>>n>>m;
    ll a[m],sum=0;
    loop(i,m){
        cin>>a[i];
        sum=sum+a[i];

    }
    if(n>=sum) pt(n-sum);
    else pt("-1");
    
}


/*



*/





Measured memory_bytes: 3668
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forab(i, a, b) for(int i=(a);i<(b);++i)
#define foreach(i, n) for (__typeof(n.begin()) i = n.begin(); i != n.end(); ++i)
#define sqr(x) ((x)*(x))
#define clr(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)a.size())
#define inf 0x3f3f3f3f
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
const double eps = 1e-8;
int dcmp(double x) { if (x < -eps) return -1; else return x > eps;}
#define se(x) cout<<#x<<" = "<<x<<endl
	
ll solve(int n, int k) {
	ll t = n / k;
	ll ret = t * t * t;
	if (k % 2 == 0 && n >= k/2) {
		t = (n - k/2) / k + 1;
		ret += t * t * t;
	}
	return ret;
}


ll solve2(int n, int k) {
	int cnt = 0;
	forab(a, 1, n+1) {
		forab(b, 1, n+1) {
			forab(c, 1, n+1) {
				if ((a + b) % k != 0) {
					continue;
				}
				if ((b + c) % k != 0) {
					continue;
				}
				if ((c + a) % k != 0) {
					continue;
				}
				cnt++;
			}
		}
	}
	return cnt;
}

int main(int argc, char *argv[]) {
	int n, k;
	while (scanf("%d%d", &n, &k) != EOF) {
		ll ret = solve(n, k);
//		printf("%lld %lld\n", ret, solve2(n, k));
		printf("%lld\n", ret);
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,n;
  cin >> h >> n;
  vector<pair<int,int> >p(n);
  int i,j;
  for(i=0;i<n;i++){
    cin >> p[i].first >> p[i].second;
  }
  int inf = 1<<30;
  vector<int>dp(h+20000,inf);
  dp[0]=0;
  for(i=0;i<=h;i++){
    for(j=0;j<p.size();j++){
      if(dp[i]!=inf){
        dp[i+p[j].first] = min(dp[i+p[j].first],dp[i]+p[j].second);
      }
    }
  }
  int minn = dp[h];
  for(i=0;i<20000;i++){
    if(minn > dp[h+i])minn=dp[h+i];
  }
  cout << minn << endl;
}


Measured memory_bytes: 384
n = int(input())
h = list(map(int, input().split()))
dp = [float('inf')] * n
dp[0] = 0
dp[1] = abs(h[1]- h[0])

for i in range(2, n):
    c1 = dp[i-1] + abs(h[i] - h[i-1])
    c2 = dp[i-2] + abs(h[i] - h[i-2])
    dp[i] = c1 if c1 < c2 else c2
print(dp[n-1])

Measured memory_bytes: 20640
n, k, l = map(int,input().split())
P = [list(map(int,input().split())) for i in range(k)]
R = [list(map(int,input().split())) for i in range(l)]

PM = [[] for i in range(n+1)]
RM = [[] for i in range(n+1)]

for i in range(k):
    PM[P[i][0]].append(P[i][1])
    PM[P[i][1]].append(P[i][0])
for i in range(l):
    RM[R[i][0]].append(R[i][1])
    RM[R[i][1]].append(R[i][0])

C = [[0] * 2 for i in range(n+1)]

VP = [0] * (n+1)
clr = 0
for i in range(1, n+1):
    if VP[i] == 0:
        VP[i] = 1
        clr += 1
        Q = [i]
        st = 0
        while st < len(Q):
            j = Q[st]
            C[j][0] = clr
            for item in PM[j]:
                if VP[item] == 0:
                    VP[item] = 1
                    Q.append(item)
            st += 1

VR = [0] * (n+1)
clr = 0
for i in range(1, n+1):
    if VR[i] == 0:
        VR[i] = 1
        clr += 1
        Q = [i]
        st = 0
        while st < len(Q):
            j = Q[st]
            C[j][1] = clr
            for item in RM[j]:
                if VR[item] == 0:
                    VR[item] = 1
                    Q.append(item)
            st += 1

# print(C)

D = {}
for i in range(1, n+1):
    try:
        D[(C[i][0], C[i][1])] += 1
    except:
        D[(C[i][0], C[i][1])] = 1

ANS = []

for i in range(1, n+1):
    ANS.append(str(D[(C[i][0], C[i][1])]))

print(" ".join(ANS))



Measured memory_bytes: 142544
H,W = map(int,input().split())
h,w = H//2, W//2
h1, w1 = h, w
if H & 1:
    h += 1

if W & 1:
    w += 1

if H == 1:
    print(1)
elif W == 1:
    print(1)
else:
    print(w * h + w1 * h1)
    

Measured memory_bytes: 38256
#include <stdio.h>
#include <algorithm>
#include <tuple>
using namespace std;
int N, M; tuple<int, int, int> D[20000]; bool infected[20000];
int main() {
	while (true) {
		scanf("%d%d", &N, &M);
		if (N == 0 && M == 0) break;
		infected[0] = true;
		for (int i = 1; i < N; i++) infected[i] = false;
		for (int i = 0; i < M; i++) scanf("%d%d%d", &get<0>(D[i]), &get<1>(D[i]), &get<2>(D[i]));
		sort(D, D + M);
		int ret = 1;
		for (int i = 0; i < M; i++) {
			if (infected[--get<1>(D[i])] && !infected[--get<2>(D[i])]) {
				infected[get<2>(D[i])] = true; ret++;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> A1(N), A2(N);
  for (int i = 0; i < N; i++) cin >> A1.at(i);
  for (int i = 0; i < N; i++) cin >> A2.at(i);
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int tmp = 0;
    for (int j = 0; j <= i; j++) tmp += A1.at(j);
    for (int k = i; k < N; k++) tmp += A2.at(k);
    ans = max(ans, tmp);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn ok(hs: &[i64], n: i64, a: i64, b: i64) -> bool {
    let d = a - b;
    let mut cnt = 0;
    for i in 0..hs.len() {
        let r = hs[i] - b*n;
        cnt += max(0, (r + d - 1) / d);
    }
    cnt <= n
}

fn main() {
    input!{
      n: usize,
      a: i64,
      b: i64,
      hs: [i64; n],
    }

    let mut l = 0i64;
    let mut r = *hs.iter().max().unwrap() / b + 1;

    while r-l > 1 {
        let mid = (r+l)/2;
        if ok(&hs, mid, a, b) {
            r = mid;
        } else {
            l = mid;
        }
    }
    println!("{}", r);
}


Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Prob0003
{
    class Program
    {
        const char splitBy = ' ';

        static void Main(string[] args)
        {
            int N = Convert.ToInt32(System.Console.ReadLine());
            for (int i = 0; i < N; i++)
            {
                int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), e => int.Parse(e));
                var sorted = input.OrderBy(e => e).ToArray();
                if (Math.Pow(sorted[0], 2) + Math.Pow(sorted[1], 2) == Math.Pow(sorted[2], 2))
                    Console.WriteLine("YES");
                else
                    Console.WriteLine("NO");
            }
        }
    }
}

Measured memory_bytes: 6268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

//-----------------------------------------------

//------------------------------------------------
int main(){
  int n,x,d,ans;
  int L[101];
  cin>>n>>x;
  ans=1;
  d=0;
  rep(i,0,n) cin>>L[i];
  rep(i,0,n){
    d=d+L[i];
    if(d<=x) ans+=1;
  }
cout<<ans<<endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#define INF 100000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cstdio>

using namespace std;

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

static const double EPS = 1e-8;

const int tx[] = {0,1,0,-1};
const int ty[] = {-1,0,1,0};

struct Rect {
  int lx,ly;
  int rx,ry;
  int id;
  Rect(int rx,int ry,int lx,int ly,int id) :
    rx(rx),ry(ry),lx(lx),ly(ly),id(id) {}
  Rect() {}

  Rect(const Rect& r) {
    lx = r.lx;
    ly = r.ly;
    rx = r.rx;
    ry = r.ry;
    id = r.id;
  }

  bool operator>(const Rect& r) const {
    if(rx == r.rx){
      return ry > r.ry;
    }
    return rx > r.rx;
  }
};

bool used[10];
int order[10];
int idx;
int total_pages;
void dfs(int border_x,int lower_bound,const vector<Rect>& pages){
  for(int round = 0; round < total_pages; round++){
    priority_queue<Rect,vector<Rect>,greater<Rect> > candidates;
    
    for(int i = 0; i < total_pages; i++){
      if(used[i]) continue;
      if(lower_bound < pages[i].ly) continue;
      if(pages[i].lx > border_x) continue;
      // if(pages[i].rx < last_rx) continue;
      candidates.push(pages[i]);
    }
    
    if(candidates.empty()) return;
    
    Rect last = candidates.top();
    candidates.pop();
    
    // while(!candidates.empty()) candidates.pop();
    // printf("border:%d id:%d lower:%d\n",border_x,last.id,lower_bound);
    order[last.id] = idx++;
    used[last.id] = true;
    
    // last_rx = last.rx;

    int next_lower_bound = last.ly;
    int next_border_x = 1000;
    // cout << "last:" << last.id<< endl;
    for(int i = 0; i < total_pages; i++){
      if(pages[i].ly > last.ly && pages[i].ry < last.ly
         && pages[i].rx >= last.lx){
        next_border_x = min(pages[i].rx,next_border_x);
      }
    }
    // printf("next:border:%d id:%d lower:%d\n",border_x,last.id,lower_bound);
    dfs(next_border_x,next_lower_bound,pages);
  }
}

int main(){
  bool is_first = true;
  while(~scanf("%d",&total_pages)){
    if(total_pages == 0) break;
    vector<Rect> pages;
    for(int i = 0; i < total_pages; i++){
      int lx,ly;
      int rx,ry;
      scanf("%d %d %d %d",&rx,&ry,&lx,&ly);
      pages.push_back(Rect(rx,ry,lx,ly,i));
    }


    memset(used,false,sizeof(used));
    memset(order,0,sizeof(order));
    idx = 1;
    dfs(1000,1000,pages);

    if(!is_first) {
      printf("\n");
    }
    for(int i = 0;i<total_pages;i++){
      printf("%d\n",order[i]);
    }
    is_first = false;
  }
}

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

// --------------------------------------------------------------------------------
#define fast_IO	ios_base::sync_with_stio(false),cin.tie(NULL),cout.tie(NULL);
#define ll long long 
#define mset(arr,val) memset(arr,val,sizeof(arr))
#define deb(name,value) cout <<"->>  "<<name<< "= " <<value<<" "
#define frepi(a,b,k) for(int i=a;i<=b;i+=k)
#define frepj(a,b,k) for(int j=a;j<=b;j+=k)
// --------------------------------------------------------------------------------


void solve()
{
    string s1,s2;cin>>s1>>s2;
    for(int i=0;i<s1.size();++i)
    {
    	if(s1[i]!=s2[i])
    	{
    		cout<<"No\n";
    		return;
    	}
    }
    cout<<"Yes\n";
}

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

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

long long r[10],d[250][250];

int main()
{
	long long n,m,R,i,j,k,a,b,c,ans=0,tmp;
	scanf("%lld%lld%lld",&n,&m,&R);
	for(i=0;i<R;i++)
		scanf("%lld",&r[i]);
	while(m--)
	{
		scanf("%lld%lld%lld",&a,&b,&c);
		if(d[a][b]==0) d[a][b]=c;
		else d[a][b]=min(d[b][a],c);
		if(d[b][a]==0) d[b][a]=c;
		else d[b][a]=min(d[b][a],c);
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j) d[i][i]=0;
			else if(!d[i][j]) d[i][j]=30000000;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	for(sort(r,r+R);next_permutation(r,r+R);)
	{
		for(i=1,k=r[0],tmp=0;i<R;i++)
			tmp+=d[k][r[i]],k=r[i];
		if(ans==0 || tmp<ans) ans=tmp;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXD = 1e5 + 5;
const int mod = 1e9 + 7;

inline void add_mod(int &a,int b){ a+=b; if(a>=mod) a-=mod;}

bool isnp[MAXD],ok[MAXD];
int p[MAXD],q[MAXD],pcnt=0;
int cnt[MAXD];
void sieve(int n)
{
	isnp[0]=isnp[1]=1;
	ok[1]=1; cnt[1]=0;
	for(int i=2; i<=n; ++i)
	{
		if(!isnp[i]) p[++pcnt]=q[i]=i, ok[i]=1, cnt[i]=1;
		for(int j=1; j<=pcnt && (ll)i*p[j]<=n; ++j)
		{
			int x = i*p[j];
			isnp[x]=1;
			q[x]=p[j];
			if(!(i%p[j])) break;
			if(ok[i]) ok[x]=1, cnt[x]=cnt[i]+1;
		}
	}
}

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

int n;
int f[MAXD];

int gao(int x)
{
	if(~f[x]) return f[x];
	f[x]=0;
	for(int i=1; i<=x; ++i)
	{
		if(!ok[i]) continue;
		if(cnt[i]&1)
		{
			f[x] -= pw(x/i,n);
			if(f[x]<0) f[x] += mod;
		}
		else add_mod(f[x], pw(x/i,n));
	}
	return f[x];
}

int main(void)
{
	memset(f,-1,sizeof(f));
	sieve(1e5);
	
	int d;
	scanf("%d%d",&n,&d);
	
	int ans = 0;
	for(int i=1; i<=d; ++i)
		add_mod(ans, (ll)gao(d/i)*i %mod);
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 5236
#include<iostream>
#include<map>

#define ll long long

using namespace std;

int main(){
    int n, a, b;
    ll k;
    cin >> n >> k;

    map<int, ll> m;
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        if(m.find(a) == m.end()){
            m[a] = b;
        }else{
            m[a] += b;
        }
    }

    map<int, ll> :: iterator ite = m.begin();
    while(ite != m.end()){
        if(ite -> second < k){
            k -= ite -> second;
        }else{
            cout << ite -> first << endl;
            break;
        }
        ite++;
    }
}

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

using namespace std;

typedef long long lint;
const int N = 3e3+100;
int dp[N][N];
string s, t;
vector<char> ans;

int main(){
#ifdef LOCAL
	freopen("input", "r", stdin);
#endif

	cin >> s >> t;

	int n = (int)s.size(), m = (int)t.size();

	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= m; j++){
			if (i == 0 || j == 0){
				dp[i][j] = 0;
			}
			else if (s[i - 1] == t[j - 1]){
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}

	int i = n, j = m;

	while (i > 0 && j > 0){
		if (s[i - 1] == t[j - 1]){
			ans.push_back(s[i - 1]);
			i--; j--;
		} else if (dp[i - 1][j] > dp[i][j - 1]){
			i--;
		} else {
			j--;
		}
	}

	reverse(ans.begin(), ans.end());

	for (int i = 0; i < (int)ans.size(); i++){
		printf("%c", ans[i]);
	}

	printf("\n");

	return 0; 
}

Measured memory_bytes: 39996
//実装が重そうな問題はある程度考えてから書く
//初期化を忘れずに（特に二分探索とか）
//コーナーケースを考えて（特に場合分けとか）
//不可解すぎるバグは配列外参照（配列の長さ）を検討
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b-1,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB emplace_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define int long long
#define zero 0LL
#define pb PB
using namespace std;
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef LL ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<ppr, Vppr ,greater<ppr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
int dx[] = { 0,1,0,-1,1,1,-1,-1,0 }, dy[] = { 1,0,-1,0,1,-1,1,-1,0 };
const int SIZE1 =3e5 + 1000;
const int SIZE2 = 2010;
const int SIZE3 = 22;
const int SIZE = SIZE1;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
ut N, M, K, X, L, Y,H,W,Q,D;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE], nums[SIZE], maps[SIZE2][SIZE2], answer = zero;
//LL A[SIZE], B[SIZE];
bool nable[SIZE2][SIZE2];
LL cost[SIZE2][SIZE2];
map<LL, LL> mp;
LL solve() {
	LL n[2];
	cin >> n[0] >> n[1];
	VI v[2] = { VI(n[0]),VI(n[1]) };
	VI ans, ansb;
	REP(k,2)
	
REP(i, n[k]) {
		cin >> v[k][i];
		mp[v[k][i]] = mp[v[k][i]] + 1;
		if (mp[v[k][i]] == 1) {
			ansb.pb(v[k][i]);
		}
		else {
			ans.pb(v[k][i]);
		}
	}
	sort(ALL(ans));
	sort(ALL(ansb));
	cout << ans.size() << " " << ansb.size() << endl;
	REP(i, ans.size()) {
		cout << ans[i] << endl;
	}
	REP(i, ansb.size()) {
		cout << ansb[i] << endl;
	}
	return 0;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	solve();
	//	cin >> N;
	return 0;
}


Measured memory_bytes: 27092
use std::io::*;
use std::str::FromStr;
use std::cmp::max;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let s: u64 = read();
    let w: u64 = read();
    if s <= w {
        println!("unsafe");
    } else {
        println!("safe");
    }
}


Measured memory_bytes: 2172