akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public static void main(String[] args) throws IOException {
        try (PrintWriter writer = new PrintWriter(System.out); InputReader reader = new InputReader(System.in)) {
            int[] inputInts = reader.readIntsSplitByDelimiter(" ");
            int numberOfCandles = inputInts[0];
            int numberOfRit = inputInts[1];
            int[] candleIndices = reader.readIntsSplitByDelimiter(" ");

            int minCost = Math.abs(candleIndices[0]) + Math.abs(candleIndices[numberOfCandles - 1] - candleIndices[0]);
            for (int leftIndex = 0; leftIndex < numberOfCandles - numberOfRit + 1; leftIndex++) {
                int rightIndex = leftIndex + numberOfRit - 1;

                int leftToRight = Math.abs(candleIndices[leftIndex]) + Math.abs(candleIndices[rightIndex] - candleIndices[leftIndex]);
                int rightToLeft = Math.abs(candleIndices[rightIndex]) + Math.abs(candleIndices[leftIndex] - candleIndices[rightIndex]);
                int cost = Math.min(leftToRight, rightToLeft);
                minCost = Math.min(cost, minCost);
            }

            System.out.println(minCost);
        }
    }
}

class InputReader implements Closeable, AutoCloseable {
    private final BufferedReader br;
 
    InputReader(InputStream inputStream) {
        this.br = new BufferedReader(new InputStreamReader(inputStream));
    }

    String readLine() throws IOException {
        return this.br.readLine();
    }
 
    int readInt() throws IOException {
        return Integer.parseInt(this.readLine());
    }
 
    long readLong() throws IOException {
        return Long.parseLong(this.readLine());
    }
 
    String[] readStringsSplitByDelimiter(String delimiter) throws IOException {
        return this.readLine().split(delimiter);
    }
 
    int[] readIntsSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.readStringsSplitByDelimiter(delimiter);
 
        int stringsLength = strings.length;
        int[] ints = new int[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            ints[i] = Integer.parseInt(strings[i]);
        }
 
        return ints;
    }
 
    long[] readLongsSplitByDelimiter(String delimiter) throws IOException {
        String[] strings = this.readStringsSplitByDelimiter(delimiter);
 
        int stringsLength = strings.length;
        long[] longs = new long[stringsLength];
        for (int i = 0; i < stringsLength; i++) {
            longs[i] = Long.parseLong(strings[i]);
        }
 
        return longs;
    }
 
    @Override
    public void close() throws IOException {
        br.close();
    }
}


Measured memory_bytes: 38996
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;

int main()
{
	int a, n, cnt[2] = { };
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		cnt[a % 2]++;
	}
	if (cnt[1] % 2) {
		cout << "NO" << endl;
	}
	else {
		cout << "YES" << endl;
	}
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
const int mod= 998244353;
ll tree[maxn<<2];
void build(int o,int l,int r){
    tree[o]=0;
    if(l==r){
        return ;
    }
    else {
        int mid=l+r>>1;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        tree[o]=max(tree[o<<1],tree[o<<1|1]);
    }
}
ll query(int o,int l,int r,int x,int y){
    if(x<=l&&y>=r){
        return tree[o];
    }
    int mid=l+r>>1;
    ll ans=0;
    if(mid>=x)ans=max(ans,query(o<<1,l,mid,x,y));
    if(mid<y)ans=max(ans,query(o<<1|1,mid+1,r,x,y));
    return ans;
}
void update(int o,int l,int r,int p,ll v){
    if(l==r){
        tree[o]=v;
    }
    else {
        int mid=l+r>>1;
        if(mid>=p)update(o<<1,l,mid,p,v);
        else if(mid<p)update(o<<1|1,mid+1,r,p,v);
        tree[o]=max(tree[o<<1],tree[o<<1|1]);   
    }
}
pair<ll ,ll>a[maxn];
int L[maxn];
ll b[maxn];
ll dp[maxn];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].first,&a[i].second);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)b[i]=a[i].first;
    build(1,1,n);
    for(int i=n;i>=1;i--){
        int tmp=upper_bound(b+1,b+1+n,a[i].first+a[i].second-1)-b;
        if(tmp==i+1)L[i]=i;
        else L[i]=query(1,1,n,i+1,tmp-1);
        update(1,1,n,i,L[i]);
    }
//  for(int i=1;i<=n;i++)cout<<L[i]<<" ";cout<<endl;
    dp[n+1]=1;
    for(int i=n;i>=1;i--){
        dp[i]=dp[i+1]+dp[L[i]+1];
        dp[i]%=mod;
    }
    printf("%lld\n",dp[1]);
    return 0;
}

Measured memory_bytes: 12544
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

int main() {
  ll A, B, C;
  cin >> A >> B >> C;
  if (A + B < C) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  return 0;
}

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

int a[200000],b[200000],go[200001]; 

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    //int a[M],b[M];
    int i=0;
    //int go[M];

    for(i=0;i<M;i++){
        scanf("%d %d",&a[i],&b[i]);
        go[i]=0;
    }
    for(i=0;i<M;i++){
        if(a[i]==1){
            go[b[i]]++;
        }
        if(b[i]==N){
            go[a[i]]++;
        }
    }
    for(i=0;i<M+1;i++){
        if(go[i]>=2){
            printf("POSSIBLE\n");
            return 0;
        }
    }
    cout <<"IMPOSSIBLE"<<endl;

    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
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; }
const long long INF = 1LL << 60;

