akhauriyash/Code-Regression huggingface dataset:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    r, c, k = ns()

    mat = [[0 for _ in range(c + 1)] for __ in range(r + 1)]
    for _ in range(k):
        x, y, v = ns()
        x, y = x - 1, y - 1
        mat[x][y] = v

    dp = [[0] * 4 for _ in range(c + 1)]

    for i in range(r):
        ndp = [[0] * 4 for _ in range(c + 1)]
        for j in range(c):
            for n in range(2, -1, -1):
                dp[j][n + 1] = max(dp[j][n + 1], dp[j][n] + mat[i][j])

            ndp[j][0] = max(dp[j])
            for n in range(4):
                dp[j + 1][n] = max(dp[j + 1][n], dp[j][n])
        dp = ndp

    print(max(dp[c - 1]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 230496
import sys

X, Y = map(int, input().split())
mod = 10 ** 9 + 7

# if (2 * X - Y) % 3 != 0 or (2 * Y - X) % 3 != 0:
if (X + Y) % 3 != 0:
    # 整数解がない場合
    print(0)
    sys.exit()


m = (2 * X - Y) // 3
n = (2 * Y - X) // 3

if m < 0 or n < 0:
    print(0)
    sys.exit()

u = m + n
fact = [1] * (u+1)

for i in range(1, u+1):
    fact[i] = (fact[i-1] * i) % mod

fact_inv1 = pow(fact[n], mod-2, mod)
fact_inv2 = pow(fact[m], mod-2, mod)

res = (((fact[u] * fact_inv1) % mod) * fact_inv2) % mod

print(res)


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

#define rep(i,n) for(ll i=0;i<(n);++i)
#define reps(i,n) for(ll i=1;i<=(n);++i)
#define out(a) cout<<(a)<<endl;
using ll = long long;
using str = string;
constexpr long long INF = (1LL<<60);
constexpr long long MOD = (1e9+7);
constexpr long long LMAX = LLONG_MAX;
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);} // output
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;} // input,vector<>

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(10);
  
  ll n,k;
  cin>>n>>k;
  vector<ll> a(n);
  cin>>a;

  vector<ll> lef(n),rig(n);
  rep(i,n){
    for(ll j=i+1;j<n;++j){
      if(a[i]>a[j])rig[i]++;
    }
  }
  rep(i,n){
    for(ll j=0;j<i;++j){
      if(a[i]>a[j])lef[i]++;
    }
  }

//for(const auto& elm:lef){cout<<elm<<" ";} cout<<endl;
//for(const auto& elm:rig){cout<<elm<<" ";} cout<<endl;
  ll ans=0;
  ll lk=k*(k-1)/2%MOD,rk=k*(k+1)/2%MOD;
  rep(i,n){
    ll ltmp=(lef[i]*lk)%MOD;
    ll rtmp=(rig[i]*rk)%MOD;
    ans+=ltmp+rtmp;
    ans%=MOD;
  }
  cout<<(ans)<<endl;
  
  
  return 0;
}


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

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) { 
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

int main() {
  double a, b, x; cin>>a>>b>>x;
  double ans = 0.0;
  if(x >= a * b / 2.0 * a) {
    double h = x / (a*a);

    ans = atan2(b - h, a / 2);
    //    cout << b-h << endl;
    //    cout << a / 2 << endl;
  } else {
    //    cout << "Other..." << endl;
    double h = x / a / b * 2.0;
    ans = atan2(b, h);
  }
  ans *= (180.0 / M_PI);
  //  cout << ans << endl;
  printf("%0.10f\n", ans);
  return 0;
}


Measured memory_bytes: 256
import os, sys, re, math

N = int(input())
SP = []
for i in range(N):
    (S, P) = input().split()
    SP.append([S, int(P), (i + 1)])

SP = sorted(SP, key=lambda k:k[1], reverse=True)
SP = sorted(SP, key=lambda k:k[0])

for sp in SP:
    print(sp[2])


Measured memory_bytes: 3188
#include <stdio.h>

int dp[50];

int fib(int n) {
    if (n == 0 || n == 1) return dp[n] = 1;
    if (dp[n] != -1) return dp[n];
    return dp[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    int n, i;
    for (i = 0; i < 50; i++) dp[i] = -1;

    scanf("%d", &n);
    printf("%d\n", fib(n));
    
    return 0;
}



Measured memory_bytes: 2104
//be name khoda

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string s;
	cin>>s;
	for(int i=0;i<4;i++)
		cout<<s[i];
	cout<<' ';
	for(int i=4;i<12;i++)
		cout<<s[i];
	cout<<endl;
	return 0;
}

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

typedef long long ll;
int N;
int K;
//-----------------------------------------------------------------
map<vector<int>, int> memo;
int main() {
	cin >> N >> K;

	if (N < 1000) {
		int ans = 0;
		rep(i, 0, N - 2) {
			int cnt = 0;
			rep(j, 0, 5) {
				int c = 63 * (i + 1) + 9 * (j + 1) + 9;
				if (c % 11 == K) cnt++;
			}
			ans += cnt;
		}
		cout << ans << endl;
		return 0;
	}

	int s, t;

	rep(i, 0, 500) {
		vector<int> v;
		int cnt = 0;
		rep(j, 0, 5) {
			int c = 63 * (i + 1) + 9 * (j + 1) + 9;
			if (c % 11 == K) cnt++;
			v.push_back(c % 11);
		}

		if (memo.find(v) != memo.end()) {
			s = memo[v];
			t = i;
			break;
		}
		memo[v] = i;
	}

	//cout << s << " " << t << endl;

	ll ans = 0;

	ll sm = 0;
	rep(i, s, t) {
		int cnt = 0;
		rep(j, 0, 5) {
			int c = 63 * (i + 1) + 9 * (j + 1) + 9;
			if (c % 11 == K) cnt++;
		}
		sm += cnt;
	}

	//cout << sm << endl;

	ll num = t - s;

	ll dd = (N - 2) / num;
	ans += sm * dd;

	rep(i, s + dd * num, N - 2) {
		int cnt = 0;
		rep(j, 0, 5) {
			ll c = 63LL * (ll)(i + 1LL) + 9LL * (ll)(j + 1LL) + 9LL;
			ll KK = K;
			if (c % 11LL == KK) cnt++;
		}
		ans += cnt;
	}

	cout << ans << endl;
}

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vchar = vector<char>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;

int main(){
  ll a, b;
  cin >> a >>b;
  cout << (a * b % 2 == 0 ? "Even" : "Odd") << endl;
}

Measured memory_bytes: 256
#include <string.h>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <istream>
#define INF 2147483647
#define LLINF 9223372036854775807
typedef long long ll;
using namespace std;
int a[110];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	int ans=1000000000;
	for(int i=1;i<=100;i++){
		int cnt=0;
		for(int j=0;j<n;j++){
			cnt+=(a[j]-i)*(a[j]-i);
		}
		ans=min(ans,cnt);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2000000000;//10^9
ll MOD  = 1000000007;
ll dp[110][100010];


int main() {
    
    int N,K;
    cin >> N >> K;
    vector<int> a(N);
    for(int i = 0; i < N; i++){
        cin >> a.at(i);
    }
    
    for(int i = 0; i < 110; i++){
        dp[i][0] = 1;
    }
    
    
    for(int i = 0; i < N; i++){
        for(int j = 1; j <= K; j++){
            if(j - a.at(i) - 1 >= 0){
                dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-a.at(i)-1];
            }else{
                dp[i+1][j] = dp[i+1][j-1] + dp[i][j];
            }
            dp[i+1][j] %= MOD;
        }
    }
    
    cout << (dp[N][K] + MOD) % MOD << endl;
    
}

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

bool isprime(int num) {
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false;
  double sqrtNum = sqrt(num);
  for (int i = 3; i <= sqrtNum; i += 2) {
    if (num % i == 0) return false;
  }
  return true;
}

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

  while (isprime(X) == false) X++;

  cout << X << "\n";
}