long long dp[1000000];
vector<vector<int>> G;

int rec(int v) {
	if (dp[v] != -1)return dp[v];
	int res = 0;

	for (auto nv : G[v]) {
		chmax(res, rec(nv) + 1);
	}

	return dp[v] = res;
}

int main() {
	int n, m;
	cin >> n >> m;
	G.assign(n, vector<int>());
	for (int i = 0;i < m;i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
	}
	int res = 0;
	for (int i = 0;i < n;i++)dp[i] = -1;
	for (int v = 0;v < n;v++)chmax(res, rec(v));
	cout << res << endl;
}

Measured memory_bytes: 8576
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

#define REP(i,p,n) for(ll i=p;i<ll(n);++i)
#define rep(i,n) REP(i,0,n)

using ll = long long int;
using pll = pair<ll, ll>;

int main()
{
    ll L, R, d;
    cin >> L >> R >> d;

    ll ans = 0;

    for (ll i=L;i<=R;++i)
    {
        ans += (i%d) == 0 ? 1 : 0;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  ll N,W;
  cin >> N >> W;
  ll w[N],v[N];
  vector<ll> Qu[4];
  ll weight;
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    cin >> w[i] >> v[i];
    Qu[w[i] - w[0]].push_back(v[i]);
  }
  weight = w[0];
  for (int i = 0; i < 4; i++) {
    sort(Qu[i].begin(),Qu[i].end());
    reverse(Qu[i].begin(),Qu[i].end());
  }
  vector<ll> S[4];
  for (int i = 0; i < 4; i++) {
    S[i].push_back(0);
    for (int j = 0; j < (int)Qu[i].size(); j++) {
      S[i].push_back(S[i][S[i].size()-1] + Qu[i][j]);
    }
  }
  for (int i = 0; i < (int)S[0].size(); i++) {
    for (int j = 0; j < (int)S[1].size(); j++) {
      for (int k = 0; k < (int)S[2].size(); k++) {
        for (int l = 0; l < (int)S[3].size(); l++) {
          if ((i * weight) + (j * (weight + 1)) + (k * (weight + 2)) + (l * (weight + 3)) <= W) {
            ans = max(ans,S[0][i] + S[1][j] + S[2][k] + S[3][l]);
          }
        }
      }
    }
  }

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

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

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

        int n; cin >> n;
        long long ans = 0;
        vector<int> a(n);
        for(auto &it : a) cin >> it;

        sort(a.begin(), a.end());
        n--;

        ans += a.back();
        a.pop_back();
        --n;

        while(!a.empty() && n > 0) {
                for(int i = 0; i < 2 && n > 0; ++i) {
                        --n;
                        ans += 1ll * a.back();
                }
                a.pop_back();
        }

        cout << ans;

        return 0;
}


Measured memory_bytes: 3988
#include <bits/stdc++.h>
using namespace std;
#define AC 0
vector<int> f;
inline int getf(int x) {
	if(f[x]!=x) f[x]=getf(f[x]);
	return f[x];
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	f.resize(n);
	for(int i=0;i<n;i++) f[i]=i;
	for(int x,y;m--;) {
		cin>>x>>y;
		f[getf(y-1)]=getf(x-1);
	}
	vector<int> num(n);
	for(int i=0;i<n;i++) num[getf(i)]++;
	int ans=0;
	for(int i=0;i<n;i++) ans=max(ans,num[i]);
	cout<<ans<<'\n';
	return AC;
}


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

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

  n = n %10;
  switch(n) {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      cout << "hon" << endl;
      break;
    case 0:
    case 1:
    case 6:
    case 8:
      cout << "pon" << endl;
      break;
    case 3:
      cout << "bon" << endl;
      break;
  }
}

Measured memory_bytes: 3620
N=int(input())
S=input()

R,G,B=0,0,0
for i in range(N):
    if S[i]=="R":
        R+=1
    elif S[i]=="G":
        G+=1
    else:
        B+=1

rest=0
for i in range(N):
    for j in range(i,N):
        k=2*j-i
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            rest+=1

ans=R*G*B-rest

print(ans)

Measured memory_bytes: 9120
p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in range(p):
	r+=z[i]*(z[i]-1)//2
print(r)

Measured memory_bytes: 9288
N,M = map(int,input().rstrip().split(" "))
stu = [[] for i in range(N)]
che = [[] for i in range(M)]
for i in range(N):
    stu[i] = list(map(int,input().rstrip().split(" ")))
for i in range(M):
    che[i] = list(map(int,input().rstrip().split(" ")))
for i in range(N):
    ansnum = 0
    ansdis = 10 ** 9
    for i2 in range(M):
        if abs(che[i2][0] - stu[i][0]) + abs(che[i2][1] - stu[i][1]) < ansdis:
            ansnum= i2 + 1
            ansdis = abs(che[i2][0] - stu[i][0]) + abs(che[i2][1] - stu[i][1])
    print(ansnum)


Measured memory_bytes: 9188
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<int64_t> vector(87);
  vector.at(0) = 2;
  vector.at(1) = 1; 

  for(int i = 0; i < 85; i++){
      vector.at(i+2) = vector.at(i) + vector.at(i+1);
  } 

  int N;
  cin >> N;

  cout << vector.at(N) << endl;
}


Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(){
  int a,b,c,d,e,f,ans;
  cin >>a>>b>>c>>d>>e>>f;
  ans = a+5*b+10*c+50*d+100*e+500*f;
  if (ans >= 1000){
    cout << 1<<endl;;
  }else{
    cout <<0<<endl;;
  }
  return 0;
}

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define Inf (long long)1000000000000000000

int main(){
	int N,M;
	cin>>N>>M;
	
	//距離をInfで初期化
	long long dis[N][N];
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			if(i==j)dis[i][j]=0;
			else dis[i][j]=Inf;
		}
	}
	
	//辺の情報を受け取る(有向辺を想定)
	for(int i=0;i<M;i++){
		int a,b,d;
		cin>>a>>b>>d;
		a--;b--;
		dis[a][b]=min(dis[a][b],(long long)-d);
	}
	bool flag = true;
	//最短距離を求める
	for(int k=0;k<N;k++){
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(dis[i][j]>dis[i][k]+dis[k][j]){
					dis[i][j]=min(Inf,dis[i][k]+dis[k][j]);
				}
			}
		}
	}
	
	for(int i=0;i<N;i++){
		if(dis[i][i]<0&&dis[0][i]<10000000000000000&&dis[i][N-1]<10000000000000000){
			flag=false;
			break;
		}
	}
	
	
	if(flag)cout<<-dis[0][N-1]<<endl;
	else cout<<"inf"<<endl;
	return 0;
}

Measured memory_bytes: 8064
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>
#include <random>
#include <list>
#include <numeric>
#include <chrono>
#include <set>


#define rep(i,p,q) for(ll i = p;i < q;i++)
#define ll long long

using namespace std;

vector<vector<ll>> graph;
vector<ll> query;
vector<ll> ans;
vector<ll> visited;


const long long MAX_N = 1 << 17;
const long long MOD = 1000000007;

long long dat[2 * MAX_N - 1];

ll fact(ll n) {
	if (n == 1) return 1;
	if (n == 0) return 0;
	return n * fact(n - 1);
}

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

//ABC152
int main(void) {
	ll n, m;
	cin >> n >> m;
	cout << (n == m ? "Yes" : "No") << endl;
}


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


int main(void) {
	int x,y,z;
	cin >> x >> y >> z;
	x-=z;
	int ans=0;
	for(int i=0; ; i++){
		if(i*(y+z)<=x)ans=i;
		else break;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[200005];
int st[200005],c[200005],top;
bool check(int k)
{
	top=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]>a[i-1])
		{
			if(st[top]!=1)++top;
			st[top]=1;
			c[top]=a[i];
			continue;
		}
		while(c[top-1]>=a[i])top--;
		c[top]=a[i];
		if(st[top]==k)
		{
			int num=c[top--];
			if(!top)return 0;
			if(c[top]!=c[top-1]+1)
			{
				c[top]--;
				top++;
				c[top]=c[top-1]+1;
				st[top]=st[top-1];
			}
			st[top]++;
			if(st[top]==st[top-1])c[top-1]=c[top],top--;
			st[++top]=1;
			c[top]=num;
		}
		else
		{
			if(c[top]!=c[top-1]+1)
			{
				c[top]--;
				top++;
				c[top]=c[top-1]+1;
				st[top]=st[top-1];
			}
			st[top]++;
			if(st[top]==st[top-1])c[top-1]=c[top],top--;
		}
	}
	return 1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using LL = long long;
#define eps 1e-8
#define fi first
#define se second
#define eb emplace_back
#define close \
    std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c)         \
    (sort(c.begin(), c.end()), \
     c.resize(distance(c.begin(), unique(c.begin(), c.end()))))
#define CASET           \
    int ___T;           \
    scanf("%d", &___T); \
    for (int __CS = 1; __CS <= ___T; __CS++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
mt19937 dlsrand(random_device{}());
mt19937 mrand(std::chrono::system_clock::now().time_since_epoch().count());
int rnd(int x) { return mrand() % x; }
LL bin(LL x, LL n, LL MOD) {
    LL ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
const double PI = acos(-1.0);
constexpr int maxn = 3e3 + 10;
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 998244353;
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
void dec(int &a, int b) {
    a -= b;
    if (a < 0) a += mod;
}
int n, s, dp[maxn][maxn], a[maxn];
int main() {
    cin >> n >> s;
    int ans = 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        memcpy(dp[i], dp[i - 1], sizeof dp[0]);
        for (int j = a[i]; j <= s; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i]]) % mod;
        }
        dp[i][a[i]] = (dp[i][a[i]] + i) % mod;
        add(ans, dp[i][s]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 35584
open Hashtbl
let n = Scanf.scanf " %d" (+) 0
let ds = Array.init n @@ fun _ -> Scanf.scanf " %d" (+) 0
let m = Scanf.scanf " %d" (+) 0
let ts = Array.init m @@ fun _ -> Scanf.scanf " %d" (+) 0
let h = create 200000
let _ = Array.iter (fun t -> if mem h t then replace h t @@ find h t + 1 else add h t 1) ts;
  Array.iter (fun d -> if mem h d then replace h d @@ max 0 @@ find h d - 1) ds;
  iter (fun _ c -> if c <> 0 then (print_endline "NO"; exit 0)) h; print_endline "YES"

Measured memory_bytes: 23168
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  myerr("-----start-----");
  var start = new Date();
  Main();
  var end = new Date() - start;
  myerr("----- end -----");
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var N = nextInt();
	N %= 10;
	if(N == 2 || N == 4 || N == 5 || N == 7 || N == 9){
		myout("hon");
	}else if(N == 0 || N == 1 || N == 6 || N == 8){
		myout("pon");
	}else{
		myout("bon");
	}
}