Measured memory_bytes: 256
a=list(map(int,input().split()))
a1=a.copy()
count=0
if a[0]%2==1 or a[1]%2==1 or a[2]%2==1:
    print(count)
elif a[0]==a[1]==a[2]:
    print(-1)
else:
    while True:
        a[0]=(a1[1]+a1[2])//2
        a[1]=(a1[0]+a1[2])//2
        a[2]=(a1[0]+a1[1])//2
        a1=a.copy()
        count+=1
        if a[0]%2==1 or a[1]%2==1 or a[2]%2==1:
            print(count)
            exit()

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<unordered_set>
#include<map>
#include<cmath>
#include <iterator>
#include<stack>
#include<queue>
#include <iomanip>
#include<math.h>
#include <limits.h>
#include <numeric>
#include <functional>
#include<fstream>
#include <bitset>
#include <cstring>
using namespace std;

#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
ll dp[101][(int)1e5+1];
pair<int, int>p[101];
int x, w;
ll f(int i, int w) {
	if (w == 0 || i == x)
		return 0;
	else if (p[i].first > w)
		return dp[i][w] = f(i + 1, w);
	else if (dp[i][w] != -1)
		return dp[i][w];
	return dp[i][w] = max(p[i].second + f(i + 1, w - p[i].first), f(i + 1, w));
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> x >> w;
	for (int i = 0; i < x; i++)
		cin >> p[i].first >> p[i].second;
	memset(dp, -1, sizeof(dp));
	cout << f(0, w) << endl;
	/*for (int i = 0; i < x; i++) {
		for (int j = 0; j <= w; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	return 0;
}

Measured memory_bytes: 79232
def f(d):
    s = {'E':"310542",'S':"402351",'R':"031425"}
    a, b = input().split()
    for c in "SE":
        for i in range(4):
            d = [d[int(i)]for i in s[c]]
            for j in range(4):
                d = [d[int(i)]for i in s['R']]
                if d[0] == a and d[1] == b:
                    print(d[2])
                    return

d = input().split()
for n in range(int(input())): f(d)


Measured memory_bytes: 5608
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());
 
long long power(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}



signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  

    
    int n,x;
    cin>>n>>x;
    if(x==1||x==2*n-1)
    {
        cout<<"No";
    }
    else
    {
        cout<<"Yes\n";
        vector<int>ans;
        if(x<=n)
        {
            for(int i=x+1;i<=n;i++)
                ans.push_back(i);
            for(int i=1;i<=x;i++)
                ans.push_back(i);
            for(int i=n+1;i<=2*n-1;i++)
                ans.push_back(i);
        }
        else
        {
            for(int i=1;i<=n-1;i++)
                ans.push_back(i);
            for(int i=x;i<=2*n-1;i++)
                ans.push_back(i);
            for(int i=n;i<x;i++)
                ans.push_back(i);
        }
        for(auto i:ans)
            cout<<i<<"\n";
        
    }
    

} 
    
 

Measured memory_bytes: 5392
#include<iostream>

using namespace std;
int main() {
    int a, b, c;
    while (1) {
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1)break;
        int o = a + b;
        if (a == -1 || b == -1)cout << "F" << endl;
        else if (o >= 80)cout << "A" << endl;
        else if (o >= 65 && o < 80)cout << "B" << endl;
        else if (o >= 50 && o < 65)cout << "C" << endl;
        else if (o >= 30 && o < 50 && c >= 50)cout << "C" << endl;
        else if (o < 30)cout << "F" << endl;
        else cout << "D" << endl;
    }
    return 0;
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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; }
  
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

int N;
vector<int> adj[100005];
int ans[100005];
vector<int> c;
int id = 0;
bool seen[100005];

void dfs(int now){
    for(auto u:adj[now]){
        if(seen[u] == false){
            seen[u] = true;
            dfs(u);
        }
    }

    //cout << id << endl;
    ans[now] = c[id++];
}

int main(){
    cin >> N;
    for(int i=0; i<N-1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    c.resize(N);
    for(int i=0; i<N; i++) cin >> c[i];
    sort(c.begin(), c.end());
    int sum = 0;
    for(int i=0; i<N-1; i++) sum += c[i];

    seen[1] = true;
    dfs(1);

    cout << sum << endl;
    for(int i=1; i<=N; i++){
        if(i != 1) cout << " ";
        cout << ans[i];
    }
    cout << endl;

    //for(int i=0; i<N; i++) cout << c[i] << endl;
}

Measured memory_bytes: 3328
#include <stdio.h>
int main(void)
{
	int vertical, horizonal, work;
	
	fscanf(stdin, "%d %d", &vertical, &horizonal);
	while (vertical && horizonal) {
		while (0 < vertical--) {
			work = horizonal;
			while (0 < work--) fputc('#', stdout);
			fputc('\n', stdout);
		}
		fputc('\n', stdout);
	fscanf(stdin, "%d %d", &vertical, &horizonal);
	}


	return 0;
}

Measured memory_bytes: 576
import math
a,b,c,d = map(int,input().split()) 

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
a-=1
e=lcm(c,d)

ansb=0
ansb += b//c
ansb += b//d
ansb -= b//e



ansa=0
ansa += a//c
ansa += a//d
ansa -= a//e
print((b-a)-(ansb-ansa))

Measured memory_bytes: 9144
s=list(input())
t=list(input())

sl=len(s)
tl=len(t)

for i in range(sl-tl,-1,-1):
    j=0
    while j<tl :
        if s[j+i]==t[j] or s[j+i]=='?':
            j+=1
        else:
            break
    if j==tl:
        for k in range(tl):
            s[i+k]=t[k]
        for k in range(sl):
            if s[k]=='?':
                s[k]='a'
        print(''.join(s))
        exit()
print('UNRESTORABLE')


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

int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m;
    int low = 0;
    int high = 10000000;
    cin >> n >> m;
    for(int i = 0 ;i < m; i++){
        int l, r;
        cin >> l >> r;
        if (l > low) low = l;
        if(r < high) high = r;
    }
    cout << max(0, high-low+1) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(void){
        int n,k;
        int i=scanf("%d",&n);
        int j=scanf("%d",&k);
        if(i<1||j<1){
                printf("error");
                exit(1);
        }

        int l[n];
        for(int i=0;i<n;i++){
                j=scanf("%d",&l[i]);
                if(j<1){
                        printf("Error");
                        exit(1);
                }
        }

        int tmp=0;
        for(int i=1;i<n;i++){
                for(int j=i;j>0;j--){
                        if(l[j-1]<l[j]){
                                tmp=l[j-1];
                                l[j-1]=l[j];
                                l[j]=tmp;
                        }else{
                                break;
                        }
                }
        }

        int sum=0;
        for(int i=0;i<k;i++){
                sum+=l[i];
        }
        printf("%d",sum);
        return 0;
}

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

int main() {
  
  int N;
  cin >> N;// 先にＮを入力しないと次の行がエラーになる
  vector<int> a(N); 
  for(int i=0; i<N; i++){
    cin >> a.at(i); 
  }
  //cout << "a.at(N-1):"<< a.at(N-1) << endl;
  
  vector<int>b(N);// (N)を書かないとエラーになる
  b.at(0) = a.at(0);
  for(int j=1; j<N; j++){
    b.at(j) = a.at(b.at(j-1)-1);
  }
  //cout << b.at(0) << b.at(1) << b.at(2) << endl;
 
  int count = 0;
  for(int i=0; i<N; i++){
    if(b.at(i) == 2){
      cout << count + 1 << endl;
      break;// !!これ絶対必要。最後の肝
    }
     if(b.at(i) != 2){
      count++;
    }
  } 
  
  //cout << "count" << count << endl;
  if(count == N){
    cout << "-1" << endl;  
  }
  
}


Measured memory_bytes: 1024
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

map<string, int> cont;

int main() {
	int n;
	cin >> n;
	long long res = 0;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;

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

		res += cont[s];
		cont[s]++;

	}


	cout << res << endl;
}


Measured memory_bytes: 11136
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int a,b,n,x,y;
	int dirx[2]={1,0};
	int diry[2]={0,1};
	vector<pair<int,int> > vec;
	while(cin>>a>>b,a||b){
		int ans=0;
		cin>>n;
		vec.clear();
		rep(i,n){
			cin>>x>>y;
			pair<int,int> p;
			p.first=x-1;
			p.second=y-1;
			vec.push_back(p);
		}
		queue<pair<int,int> > que;
		pair<int,int> start(0,0);
		que.push(start);
		while(!que.empty()){
			pair<int,int> now=que.front();
			que.pop();
			if(now.first>=a || now.second>=b)continue;
			bool check=false;
			rep(i,vec.size()){
				if(now==vec[i])check=true;
			}
			if(check)continue;
			if(now.first==a-1 && now.second==b-1)ans++;
			rep(i,2){
				now.first+=dirx[i];
				now.second+=diry[i];
				que.push(now);
				now.first-=dirx[i];
				now.second-=diry[i];
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 13780
#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--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S;
  cin >> S;
  int N=S.size();  
  ll ans=0;
  REP(i,1 << (N - 1)){
    ll sum=0;
    ll a = S[0] - '0';
    
    REP(j,N-1){
      //bitが立っているならば，+を挿入
      if(i & (1<<j)){
        sum += a;
        a=0;
      }
      //立っていなかったら次の文字
      a = a*10 + S[j+1] - '0';
    }
    sum += a;
    ans += sum;
  }
      
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))

cnt = 0
for i in range(len(A)):
    mini = i
    for j in range(i,len(A)):
        if A[j] < A[mini]:
            mini = j
    if i != mini:
        #一番小さい値が確定して，先頭にくる
        A[i],A[mini] = A[mini],A[i]
        cnt += 1
print(*A)
print(cnt)


Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
int W, H, N, x[10009], y[10009];
int main() {
	cin >> W >> H >> N;
	for(int i = 0; i < N; i++) cin >> x[i] >> y[i];
	int ret = 0;
	for(int i = 1; i < N; i++) {
		int w1 = abs(x[i - 1] - x[i]), w2 = abs(y[i - 1] - y[i]);
		if((x[i - 1] - x[i]) * (y[i - 1] - y[i]) >= 0) ret += w1 + w2 - min(w1, w2);
		else ret += w1 + w2;
	}
	cout << ret << endl;
	return 0;
}

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

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#include <array>
#include <deque>
#include <queue>
#include <map>
#include <set>
#define all(x) (x).begin(),(x).end()

const int MOD = 1e9 + 7;

void solve(){

}
ll com(ll n, ll k) {
    if (n == k || k == 0){
        return 1;
    } else {
        return com(n-1, k-1) + com(n-1, k);
    }
}
int main(){
    ll n,k;
    cin >> n >> k;
    cout << n - k + 1 << endl;

    return 0;
}


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

typedef long long int ll;

int main(){
   ll N;
   cin >> N;
   vector<ll> A(N);
   for(ll i = 0;i < N;i++){
      cin >> A[i];
   }
   sort(A.begin(),A.end());
   reverse(A.begin(),A.end());
   ll M = 0,m = 0;
   bool frag = 0;
   bool Q = 1;
   for(ll i = 0;i < N - 1;i++){
   
      if(A[i] == A[i+1] && frag){
         m = A[i];
         break;
      }



      if(A[i] == A[i+1] && Q){
         M = A[i];
         i++;
         frag = 1;
         Q = 0;
      }
      
   }
   cout << M*m << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>


using namespace std;



int main() {

	int A, B, ans, tmp, a, b;

	cin >> A >> B;

	for (int i = 10; i <= 1250; i++) {
		a = i * 0.08;
		b = i * 0.1;
		if (A == a && B == b) {
			ans = i;
			break;
		}
		ans = -1;
	}


	cout << ans;

	return 0;

}

Measured memory_bytes: 256
#include <iostream>
    #include <string>
    #include <set>  
    #include <stack>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    #include <queue>
    #include <deque>
    #include <cstring>
    #include <cstdio>
    #include <map>
    #include <numeric>
    #include <cassert>
    #include <iomanip>
    #include <sstream>
    #include <ctime>
    #include <bitset> 
    #include <unordered_map>
using namespace std;
#define for1(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,maxn) for1(i,0,maxn)
#define ford(i,b,a) for(int i=(int)(b)-1;i>=a;--i)
typedef long long ll;
typedef unsigned long long int128;
typedef pair<int,int> pii;
typedef pair<int,pii > piii;
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
#define mod1 1000000007
#define mod2 998244353
#define eps 1e-10
#define pi acos(-1)
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define dprintf(...) printf(__VA_ARGS__)
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1^1)
const int maxn=1e5+7;
int n;
vector<int> z_o_sum;
int val[maxn];
ll merge_count(vector<int> &a)
{
	if(a.size()<=1)return 0;
	ll cnt=0;
	vector<int> b(a.begin(),a.begin()+a.size()/2);
	vector<int> c(a.begin()+a.size()/2,a.end());
	cnt+=merge_count(b);
	cnt+=merge_count(c);
	int ai=0,bi=0,ci=0;
	while(ai<a.size())
	{
		if(bi<b.size()&&(ci==c.size()||b[bi]<=c[ci]))
			a[ai++]=b[bi++];
		else
			cnt+=a.size()/2-bi,a[ai++]=c[ci++];
	}
	return cnt;
} 
bool chk(int x)
{
	z_o_sum.resize(n);
	ll all=0;
	rep(i,n)
	{
		z_o_sum[i]=i?z_o_sum[i-1]:0;
		if(val[i]>=x)z_o_sum[i]++;
		else z_o_sum[i]--;
		if(z_o_sum[i]<0)all++;
	//	cout<<i<<" "<<z_o_sum[i]<<endl;
	}
	all+=merge_count(z_o_sum);
//	cout<<all<<endl;
	ll n_=1ll*n; 
	return (n_*(n_+1)/2-all)>=((n_*(n_+1)/2+1)/2);
}
int main()
{
	scanf("%d",&n);
	int mx=0;
	rep(i,n)
		scanf("%d",val+i),mx=max(mx,val[i]);
	int lb=-1,ub=mx+1;
	while(ub-lb>1)
	{
		int mid=(lb+ub)>>1;
	//	cout<<mid<<endl;
	//	system("pause");
		if(chk(mid))lb=mid;//cout<<1<<endl;
		else ub=mid;//cout<<2<<endl;
	}
	printf("%d\n",lb);
	return 0;
}

Measured memory_bytes: 1864
def solve():
    n,m = map(int,input().split())
    ans = [None for _ in range(n)]

    for _ in range(m):
        s,c = map(int,input().split())
        if s == 1 and c == 0:#左から一桁めが0のとき
            if n != 1:
                print(-1)
                return
            else:
                ans[0] = c

        if ans[s-1] != None and ans[s-1] != c:#既に値が決まっている桁を再更新する時:
            print(-1)
            return

        ans[s-1] = c


    if ans[0] == None:
        if n != 1:
            ans[0] = 1
        else:
            ans[0] = 0
    
    
    for i in range(1,n):
        if ans[i] == None:
            ans[i] = 0

    print("".join(map(str,ans)))


if __name__ == "__main__":
    solve()



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

int count_same(string str1, string str2){
    int count{0};

    for(int i{0}; i<int(str1.size()); ++i){
        if(str1[i] == str2[i]){
            ++count;
        }
    }

    return count;
}

int main(void){
    string S, T;
    cin >> S >> T;
    int max_count{0};

    for(int i{0}; i<=int(S.size()-T.size()); ++i){
        int count = count_same(T, S.substr(i, T.size()));
        if(count > max_count){
            max_count = count;
        }
    }

    cout << T.size()-max_count << endl;


}


Measured memory_bytes: 3628
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class EGluttony {
public:
    static constexpr int kStressIterations = 0;

    static void generateTest(std::ostream& test) {
    }

    vector<int> A, F;
    int N, K;

    bool check(int x) {
        int cur = K;
        REP(i, N) {
            int v = x / F[i];
            v = max(0LL, A[i] - v);
            if (cur < v) {
                return false;
            }
            cur -= v;
        }
        return true;
    }

    void solve(std::istream& cin, std::ostream& cout) {
        cin >> N >> K;
        A.resize(N);
        F.resize(N);
        REP(i, N) cin >> A[i];
        REP(i, N) cin >> F[i];
        sort(A.begin(), A.end());
        sort(F.rbegin(), F.rend());

        int l = -1;
        int r = INF;
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }

        cout << r << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    EGluttony solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 3456
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include <time.h>
typedef long long ll;
typedef long double ld;
#define INF (1LL<<60)
/*swap 交換*/
void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
/*2つのうち大きい数を返す*/
ll max2(ll a,ll b){return a>=b?a:b;}
/*2つのうち小さい数を返す*/
ll min2(ll a,ll b){return a>=b?b:a;}
/*絶対値*/
ll ABS(ll a){return a>=0?a:(-a);}
typedef struct{
    ll aa;
    ll bb;
}frequent;
// 小大
int compare(const void *a, const void *b){return *(ll *)a - *(ll *)b;}

ll bisearch(ll x, ll l, ll r, ll n, ll a[n]){
    ll i;
    if(a[(l+r)/2]>x){
        if(r-l<2){
            for(i=r;i>=0;i--){
                if(a[i]<=x) break;
            }
            return n-i-1;
        }
        return bisearch(x,l,(l+r)/2,n,a);
    }else{
        if(r-l<2){
            for(i=r;i>=0;i--){
                if(a[i]<=x) break;
            }
            return n-i-1;
        }
        return bisearch(x,(l+r)/2,r,n,a);
    }

}
ll bisearcha(ll x, ll l, ll r, ll n, ll a[n]){
    ll i;
    if(a[(l+r)/2]<x){
        if(r-l<2){
            for(i=r;i>=0;i--){
                if(a[i]<x) break;
            }
            return i+1;
        }
        return bisearcha(x,(l+r)/2,r,n,a);
    }else{
        if(r-l<2){
            for(i=r;i>=0;i--){
                if(a[i]<x) break;
            }
            return i+1;
        }
        return bisearcha(x,l,(l+r)/2,n,a);
    }

}


int main(void){
    ll n,i,ans=0;
    scanf("%lld",&n);
    ll a[n],b[n],c[n],ab[n],bc[n];
    for(i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    for(i=0;i<n;i++){
        scanf("%lld",&b[i]);
    }
    for(i=0;i<n;i++){
        scanf("%lld",&c[i]);
    }
    qsort(a,n,sizeof(ll),compare);
    qsort(b,n,sizeof(ll),compare);
    qsort(c,n,sizeof(ll),compare);
    // ll marka=0,markb=0;
    for(i=0;i<n;i++){
        ab[i] = bisearcha(b[i],0,n-1,n,a);
        bc[i] = bisearch(b[i],0,n-1,n,c);
        // marka = ab[i];
        // markb = n-bc[i];
    }
    for(i=0;i<n;i++){
        ans+=ab[i]*bc[i];
    }
    
    // for(i=0;i<n;i++){
    //     printf("%lld %lld\n",ab[i],bc[i]);
    // }

    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 4848
#include<stdio.h>
#include<math.h>
int main()
{
  int N,D;
  double x[15][15]={};
  int i,j;
  int k,l;
  int counter=0;
  double distance;
  
  
  scanf("%d %d",&N,&D);
  for(i=0;i<N;i++)
  {
    for(j=0;j<D;j++)
    {
      scanf("%lf",&x[i][j]);
      //printf("%lf\n",x[i][j]);
    }
    //printf("\n");
  }
  
  for(i=0;i<N;i++)
    for(j=i+1;j<N;j++)
    {
      distance=0;
      for(k=0;k<D;k++)
      {
        distance+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
      }
      if(ceil(sqrt(distance))==floor(sqrt(distance)))
      {
        //printf("%lf",sqrt(distance));
        counter++;
      }
    }
  
  printf("%d",counter);
  return 0;
}

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

template<i64 M>
struct modint {
    i64 x;

    constexpr modint(const i64 y = 0) noexcept : x(y >= 0 ? y % M : (M - (-y) % M) % M) {}

    constexpr modint operator-() const noexcept { return modint(-x); }
    constexpr modint operator+(const modint &rhs) const noexcept { return modint(*this) += rhs; }
    constexpr modint operator-(const modint &rhs) const noexcept { return modint(*this) -= rhs; }
    constexpr modint operator*(const modint &rhs) const noexcept { return modint(*this) *= rhs; }
    constexpr modint operator/(const modint &rhs) const noexcept { return modint(*this) /= rhs; }

    constexpr modint &operator+=(const modint &rhs) noexcept {
        x += rhs.x;
        if (x >= M) x -= M;
        return *this;
    }

    constexpr modint &operator-=(const modint &rhs) noexcept {
        if (x < rhs.x) x += M;
        x -= rhs.x;
        return *this;
    }

    constexpr modint &operator*=(const modint &rhs) noexcept {
        x = x * rhs.x % M;
        return *this;
    }

    constexpr modint &operator/=(const modint &rhs) noexcept {
        i64 a = rhs.x, b = M, u = 1, v = 0;
        while (b > 0) {
            i64 t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        *this *= u;
        return *this;
    }

    friend ostream &operator<<(ostream &os, const modint &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, modint &a) {
        i64 t;
        is >> t;
        a = modint(t);
        return is;
    }
};

constexpr i64 MOD = 998244353;
using m64 = modint<MOD>;

template<typename T = m64>
struct combinatorics {
    vector<T> fac;

    combinatorics(i64 n): fac(2*n+1) {
        fac[0] = 1;
        for (i64 i = 1; i <= 2*n; i++) fac[i] = fac[i-1] * i;
    }

    T p(i64 n, i64 k) const {
        if (k < 0 || n < k) return 0;
        return fac[n] / fac[n-k];
    }

    T c(i64 n, i64 k) const {
        if (k < 0 || n < k) return 0;
        return fac[n] / (fac[k] * fac[n-k]);
    }

    T h(i64 n, i64 k) const {
        return c(n+k-1, k);
    }
};

void solve() {
    i64 n, a, b, k;
    cin >> n >> a >> b >> k;

    combinatorics<> c(n);
    m64 ans = 0;
    for (i64 x = 0; x <= n; x++) {
        i64 y = (k - a * x) / b;
        if (a * x + b * y != k || y > n) continue;
        ans += c.c(n, x) * c.c(n, y);
    }

    cout << ans << endl;
}

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


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

int top,S[1000];

void push(int x){
    S[++top]=x;
}

int pop(){
    top--;
    return S[top+1];
}

int main()
{
    top=0;
    int a,b;
    char s[100];
    while(scanf("%s",s)!=EOF){
        if(s[0]=='+'){
            a=pop();
            b=pop();
            push(a+b);
        }else if(s[0]=='-'){
            a=pop();
            b=pop();
            push(b-a);
        }else if(s[0]=='*'){
            a=pop();
            b=pop();
            push(a*b);
        }else if(s[0]=='/'){
            a=pop();
            b=pop();
            push(b/a);
        }else{
            push(atoi(s));
        }
    }

    cout<<pop()<<endl;
    return 0;
}

Measured memory_bytes: 3192
"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, d = map(int, read().split())
print(min(a, b) + min(c,d))


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

int main(void){
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int time = 0, temp = a;
    if (a < 0) {
        for (temp = a; temp < 0; temp++) {
            time += c;
            
        }
        temp = 0;
        time += d;
    }
    for(; temp < b; temp++) {
        time += e;
    }
    cout << time << endl;
}



Measured memory_bytes: 3100
#!/usr/bin/env python3
#ABC51 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n,m = map(int,input().split())
edge = [[] for _ in range(n)]
w = [[float('inf')]*n for _ in range(n)]
x = []
for _ in range(m):
    a,b,c = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    w[a-1][b-1] = c
    w[b-1][a-1] = c
    x.append([a,b,c])

for i in range(n):
    for j in range(n):
        for k in range(n):
            w[j][k] = min(w[j][k],w[j][i]+w[i][k])

ans = 0
for i in x:
    a,b,c = i
    if w[a-1][b-1] < c:
        ans += 1
print(ans)


Measured memory_bytes: 46828
M = 10**9+7

def getModInv(a, b):
    return 1 if (a == 1) else int((1-b*getModInv(b%a, a))/a%b)

def main():
    N, K = map(int, (input().split()))

    F = [1]*(N+1)
    k = 1

    for i in range(1, N+1):
        k *= i
        k %= M
        F[i] = k
        
    a = F[K-1]*F[N-K+1]%M
    for i in range(1, K+1):
        if N-K+1-i < 0:
            print(0)
            continue

        b1 = F[K-i]*F[i-1]%M
        b2 = F[N-K+1-i]*F[i]%M
        b = b1*b2%M

        print(a*getModInv(b, M)%M)

    

if __name__ == '__main__':
    main()


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

using ll = long long;

struct Ans {
    int N;
    int M;
    int u[60];
    int v[60];
    int w[60];
};

struct Ans solve(int L) {
    struct Ans ret;
    if (L < 3) {
        ret.N = 2;
        ret.M = L;
        rep(i, L) {
            ret.u[i] = 0;
            ret.v[i] = 1;
            ret.w[i] = i;
        }
        return ret;
    }
    if (L % 2 == 1) {
        ret = solve(L - 1);
        ret.u[ret.M] = 0;
        ret.v[ret.M] = ret.N - 1;
        ret.w[ret.M] = L - 1;
        ret.M++;
    } else {
        ret = solve(L / 2);
        ret.u[ret.M] = ret.N - 1;
        ret.v[ret.M] = ret.N;
        ret.w[ret.M] = 0;
        ret.u[ret.M + 1] = ret.N - 1;
        ret.v[ret.M + 1] = ret.N;
        ret.w[ret.M + 1] = L / 2;
        ret.N++;
        ret.M += 2;
    }
    return ret;
}

int main() {
    int L;
    cin >> L;
    struct Ans a = solve(L);
    cout << a.N << " " << a.M << endl;
    rep(i, a.M) cout << a.u[i] + 1 << " " << a.v[i] + 1 << " " << a.w[i] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<60)
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)cerr<<x[_]<<' ';cerr<<'\n',aaa
#define dbgs(x) cerr<<(#x)<<"[stl]: ";for(int _:x)cerr<<_<<' ';cerr<<'\n',aaa
#define dbgp(x) cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define int ll
#define maxn 300000

using namespace std;

int n, m, k;

struct AINT {
  int yy[4*maxn+5];
  void upd (int p, pii itv, int x, int val) {
    if (x < itv.fi || x > itv.se) return;
    if (itv.fi == itv.se) {
      yy[p] = val;
      return;
    }
    if (itv.fi < itv.se) {
      int mid = (itv.fi + itv.se) / 2;
      upd (p*2, pii(itv.fi, mid), x, val);
      upd (p*2+1, pii(mid+1, itv.se), x, val);
      yy[p] = max(yy[p*2], yy[p*2+1]);
    }
  }
  void pupd (int x, int val) {
    upd (1, pii(1,m), x, val);
  }
  int q_query;
  void qry (int p, pii itv, pii ok) {
    if (itv.se < ok.fi || ok.se < itv.fi) return;
    if (itv.fi >= ok.fi && itv.se <= ok.se) {
      q_query = max(q_query, yy[p]);
      return;
    }
    int mid = (itv.fi + itv.se) / 2;
    qry (p*2, pii(itv.fi, mid), ok);
    qry (p*2+1, pii(mid+1, itv.se), ok);
  }
  int pqry (pii ok) {
    q_query = 0;
    qry(1, pii(1,m), ok);
    return q_query;
  }
};

AINT aint;
pii v[maxn+5];
vi linii[maxn+5], coloane[maxn+5];
int sc[maxn+5];

signed main () {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n >> m >> k;
  int i, j, z;
  for (i = 1; i <= k; i++) {
    cin >> v[i].fi >> v[i].se;
    linii[v[i].fi].pb(i);
    coloane[v[i].se].pb(i);
  }
  for (j = 1; j <= m; j++) {
    sc[j] = sz(coloane[j]);
    aint.pupd(j, sc[j]);
  }
  int ans = 0, now;
  for (i = 1; i <= n; i++) {
    ///vreau sa pun bomba pe linia i
    now = sz(linii[i]);
    for (int x: linii[i]) {
      sc[v[x].se]--;
      aint.pupd(v[x].se, sc[v[x].se]);
    }
    ans = max(ans, now + aint.pqry(pii(1,m)));
    for (int x: linii[i]) {
      sc[v[x].se]++;
      aint.pupd(v[x].se, sc[v[x].se]);
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 51672
use proconio::input;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default)]
struct Struct;

//#[proconio::fastout]
fn main() {
    input! {
        d: usize,
        t: usize,
        s: usize,
    }

    println!("{}", if d <= t*s { "Yes" } else { "No" });
}


Measured memory_bytes: 2080
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

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

const int MX=200005;
char s[MX];
int n,dp[MX][2];

int f(int i,int c)
{
    if(i==n) return 0;
    if(s[i]!='?'){
        if(i){
            if(c) dp[i][c]=(s[i]=='P')?f(i+1,0):(1+f(i+1,1));
            else dp[i][c]=(s[i]=='P')?f(i+1,0):(2+f(i+1,1));
        }
        else{
            int p=(s[i]=='P')?0:1;
            dp[i][c]=f(i+1,p);
        }
        return dp[i][c];
    }
    if(dp[i][c]==-1){
        if(i){
            if(c) dp[i][c]=max(f(i+1,0),1+f(i+1,1));
            else dp[i][c]=max(f(i+1,0),2+f(i+1,1));
        }
        else dp[i][c]=max(f(i+1,0),1+f(i+1,1));
    }
    return dp[i][c];
}

void fun(int i,int c)
{
    if(i==n){
        printf("\n");
        return;
    }
    if(s[i]!='?'){
        printf("%c",s[i]);
        int p=(s[i]=='P')?0:1;
        fun(i+1,p);
    }
    else{
        if(i){
            if(c){
                int x=f(i+1,0),y=1+f(i+1,1);
                if(x>y){
                    printf("P");
                    fun(i+1,0);
                }
                else{
                    printf("D");
                    fun(i+1,1);
                }
            }
            else{
                int x=f(i+1,0),y=2+f(i+1,1);
                if(x>y){
                    printf("P");
                    fun(i+1,0);
                }
                else{
                    printf("D");
                    fun(i+1,1);
                }
            }
        }
        else{
            int x=f(i+1,0),y=1+f(i+1,1);
            if(x>y){
                printf("P");
                fun(i+1,0);
            }
            else{
                printf("D");
                fun(i+1,1);
            }
        }
    }
}

int main()
{
    scanf("%s",s);
    n=strlen(s);
    memset(dp,-1,sizeof(dp));
    int x=f(0,0);
    fun(0,0);
    return 0;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<string> data(H);
  for (int i=0; i<H; i++) {
    cin >> data.at(i);
  }
  vector<string> data2;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(data.at(i).at(j) == '#'){
        data2.push_back(data.at(i));
        break;
      }
    }
  }
  vector<int> B(W);
  for(int i=0;i<W;i++){
    for(int j=0;j<data2.size();j++){
      if(data2.at(j).at(i) == '#'){
        B.at(i) = 1;
        break;
      }
    }
  }
  for(int i=0;i<data2.size();i++){
    for(int j=0;j<W;j++){
      if(B.at(j) == 1){
        cout << data2.at(i).at(j);
      }
    }
    cout << endl;
  }
}

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

int main(){
    int n, k; cin >> n >> k;
    vector<double> p(200000);
    for(int i=0; i<n; i++) cin >> p[i];

    vector<int> sigma(1000);
    sigma[0] = 1;
    for(int i=1; i<1000; i++){
        sigma[i] = sigma[i-1]+(i+1);
    }
    for(int i=0; i<n; i++){
        p[i] = sigma[p[i]-1] / p[i];
    }
    double MAX = 0; 
    double tmp = 0; 
    for(int i=0; i<k; i++) tmp += p[i];
    MAX = tmp;
    for(int i=1; i<=n-k; i++){
        tmp = tmp - p[i-1] + p[i+k-1];
        if(tmp > MAX){
            MAX = tmp; 
        }
    }
    printf("%.12f\n", MAX);
    return 0;
}

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

using namespace std;

#define int long long

signed main(){
  int n, k; cin >> n >> k;
  vector<int > v(n);
  for(auto &it : v) cin >> it;
  
  sort(v.begin(), v.end());
  
  int x = n-k;
  int sum = 0;
  for(int i = 0; i < x; i++) sum += v[i];
  
  cout << sum;
  
  return 0;
}


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

int main() {
  char a,b,c,d; cin>>a>>b>>c>>d;
  if(a==b && a!=c && a!=d &&b!=c && b!=d){
    if(c==d)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  else if(a==c && a!=b && a!=d && c!=b && c!=d){
    if(b==d)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  else if(a==d && a!=b && a!=c && d!=b && c!=d){
    if(b==c)
      cout<<"Yes"<<endl;
    else
      cout<<"No"<<endl;
  }
  else
    cout<<"No"<<endl;
}

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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 1e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;


void solve()
{
    int N; cin >> N;
    vi p(N); REP(i, N) cin >> p[i];
    int ans = 0;
    REP(i, N) ans += p[i];
    cout << ans - (*max_element(ALL(p)) / 2) << endl;
}
    
int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}

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

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<long long int>>vec(n,vector<long long int>(2));
  for(int i=0;i<n;i++){
    for(int j=0;j<2;j++){
      cin>>vec.at(i).at(j);
    }
  }
  vector<long long int>vec1(n);
  for(int i=0;i<n;i++){
    vec1.at(i)=vec.at(i).at(0)*1000000+vec.at(i).at(1);
  }
  sort(vec1.begin(),vec1.end());
  long long int sum=0;
  for(int i=0;i<n;i++){
    if(vec1.at(i)%1000000<m){
      sum+=(vec1.at(i)/1000000)*(vec1.at(i)%1000000);
      m-=vec1.at(i)%1000000;
    }
    else{
      sum+=(vec1.at(i)/1000000)*m;
      break;
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 6656
a,b=map(int,input().split())
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

print(a*b//gcd(a,b))


Measured memory_bytes: 3060
list1 = [int(i) for i in input().split()]
l = list1[0]
r = list1[1]
if (l// 2019 != r//2019):
	print(0)
else:
	max1 = 10000000000
	if l - r >= 2019:
		for i in range(l,l+2020):
			for j in range(i+1,l+2020):
				temp = ((i%2019)*(j%2019))%2019
				if temp < max1 :
					max1 = temp
	else :
		for i in range(l,r+1):
			for j in range(i+1,r+1):
				temp = ((i%2019)*(j%2019))%2019
			
				if temp < max1 :
					max1 = temp
		
	print(max1)			

Measured memory_bytes: 3064