Measured memory_bytes: 30032
import math
N = 100001
pr = [True]*(N+1)
pr[0] = pr[1] = False
for i in range(2,int(math.sqrt(N))) :
    if pr[i]:
        for j in range(i+i,N,i):pr[j] = False

c = [0]*(N+1)

for i in range(3,N,2):
    if pr[i] and pr[(i+1)//2]:
        c[i]+=1
for i in range(3,N):
    c[i]+=c[i-1]
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(c[r]-c[l-1])

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

int n,k;
vector<ll> w(100000);

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

ll solve(){
  ll left,right,mid;
  left = 0;
  right = 100000*10000;
  while(left<right){
    mid = (left + right)/2;
    if(check(mid)>=n) right = mid;
    else left = mid+1;
  }
  return right;
}



int main(){
  cin >> n >> k;
  rep(i,n) cin >> w[i];
  ll ans = solve();
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3456
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

N=int(input())
X=input().split()
X=[int(x) for x in X]

cost=[]

for i in range(1,101):
    c=0
    for x in X:
        c+=(x-i)**2
    cost.append(c)

print(min(cost)) 




Measured memory_bytes: 3060
#include <iostream> 
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <bits/stdc++.h> 
using namespace std; 
int i,j,n,m,dp,mini;

int min(int a,int b)
{
    if(a>b)
    return b;
    return a;
}

int mod (int a)
{
    if(a<0)
    return a*(-1);
    return a;
}

int steps(int *A,int K,int N)
{
    int dp[N];
    dp[0]=0;
    dp[1]=mod(A[1]-A[0]);
  
    for(i=2;i<N;i++)
    {
        mini = mod(A[i]-A[i-1])+dp[i-1];
        for(j=1;j<=K&&j<=i;j++)
        {
            mini=min(dp[i-j]+mod(A[i]-A[i-j]),mini);
        }
        dp[i]=mini;
    }
   return dp[N-1];
}

int main()
{
    int N,K;
    cin>>N>>K;
    int a;
    int A[N];
    for(int i=0;i<N;i++)
    {
        cin>>a;
        A[i]=a;
    }
    if(N==1)
    cout <<0;
    if(N==0)
    cout <<0;
    else if(N==2)
    cout<<mod(A[1]-A[0]);
    else
    cout<<steps(A,K,N);
    return 0;
}

Measured memory_bytes: 4400
#include<iostream>
#define BOARD_LEN 9
using namespace std;

void Rule_Col(int board[][BOARD_LEN], int bad[][BOARD_LEN]){
	for(int i = 0; i < BOARD_LEN; ++i){
		for(int j = 0; j < BOARD_LEN; ++j){
			int t = board[j][i];
			for(int k = 0; k < BOARD_LEN; ++k){
				if( k == j )
					continue;
				if( t == board[k][i] )
					bad[k][i] = 1;
			}
		}
	}
}
void Rule_Row(int board[][BOARD_LEN], int bad[][BOARD_LEN]){
	for(int i = 0; i < BOARD_LEN; ++i){
		for(int j = 0; j < BOARD_LEN; ++j){
			int t = board[i][j];
			for(int k = 0; k < BOARD_LEN; ++k){
				if( k == j )
					continue;
				if( t == board[i][k] )
					bad[i][k] = 1;
			}
		}
	}
}
void Rule_Square(int board[][BOARD_LEN], int bad[][BOARD_LEN]){
	const int ai[] = {1,4,7};
	const int aj[] = {1,4,7};

	for(int i = 0; i < sizeof(ai)/sizeof(*ai); ++i){
		for(int j = 0; j < sizeof(aj)/sizeof(*aj); ++j){
			const int di[] = {-1,0,1,-1,0,1,-1,0,1};
			const int dj[] = {-1,-1,-1,0,0,0,1,1,1};
			for(int k = 0; k < sizeof(di)/sizeof(*di); ++k){
				int t = board[ai[i]+di[k]][aj[j]+dj[k]];
				for(int l = 0; l < sizeof(di)/sizeof(*di); ++l){
					if( k == l )
						continue;
					if( t == board[ai[i]+di[l]][aj[j]+dj[l]] )
						bad[ai[i]+di[l]][aj[j]+dj[l]] = 1;
				}
			}
		}
	}
}
int main(void){
	int n;
	bool bFirst = true;

	cin >> n;
	for(int D = 0; D < n; ++D){
		int bad[BOARD_LEN][BOARD_LEN] ={{0,},};
		int board[BOARD_LEN][BOARD_LEN];

		if( bFirst )
			bFirst = false;
		else
			cout << '\n';

		for(int i = 0; i < sizeof(board)/sizeof(*board); ++i){
			for(int j = 0; j < sizeof(*board)/sizeof(**board); ++j){
				cin >> board[i][j];
			}
		}
		Rule_Col( board, bad );
		Rule_Row( board, bad );
		Rule_Square( board, bad );
		for(int i = 0; i < sizeof(board)/sizeof(*board); ++i){
			for(int j = 0; j < sizeof(*board)/sizeof(**board); ++j){
				if( bad[i][j] )
					cout << '*';
				else
					cout << ' ';
				cout << board[i][j];
			}
			cout << '\n';
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
using namespace std;
int cup[3]={1,0,0};
int main(){
  for(;;){
    char a,b;
    int x,y,z;
    if(scanf("%c,%c%*c",&a,&b) == EOF) break;
    x = a-'A';
    y = b-'A';
    z = cup[x];
    cup[x] = cup[y];
    cup[y] = z;
  }
  for(int i=0; i<3; i++) if(cup[i] == 1) cout <<(char)('A'+i)<<endl;
  return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N (100000L)
#define NUM_MOD (1000000007L)

long mod(long n, long k) { return n % k >= 0 ? n % k : n % k + k; }

long pow_10s[MAX_N + 1] = {};
long dpss[MAX_N + 1][13] = {};

int main(int argc, char *argv[]) {
  // read inputs
  char cs[MAX_N + 1];
  scanf("%s", cs);
  const long N = strlen(cs);

  // calculate powers of 10
  pow_10s[0] = 1;
  for (long i = 0; i < N; i++) {
    pow_10s[i + 1] = (10 * pow_10s[i]) % 13;
  }

  // solve
  // initialize
  dpss[N][0] = 1;
  for (long j = 1; j < 13; j++) {
    dpss[N][j] = 0;
  }
  // update
  long num_q = 0;
  for (long i = N - 1; i >= 0; i--) {
    const char c = cs[i];
    if (c == '?') {
      num_q++;
    }
    for (long j = 0; j < 13; j++) {
      if (c != '?') {
        const long d = c - '0';
        dpss[i][j] = dpss[i + 1][mod(j - d * pow_10s[N - i - 1], 13)];
      } else {
        for (long d = 0; d < 10; d++) {
          dpss[i][j] =
              (dpss[i][j] + dpss[i + 1][mod(j - d * pow_10s[N - i - 1], 13)]) %
              NUM_MOD;
        }
      }
    }
  }

  printf("%ld\n", dpss[0][5]);

  return 0;
}


Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
vector<ll>date;

void dfs(ll now){
  if(now>=3234566667
){
    return;
  }

  if(now%10==0){
    date.push_back(now*10+now%10+1);
    date.push_back(now*10+now%10);
    dfs(now*10+now%10+1);
    dfs(now*10+now%10);
    
  }
  
   else if(now%10==9){
    date.push_back(now*10+now%10-1);
    date.push_back(now*10+now%10);
    dfs(now*10+now%10-1);
    dfs(now*10+now%10);
    
  }
  
  
  else{
    date.push_back(now*10+now%10+1);
    date.push_back(now*10+now%10);
    date.push_back(now*10+now%10-1);
    dfs(now*10+now%10+1);
    dfs(now*10+now%10-1);
    dfs(now*10+now%10);
  }

}
int main(){
  
  ll K;
  cin>>K;
  
  
  rep(i,9){
    dfs(i+1);
  }
rep(i,9){
date.push_back(i+1);
}
  
  sort(all(date));
  
  cout<<date[K-1]<<endl;
  
  
  


}


Measured memory_bytes: 6256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define re cin>>
#define pr cout<<
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)


const int N=6e5+5;
const int mod=1e9+7;

vector<pii> qq[N];
int ar[N],q,n,ans[N];
int old[N];


struct bit{
      int nn;
      vector<ll> v;
      bit(){}
      bit(int x){nn=x;v=vector<ll>(nn+1,0);}
      ll query(ll x){
            ll res=0; 
            while(x) res+=v[x],x-=(x&-x);
            return res;
      }
      void update(ll x,ll by){ while(x<=nn) v[x]+=by, x+=(x&-x); }	
} bb(N);

int main(){
      
      cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
      
      cin>>n>>q;
      for(int i=1;i<=n;i++) cin>>ar[i];

      for(int i=1;i<=q;i++) {
            int l,r;
            cin>>l>>r;
            qq[r].push_back({l,i});
      }     

      for(int i=1;i<=n;i++){
            if(old[ar[i]]) bb.update(old[ar[i]],-1);
            old[ar[i]]=i;
            bb.update(i,1);
            for(auto pp: qq[i]){
                  ans[pp.second]=bb.query(N-2)-bb.query(pp.first-1);
            }
      }

      for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
      return 0;
}

Measured memory_bytes: 38332
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;
 
#define rep(i, n) for(int i = 0; i < (int)(n);    i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;

ll gcd ( ll a, ll b ) { if ( b == 0 ) return a; else return gcd ( b, a%b ); }
ll lcm ( ll a, ll b ) { return a * b / gcd(a, b); }


int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int N, C; std::cin >> N >> C;
  std::vector<std::vector<std::pair<int,int>>> L(C);
  rep(i,N) {
    int s, t, c; std::cin >> s >> t >> c; c--;
    L[c].push_back( {s,t} );
  }

  std::vector<int> S(3e5);
  rep(i,C) {
    std::vector<int> tt(3e5);
    rep(j,sz(L[i])) tt[L[i][j].first*2-1]++, tt[L[i][j].second*2]--;
    rep(j,3e5) if( j != 0 ) tt[j] += tt[j-1];
    rep(j,3e5) if ( tt[j] > 0 ) S[j]++;
  }

  int ans = 0;
  rep(i,3e5) chmax(ans, S[i]);
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 3840
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Buffer(make([]byte, 500000), 500000)
	sc.Split(bufio.ScanWords)

	s := next()
	t := next()

	count := 0
	for i := range s {
		if s[i] == t[i] {
			count++
		}
	}
	fmt.Println(count)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextInt64() int64 {
	sc.Scan()
	i, _ := strconv.ParseInt(sc.Text(), 10, 64)
	return i
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;


class Program
{
    static void Main(string[] args)
    {

        List<long> a = new List<long>();
        int n = int.Parse(Console.ReadLine());
        long max = -999999999999;
        long min = 999999999999;

        for (int j = 0; j < n;j++)
        {
            string s = Console.ReadLine();
            if (string.IsNullOrEmpty(s)) break;
            a.Add(long.Parse(s));
        }


		for (int i = 0; i <= n - 1; i++)
		{
			max = Math.Max(max, a[i] - min);
			min = Math.Min(min, a[i]);
		}



        Console.WriteLine("{0}",max);

	}
}

Measured memory_bytes: 14692
N,M = map(int,input().split())

x = [0] * N
y = [0] * N
ans = 0

for i in range(M):
    s,c = map(int,input().split())
    s -= 1
    if y[s] != 0 and x[s] != c:
        ans = -1
    else:
        y[s] = 1
        x[s] = c

if ans == -1:
    pass
elif y[0] == 1 and N > 1 and x[0] == 0:
    ans = -1
elif N > 1 and x[0] == 0:
    ans = 10 ** (N-1)
    for i in range(N):
        ans += x[i] * (10**(N-i-1))
else:
    for i in range(N):
        ans += x[i] * (10**(N-i-1))

print(ans)
    

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

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

    while (k != 0) {
        if (a >= b) {
            b = b * 2;
            k--;
        }
        else if (b >= c) {
            c = c * 2;
            k--;
        }
        else break;
    }

    if (a < b && b < c) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
        return 0;
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	public static void main(String[] args) throws IOException{
		// 入力導入部
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		
		String strin=br.readLine();
		String[] str=strin.split("");
		
		for(String i:str){
			if(i.equals(i.toLowerCase())){
				System.out.print(i.toUpperCase());
			}else System.out.print(i.toLowerCase());
		}
		
		System.out.println();
		}}

Measured memory_bytes: 19268
#include <cstddef>
#include <complex>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>
#include <bitset>

using ll = long long;
using ull = unsigned long long;

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

int main()
{
    using namespace std;

    int p, q, r;
    cin >> p >> q >> r;

    cout << min({p + q, q + r, r + p}) << endl;

    return 0;
}


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

int main () {
    
    int n = 0, l = 0, r = 0, s = 0;

    scanf ("%d", &n);
    while (n--) {
        scanf ("%d%d", &l, &r);
        s += abs (r - l) + 1;
    }

    printf ("%d\n", s);
    return 0;
}

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


def solve(A: int, P: int):
    piece = A * 3 + P
    print(piece // 2)
    return


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

    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    solve(A, P)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include<bits/stdc++.h> 
using namespace std;
long long x,k,d;
int main() {
	scanf("%lld%lld%lld",&x,&k,&d);
	x = abs(x);
	k = abs(k);
	d = abs(d);
	if (abs(x/d) >= k) {
		printf("%lld",abs(x-k*d));
	}
	else {
		long long n = x/d;
		n++;
		if ((k-n)%2 ==1) {
			n++;
		}
		x -= d*n;
		printf("%lld",min(abs(x),x+d+d));
	}
	return 0;
}

Measured memory_bytes: 3828
R,G,B,N=map(int,input().split())
import math
ans=0
a=math.floor(N/R)
for i in range(a+1):
    nokori=N-R*i
    b=math.floor(nokori/G)
    for j in range(b+1):
        nokori2=nokori-j*G
        if nokori2%B==0:
            ans+=1
        else:
            pass
print(ans)

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

int main() {
    for(;;){
        int n;
        cin >> n;
        if (n==0) {
            break;
        }
        int a[n];
        for (int i=0; i<n;i++) {
            cin >> a[i];
        }
        sort(a,a+n);
        int ans=0;
        for (int i=1;i<n-1;i++) {
            ans+=a[i];
            }
        cout<<ans/(n-2)<<"\n";
        }
}

Measured memory_bytes: 1176
use std::io::*;
use std::str::FromStr;

pub 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")
}

use std::cmp::max;

fn main() {
    let x = read::<usize>();

    let mut dp = vec![vec![0; 100001]; 7];
    dp[0][0] = 1;
    for i in 1..7 {
        for j in 0..100001 {
            if j >= 99+i && dp[i][j-i-99] == 1 {
                dp[i][j] = 1;
            }
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
        }
    }
    println!("{}", dp[6][x]);
}


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

int main() {
	int n,m,i,j,k;
	cin >> n;
	vector<int> x(n),y(n);
	int array[]={0,1,2,3,4,5,6,7};
	
	double ans,cur,res;
	for(i=0; i<n; i++){
		cin >> x[i] >> y[i];
	}
	
	ans=0;
	for(i=0; i<n-1; i++){
		for(j=i+1; j<n; j++){
			ans+=sqrt(double((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])));
		}
	}
	cout << fixed ;
	cout<< setprecision(8) <<ans*2/n;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]C - Go to School
            int N = int.Parse(Console.ReadLine());
            var A = ReadLine();

            var ids = Enumerable.Range(1, N).ToArray();

            Array.Sort(A, ids);

            Console.WriteLine(String.Join(" ", ids));            
        }

        static int[] ReadLine()
        {
            var line = Console.ReadLine();
            var arr = line.Split(' ');

            return arr.Select(x => int.Parse(x)).ToArray();
        }
    }
}

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

int main(){
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> x(n, k-q);
    rep(i,q){
        int a;
        cin >> a;
        --a;
        x[a]++;
    }
    rep(i,n) {
        if(x[i]<=0) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <cmath>
#include <stdio.h>
#include <functional>

using namespace std;
using ll = long long;
using ld = double;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll, ll>;
const ll INF = 1e17;
const ld eps = 1e-10;
const ll MOD = 1e9 + 7;

const double pi = acos(-1.0);

ll fmod(ll a, ll mod) {
	if (a<0) {
		return (a + (-a / mod + 1)*mod) % mod;
	}
	else
		return a%mod;
}

ll gcd(ll a, ll b) {
	if (a%b == 0)
		return b;
	else
		return gcd(b, a%b);
}
//ax+by=1のxを求める(bは素数)
ll extgcd(ll a, ll b) {
	if (b%a == 0)
		return 1;
	else {
		return (1 - b*extgcd(b%a, a)) / a;
	}
}

ll power(ll base, ll n) {
	if (n == 0)
		return 1;
	ll xx = power(base, n / 2);
	if (n % 2)
		return (xx * xx) % MOD * base % MOD;
	else
		return (xx * xx) % MOD;
}

vector<ll> fact;
vector<ll> ifact;

ll comb(ll n, ll r) {
	return fact[n] * ifact[n - r] % MOD * ifact[r] % MOD;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N, A, B, C;
	cin >> N >> A >> B >> C;
	fact.resize(N * 2 + 10, 1);
	ifact.resize(N * 2 + 10, 1);
	for (ll i = 1;i < fact.size();i++) {
		fact[i] = fact[i - 1] * i % MOD;
		ifact[i] = fmod(extgcd(fact[i], MOD), MOD);
	}
	ll tmpa = 100 * fmod(extgcd(A + B, MOD), MOD) * A % MOD;
	B = 100 * fmod(extgcd(A + B, MOD), MOD) * B % MOD;
	A = tmpa;
	ll Q = power(100, 2 * N - 1);
	ll P = 0;
	for (ll i = 0;i < N;i++) {
		P = (P + power(A, N) * power(B, i) % MOD * comb(N + i - 1, i) % MOD * power(100, N - i) % MOD * (N + i)) % MOD;
		P = (P + power(A, i) * power(B, N) % MOD * comb(N + i - 1, i) % MOD * power(100, N - i) % MOD * (N + i)) % MOD;
	}
	Q = Q * (100 - C) % MOD;
	//cout << P << "/" << Q << endl;
	cout << P * fmod(extgcd(Q, MOD), MOD) % MOD << endl;
	return 0;
}






Measured memory_bytes: 3328
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<25;
const double pi=acos(-1);
const double eps=1e-8;
const vi emp;

int n,s;

int func(int x){
	x*=x;
	x/=100;
	x%=10000;
	return x;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>s;
		cout<<"Case "<<i+1<<':'<<endl;
		for(int i=0;i<10;i++){
			s=func(s);
			cout<<s<<endl;
		}
	}
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n;
ll d,x[200001],y[200001];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>d;
	d*=d;
	int ans=0;
	rep(i,n){
		cin>>x[i]>>y[i];
		x[i]*=x[i];
		y[i]*=y[i];
		if(x[i]+y[i]<=d)
		ans++;
	}
	cout<<ans;
	re 0;
}

Measured memory_bytes: 6772
N, A, B, C = gets.split(' ').map(&:to_i)
L = N.times.map { gets.to_i }

def f(cur, a, b, c)
  if cur == N
    return [a,b,c].min > 0 ? (a - A).abs + (b - B).abs + (c - C).abs - 30 : Float::INFINITY
  else
    mp1 = f(cur + 1, a, b, c)
    mp2 = f(cur + 1, a + L[cur], b, c) + 10
    mp3 = f(cur + 1, a, b + L[cur], c) + 10
    mp4 = f(cur + 1, a, b, c + L[cur]) + 10

    return [mp1, mp2, mp3, mp4].min
  end
end

puts f(0, 0, 0, 0)


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

int main() {
  int N;
  ll K;
  cin >> N >> K;
  int A[N];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  
  ll d = pow(10, 9) + 7;
  ll ans = 0;
  ll sum1 = 0;
  ll sum2 = 0;
  
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (A[i] > A[j]) sum1++;
    }
  }

  int a[2 * N];
  for (int i = 0; i < N; i++) {
    a[i] = A[i];
    a[N + i] = A[i];
  }

  
  for (int i = 0; i < N; i++) {
    for (int j = N; j < 2 * N; j++) {
      if (a[i] > a[j]) {
        sum2++;
      }
    }
  }
  
  ans += K * sum1 % d;
  ans += (K * (K - 1) / 2) % d * (sum2);
  ans %= d;
  cout << ans << "\n";
  return 0;
}

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

const int N_MAX = 100;
const int W_MAX = 10000;

int N;
int W;

int *value;
int *weight;

int dp[N_MAX + 1][W_MAX + 1];

int rec(int index,int maxWeight)
{
    if(dp[index][maxWeight] != -1)
    {
        return dp[index][maxWeight];
    }
    int res;
    if(index==N)
    {
        res = 0;
    }
    else if (maxWeight < weight[index]){
        res = rec(index + 1,maxWeight);
    }
    else
    {
        res = max(
            rec(index + 1,maxWeight),
            rec(index + 1,maxWeight - weight[index]) + value[index]
        );
    }
    dp[index][maxWeight] = res;


    return res;
}

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

    for(int i = 0;i < N_MAX + 1;i++)
    {
        for(int j = 0;j < W_MAX + 1;j++)
        {
            dp[i][j] = -1;
        }
    }

    value = new int[N];
    weight = new int[N];

    for(int i = 0;i < N;i++)
    {
        cin >> value[i];
        cin >> weight[i];
    }

    cout << rec(0,W) << '\n';


}

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

int main() {
   string S;
   cin >> S;
   if( S == "SSS" ) cout << "0" << endl;
   else if( S == "SSR" ) cout << "1" << endl;
   else if( S == "SRR" ) cout << "2" << endl;
   else if( S == "SRS" ) cout << "1" << endl;
   else if( S == "RSS" ) cout << "1" << endl;
   else if( S == "RSR" ) cout << "1" << endl;
   else if( S == "RRR" ) cout << "3" << endl;
   else if( S == "RRS" ) cout << "2" << endl;
}

Measured memory_bytes: 3620
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>
#include<map>
#include<queue>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)
#define in(i,j,k) ((i)>=(j)&&(i)<=(k))

int main(){
	int n,s,a,c;
	vector<int> v;
	for(;;){
		scanf("%d%d",&n,&s);
		if(n==0 && s==0)break;
		v.clear();
		rep(i,10)v.push_back(i<n);
		c=0;
		do{
			a=0;
			rep(i,10)a+=i*v[i];
			c+=(s==a);
		}while(prev_permutation(v.begin(),v.end()));
		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 1208
use proconio::input;

#[proconio::fastout]
pub fn main() {
    const M: i64 = 1000000007;
    input! {
    n:usize,
    k:usize,
    a:[i64;n],
    }
    let mut a_pos: Vec<i64> = a.iter().filter(|&x| x >= &0).cloned().collect();
    let mut a_neg: Vec<i64> = a.iter().filter(|&x| x <= &0).cloned().collect();
    let ans = if n == k {
        a.iter().fold(1, |pr, v| (pr * v).rem_euclid(M))
    } else if a_pos.len() == 0 && k % 2 == 1 {
        //必ず非正。絶対値を最小化したい
        a_neg.sort_by_key(|&x| std::cmp::Reverse(x));
        a_neg.iter().take(k).fold(1, |pr, v| (pr * v).rem_euclid(M))
    } else {
        //必ず非負
        a_pos.sort();
        a_neg.sort();
        let init = if k % 2 == 1 {
            a_pos.pop().unwrap()
        } else {
            1
        };
        let mut a_all: Vec<i64> = a_pos.rchunks_exact(2).map(|c| c[0] * c[1]).collect();
        a_all.append(&mut a_neg.chunks_exact(2).map(|c| c[0] * c[1]).collect());
        a_all.sort_by_key(|&x| std::cmp::Reverse(x));
        let b = a_all.iter().take(k / 2).map(|&v| v.rem_euclid(M));
        (init * b.fold(1, |pr, v| (pr * v).rem_euclid(M))).rem_euclid(M)
    };
    println!("{}", ans);
}


Measured memory_bytes: 9484
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define cst(x) cout<<fixed<<setprecision(x)
#define pi 3.14159265359
#define mod 1000000007
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;
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; }


int main(){

    int h,w,d; cin >> h >> w >> d;
    map<int,pint> mp;
    rep(i,h)rep(j,w){
        int key; cin >> key;
        mp[key] = make_pair(i,j);
    }
    vector<ll> cum(h*w+1);
    for(int i = 1; i <= d; i++) cum.at(i) = 0;
    for(int i = d+1; i <= h*w; i++){
        pint n = mp.at(i);
        pint nv = mp.at(i-d);
        cum.at(i) = cum.at(i-d) + abs(n.first-nv.first) + abs(n.second - nv.second);
    }
    int q; cin >> q;
    rep(i,q){
        int l,r; cin >> l >> r;
        ll cost;
        cost = cum.at(r) - cum.at(l);
        cout << cost << endl;
    }

    return 0;   

}


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

int n;
long long a[100010];
long long memo[100010][2];
long long dp(int pos, int nxt) {
    if (pos == n) return 0;
    if (memo[pos][nxt] != -1) return memo[pos][nxt];
        long long ans = - 1LL << 30;
    if (!nxt) {
        ans = a[pos] + dp(pos + 1, 0);
        if (pos != n - 1) ans = max(ans, -a[pos] + dp(pos + 1, 1));
    } else {
        ans = -a[pos] + dp(pos + 1, 0);
        if (pos != n - 1) ans = max(ans, a[pos] + dp(pos + 1, 1));
    }
    return memo[pos][nxt] = ans;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    memset(memo, -1, sizeof(memo));
    cout << dp(0, 0) << "\n";
    return 0;
}

Measured memory_bytes: 8832