akhauriyash/Code-Regression huggingface dataset:
/*
      Ashraful Islam Paran
      27-August-2020
      10:17:31
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(n) for (int i = 0; i < n; i++)
#define fo(i, x, n) for (int i = x; i < n; i++)
#define fb(i, x, n) for (int i = n - 1; i <= 0; i--)
#define w(t) int t; cin >> t; while (t--)



typedef unsigned long long ull;
typedef vector<long long> vi;
#define ull unsigned long long
#define msi map<string, long long>
#define mii map<long long, long long>
const int MX = 2e5 + 5;
const int INF = 1e18;
#define pb push_back
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) x.begin(), x.end()
#define ff first
#define ss second


int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    // online submission
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n,l;
    cin>>n>>l;
    string s;
    vector<string> a;
    f(n)
    {
        cin>>s;
        a.pb(s);
    }
    sort(all(a));
    for(auto val:a)
    {
        cout<<val;
    }
    
    
    
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};

int main(){
    string s;
    cin>>s;
    ll n = s.size();
    ll k,ans=0;
    cin>>k;
    ll cnt=0, cnt2=0;
    bool flag = false;// 2kaime sentou wo kaeru
    bool flag2 = false;
    bool n1flag=false, n1flag2=false;

    for (int i = 1; i < n; i++)
    {
        if(s[i]==s[i-1])
        {
            cnt++;
            
            if(i==n-1)
            {
                n1flag = true;
            }
            i++;
        }
    }
    if(n1flag==false && s[0]==s[n-1])
    {
        flag = true;
    }
    for (int i = 0; i < n; i++)
    {
        if(i==0 || s[i]==s[i-1])
        {
            cnt2++;
            if(i==n-1)
            {
                n1flag2 = true;
            }
            i++;
        }
    }
    if(n1flag2==false && s[0]==s[n-1])
    {
        flag2 = true;
    }

    if(flag == false)
    {
        ans=cnt*k;
    }
    else
    {
        if(flag2==false)
        {
            ans = cnt*(k-k/2)+cnt2*(k/2);
        }
        else
        {
            ans = cnt+cnt2*(k-1);
        }
        
    }
    
    
    cout<<ans<<endl;
    return 0;
}

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

int main(){
    int N,A,B,C,D;
    cin >> N >> A >> B >> C >> D;
    string S;
    cin >> S;
    bool possible = true;
    if (C < D){
        for (int i = A - 1; i < C - 1; i++){
            if (S[i] == '#' && S[i + 1] == '#') possible = false;
        }
        for (int i = B - 1; i < D - 1; i++){
            if (S[i] == '#' && S[i + 1] == '#') possible = false;
        }
    }
    else{
        int count = 0;
        for (int i = B - 1; i <= D - 1; i++){
            if (S[i - 1] == '.' && S[i] == '.' && S[i + 1] == '.') count++;
        }
        for (int i = A - 1; i < C - 1; i++){
            if (S[i] == '#' && S[i + 1] == '#') possible = false;
        }
        for (int i = B - 1; i < D - 1; i++){
            if (S[i] == '#' && S[i + 1] == '#') possible = false;
        }
        if (count == 0) possible = false;
    }
    if (possible) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main(){
    int h,w;
    cin>>h>>w;
    int cnt=0;
    rep(i,h){
        string s; cin>>s;
        rep(j,w){
            if(s[j]=='#')cnt++;
        }
    }
    if(cnt==h+w-1)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
    return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a+b == c+d){
        cout << "Balanced" << endl;
    }
    else if(a+b >= c+d){
        cout << "Left" << endl;
    }
    else cout << "Right" << endl;

    return 0;
}


Measured memory_bytes: 256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define int ll

#define F first
#define S second
#define _sz(x) (int)x.size()
#define pb push_back

#define error(x) cout << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int N = 500 + 20;
int n, m, x, y;
int a[N][N];
ll sum;

int32_t main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	cin >> n >> m >> x >> y;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			if (i % x == x - 1 && j % y == y - 1)
				a[i][j] = -(x * y - 1) * 501 - 1;
			else 
				a[i][j] = 501;
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			sum += a[i][j];

	if (sum <= 0) return cout << "No\n", 0;

	cout << "Yes\n";
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << a[i][j] << ' ';
		cout << '\n';
	}
}


Measured memory_bytes: 3456
#include <cstdio>

using namespace std;

int main()
{
    int a1, a2, a3;
    scanf("%d", &a1);
    scanf("%d", &a2);
    scanf("%d", &a3);

    int sum = a1 + a2 + a3;
    if (sum >= 22) {
        printf("bust");
    }
    else {
        printf("win");
    }
    return 0;
}

Measured memory_bytes: 128
import sys
input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
mod = 10 ** 9 + 7

ans = 0

def make_tables(n, mod = 10 ** 9 + 7):
    fac = [1, 1] # 階乗テーブル
    finv = [1, 1] #逆元の階乗テーブル
    inv = [0, 1] #逆元テーブル

    for i in range(2, n + 1):
        fac.append((fac[-1] * i) % mod)
        inv.append((mod -inv[mod % i] * (mod//i)) % mod)
        finv.append((finv[-1] * inv[-1]) % mod)
    return fac, finv

def nCk(n, k, mod = 10 ** 9 + 7):
    k = min(k, n-k)
    return fac[n] * finv[k] * finv[n-k] % mod

if k >= n - 1:
    x = n
else:
    x = k + 1

fac, finv = make_tables(n)

for i in range(x):
    ans += (nCk(n, i) * nCk(n - 1, i)) % mod
    ans %= mod
print(ans)

Measured memory_bytes: 80880
#include <stdio.h>

int main(void) {
  int N;
  int max1 = 0, max2 = 0;
  scanf("%d", &N);
  int A[N];
  for (int n = 0; n < N; ++n) {
    scanf("%d", &A[n]);
    if (max2 < A[n]) max2 = A[n];
    if (max1 < max2) {
      int t = max2;
      max2 = max1;
      max1 = t;
    }
  }
  for (int n = 0; n < N; ++n) {
    printf("%d\n", (A[n] == max1) ? max2 : max1);
  }
  return 0;
}


Measured memory_bytes: 2304
n,k=map(int,input().split())

ans1=0
ans2=0

for i in range(1,n+1):
    if i%k==0:
        ans1+=1
    
    if i%k==k/2:
        ans2+=1

if k%2==0:
    print(ans1**3+ans2**3)
else:
    print(ans1**3)

Measured memory_bytes: 3060
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
place=[-1]*n
for i in range(n+1):
	if place[a[i]-1]==-1:
		place[a[i]-1]=i
	else:
		R=(place[a[i]-1],i)
		break
def c(a,b):
	if a==b==0:
		return 1
	if a<b or a<=0 or b<0:
		return 0
	r=fac[a-b]*fac[b]%mod
	return fac[a]*pow(r,mod-2,mod)%mod
fac=[1]
for i in range(n+1):
	fac.append(fac[-1]*(i+1)%mod)
for i in range(1,n+2):
	ans=(c(n+1,i)-c(R[0]+n-R[1],i-1))%mod
	print(ans)

Measured memory_bytes: 20756
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a , b;
  cin >> a >> b;
 
  if ( a*b % 2 ==1) {
    cout << "Odd" << endl;
  }
  else if ( a*b % 2 == 0) {
    cout << "Even" << endl;
  }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#define N 2010
using namespace std;
int n, K;
vector <int> g[N];
int a[N], b[N];

int dfs(int u, int fa, int dep){
	//printf("dep == %d K == %d\n", dep, K);
	int ret = dep > K ? 1 : 0;
	for (int i = 0; i < g[u].size(); ++ i){
		int v = g[u][i];
		if (v == fa)  continue;
		ret += dfs(v, u, dep + 1);
	}
	return ret;
}

int main(){
	int i, j, x, y, T;
	T = 1;
	while (T --){
		scanf("%d%d", &n, &K);
		for (i = 1; i <= n; ++ i) g[i].clear();
		for (i = 1; i < n; ++ i){
			scanf("%d%d", &x, &y);
			a[i] = x, b[i] = y;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		int ans = n;
		if (K % 2){
			K = K / 2;
			for (i = 1; i < n; ++ i)
				ans = min(ans, dfs(a[i], b[i], 0) + dfs(b[i], a[i], 0));
		}
		else {
			K /= 2;
			for (i = 1; i <= n; ++ i)
				ans = min(ans, dfs(i, i, 0));
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

using namespace std;

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

    long long r = 0, g = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R')
            r++;
        else if (s[i] == 'G')
            g++;
        else
            b++;
    }

    long long ans = r*g*b;

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int k = j+(j-i);
            if (k < n && s[i] != s[j] && s[j] != s[k] && s[k] != s[i])
                ans--;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3640
# B
s = input()
l = [chr(i) for i in range(97, 97+26)]

bool = True
for i in range(len(l)):
    ans = s.count(l[i])
    if ans <= 1:
        continue
    else:
        bool = False
        break
        
if bool:
    print('yes')
else:
    print('no')

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws Exception {
    try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
      int answer = eval(reader.readLine());
      System.out.println(answer);
    }
  }

  static int eval(String s) {
    int len = s.length();
    if (len == 1)
      return 0;
    return Math.min(diff(len, s, gen(false, len)), diff(len, s, gen(true, len)));
  }

  static char[] gen(boolean high, int length) {
    char[] chars = new char[length];
    for (int i = 0; i < length; ++i) {
      chars[i] = high ? '1' : '0';
      high = !high;
    }
    return chars;
  }

  static int diff(int length, String a, char[] b) {
    int diffs = 0;
    for (int i = 0; i < length; ++i) {
      if (a.charAt(i) != b[i])
        ++diffs;
    }
    return diffs;
  }


}


Measured memory_bytes: 25556
import math
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

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

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def prime_fact(a): #素因数分解
    sqrt = math.sqrt(a)
    res = []
    i = 2
    if is_prime(a):
        res.append(a)
    else:
        while a!=1:
            while a%i==0:
                res.append(i)
                a //= i
            i += 1
    return res

def main():
    a,b = map(int,input().split())
    x = a + b
    if x<24:
        print(x)
    else:
        print(x-24)
    return

if __name__=='__main__':
    main()


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

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

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>

using namespace std;

typedef long long in;

int main(){
    in n,a,b;
    cin >> n >> a >>b;
    if(b<a){
        cout << 0 << endl;
    }
    else if(n-2<0){
        if(a==b){
            cout << 1 << endl;
        }
        else
            cout << 0 << endl;
        return 0;
    }
    else{
        cout << (b-a)*(n-2)+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define NewNode (ListNode *)malloc(sizeof(ListNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const unsigned long long mod = 998244353;
const double II = 3.1415926535;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll n,m,sum = 0;
    cin >> n >> m;
    for(int i = 0,a;i < m;i++)
    {
        cin >> a;
        sum += a;
    }
    if(sum > n)
        cout << -1 << endl;
    else
        cout << n-sum << endl;
}


Measured memory_bytes: 3652
from itertools import combinations
 
n = int(input())
 
count = {x:0 for x in "MARCH"}
 
for _ in range(n):
  s = input()[0]
  if s in count:
    count[s] += 1
 
sum_count = 0
for a, b, c in combinations("MARCH", 3):
  sum_count += count[a] * count[b] * count[c]
 
print(sum_count)

Measured memory_bytes: 3060
#include<stdio.h>
long long int len(char *str){
	long long int i,count=0;
	for(i=0;str[i]!='\0';i++){
		count++;
		}
	return count;
	
	}
int main(){
	char a[1000000],b[1000000],c[1000000];
	long long int x,y;
	scanf("%s%s%s",a,b,c);
	x=len(a);
	y=len(b);
	//z=len(c);
	if(a[x-1]==b[0]&&b[y-1]==c[0])printf("YES\n");
	else printf("NO\n");
	}


Measured memory_bytes: 2176
#include <iostream>

using namespace std;

int main(){
    long long int N,K;
    cin >> N >> K;
    long long int ans=0;
    long long int upper = N/K;
    long long int semiup = 2 * N / K;
    if(K % 2 == 1){
        ans = upper * upper * upper;
    }
    else {
        ans = (semiup-upper)* (semiup-upper) * (semiup-upper) + upper * upper * upper;

    }
    cout << ans << endl;
}

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

using namespace std;

int n;
vector<vector<pair<int,int> > > tree(100005);
int ans[100005]={};

void solve(int color,int id,int p){
  ans[id]=color;
  for(int i=0;i<tree[id].size();++i){
    if(tree[id][i].first==p) continue;
    if(tree[id][i].second%2==0) solve(color,tree[id][i].first,id);
    else solve(1-color,tree[id][i].first,id);
  }
}

int main() {
  cin >> n;
  int u,v,w;
  for(int i=0;i<n-1;++i){
    cin >> u >> v >> w;
    u--,v--;
    tree[u].push_back(make_pair(v,w));
    tree[v].push_back(make_pair(u,w));
  }
  
  solve(0,0,-1);

  for(int i=0;i<n;++i)
    cout << ans[i] << endl;
  
  return 0;
}


Measured memory_bytes: 9088
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  vector<ll> A(N);
  ll maxnum=-big, minnum=big;
  for(int i=0;i<N;++i) {
    cin>>A[i];
  }
  sort(A.begin(), A.end());
  maxnum = A[N-1];
  minnum = A[0];
  ll ans1 = minnum, ans2 = maxnum;
  for(int i=1;i<N-1;++i) {
    if(A[i]>=0) {
      ans1 = ans1 - A[i];
    }
    else {
      ans2 = ans2 - A[i];
    }
  }
  ll ans = ans2 - ans1;
  cout<<ans<<endl;
  ans1 = minnum;
  ans2 = maxnum;
  for(int i=1;i<N-1;++i) {
    if(A[i]>=0) {
      cout<<ans1<<" "<<A[i]<<endl;
      ans1 -= A[i];
    }
    else {
      cout<<ans2<<" "<<A[i]<<endl;
      ans2 -= A[i];
    }
  }
  cout<<ans2<<" "<<ans1<<endl;
}



Measured memory_bytes: 4016
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

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


  string str; cin >> str;


  ll ans = 0;
  ll now = 0;
  rep(i,str.size()){
    now += str[i]-'0';
    ll a = now-1 + (str.size()-i-1)*9;
    if(ans < a)
      ans = a;

  }
  cout << max(ans, now ) << endl;

  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) (a*a)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int main() {
	string str[3];
	REP(i, 3)cin >> str[i];
	REP(i, 3)cout << str[i][0];
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
lst = [input() for _ in range(n)]
lstset = set(lst)

if len(lst) != len(lstset):
    print("No")
else:
    cnt = 0
    for i in range(n-1):
        if lst[i][-1] == lst[i + 1][0]:
            cnt += 1
        else:
            break
    if cnt + 1 == len(lst):
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 3060
N = int(input())
C = list(input())
C_ = sorted(C)

wr = rw = 0
for i in range(len(C_)):
    if C[i] != C_[i]:
        if C[i] == 'R' and C_[i] == 'W':
            rw += 1
        else:
            wr += 1

print(max(wr, rw))


Measured memory_bytes: 12700
//

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

vector<double> P(4000);
vector<vector<double>> dp(4000,vector<double>(4000));

int main() {
    fastio
    ll N;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>P[i];
    }
    dp[0][0]=1;
    for(int i=1;i<=N;i++){
        for(int j=0;j<i;j++){
            if(j==0){
                dp[i][j] = dp[i-1][j]*(1-P[i-1]);
                continue;
            }
            dp[i][j] = dp[i-1][j] * (1-P[i-1]) + dp[i-1][j-1] * P[i-1];
        }
        dp[i][i] = dp[i-1][i-1] * P[i-1];
    }
    int i = (N+1)/2;
    double ans=0;
    for(i=i;i<=N;i++){
        ans+=dp[N][i];
    }
    cout<<fixed<<showpoint;
    cout<<setprecision(10)<<ans<<"\n";
    return 0;
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;

void solve()
{
	string s;
	cin >> s;

	int q;
	cin >> q;

	int t;
	bool reverse = false;

	deque<char> d;
	for(int i = 0; i < s.length(); ++i)
	{
		d.push_back(s[i]);
	}

	for(int i = 0; i < q; ++i)
	{
		cin >> t;
		if (t == 1)
		{
			reverse = !reverse;
		}
		else if (t == 2)
		{
			int f;
			char c;
			cin >> f >> c;
			if (f == 1)
			{
				if (reverse)
				{
					d.push_back(c);
				}
				else
				{
					d.push_front(c);
				}
			}
			else if (f == 2)
			{
				if (reverse)
				{
					d.push_front(c);
				}
				else
				{
					d.push_back(c);
				}
			}
		}
	}

	string ans = "";
	if (reverse)
	{
		while(!d.empty())
		{
			ans += d.back();
			d.pop_back();
		}
	}
	else
	{
		while(!d.empty())
		{
			ans += d.front();
			d.pop_front();
		}
	}
	cout << ans;
}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 1492
INF = 10 ** 12

N, W = map(int, input().split())

items =[] * N

for i in range(N):
    v, w = map(int, input().split())
    items.append([v,w])

dp = [[INF for i in range(W+1)] for j in range(N+1)]

for i in range(W+1):
    dp[0][i] = 0

for i in range(N+1):
    dp[i][0] = 0

for i in range(1,N+1): #1<= i <= N
    for j in range(1, W+1): # 1 <= j <= W
        if j - items[i-1][1] >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - items[i-1][1]] + items[i-1][0], dp[i][j - items[i-1][1]] + items[i-1][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

Measured memory_bytes: 18288
#include <bits/stdc++.h>
using namespace std;
int k[100005],b[100005],arr[100005];
int main() {
    int n, m;
    cin >> n >> m;
    k[1] = 1;
    for(int i = 1 ; i <= n ; i++)
        b[i] = 1;
    for(int i = 1 ; i <= m ; i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        b[x]--;
        b[y]++;
        if(k[x] == 1 && b[x] > 0)
        {
            k[y] = 1;
        }
        else if(k[x] == 1 && b[x] <= 0)
        {
            k[y] = 1;
            k[x] = 0;
        }
    }
    int tutmac = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        if(k[i] >= 1)
        {
            tutmac++;
        }
    }
    cout << tutmac;
}

Measured memory_bytes: 1024
h, _ = map(int, input().split())

r = range(10)
c = [[int(i) for i in input().split()] for _ in r]

for k in r:
    for i in r:
        for j in r:
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
else:
    a = [[int(i) for i in input().split()] for _ in range(h)]
    print(sum(c[i][1] for i in sum(a, []) if i != -1))

Measured memory_bytes: 10280
def divisor(N):
    div = []
    for i in range(1, int(N ** 0.5 + 1)):
        if N % i == 0:
            div.append(i)
            if i * i != N:
                div.append(N // i)
    return sorted(div)


N = int(input())
ans = 11
for div in divisor(N):
    ans = min(ans, max(len(str(div)), len(str(N // div))))

print(ans)

Measured memory_bytes: 3060
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  int n, m, x, y;
  cin >> n >> m >> x >> y;
  vector<int> v(n), w(m);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  for (int i = 0; i < m; i++)
    cin >> w[i];
  int z = x;
  for (int i = 0; i < n; i++)
    z = max(z, v[i]);
  z++;
  bool yes = true;
  if (z > y)
    yes = false;
  for (int i = 0; i < m; i++)
    if (z > w[i])
      yes = false;
  if (yes)
    cout << "No War" << endl;
  else
    cout << "War" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define ll long long
#define NUM 1000000007
int prime[500];
int main(void){
	int n;
    int ptr=0;
    ll ans=1;
    prime[ptr++]=2;
	scanf("%d",&n);
	for(int i=3;i<=n;i+=2){
	    int flag=0;
	    for(int j=0;prime[j]*prime[j]<=i;j++){
	        if(i%prime[j]==0){
	            flag=1;
	            break;
	        }
	    }
	    if(!flag) prime[ptr++] = i;
	}
	for(int i=0;i<ptr;i++){
	    int p=prime[i];
	    int count=0;
	    while(p<=n){
	        count += n/p;
	        p *= prime[i];
	    }
	    ans = ans*(count+1)%NUM;
	}
	printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
  int n, ans = 0;
  cin >> n;
  for(int i=1; i<=n; i++){
    int digit = to_string(i).length();
    if(digit%2){
      ans ++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>

using namespace std;

#define mod 1000000007

int main()
{
	int n, m, l, k, a, h;
	while(1){
		cin >> n >> m >> l >> k >> a >> h;
		if(n == 0) break;
		int needtime[101][101];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				needtime[i][j] = mod;
			}
		}
		vector<int> hospital;
		for(int i = 0; i < l; i++){
			int tmp;
			cin >> tmp;
			hospital.push_back(tmp);
		}
		hospital.push_back(h);
		for(int i = 0; i < k; i++){
			int x, y, t;
			cin >> x >> y >> t;
			needtime[x][y] = t;
			needtime[y][x] = t;
		}
		for(int k = 0; k < n; k++){
			for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					needtime[i][j] = min(needtime[i][j], needtime[i][k] + needtime[k][j]);
				}
			}
		}
		priority_queue<pair<int, pair<int, int> > > qu;
		vector<int> result(101, mod);
		qu.push(make_pair(0, make_pair(a, m)));
		while(!qu.empty()){
			int nowtime = -(qu.top()).first;
			int nowplace = ((qu.top()).second).first;
			int resttime = ((qu.top()).second).second;
			qu.pop();
			if(result[nowplace] <= nowtime) continue;
			// cout << nowtime << " " << nowplasce << " " << resttime << endl;
			result[nowplace] = nowtime;
			for(int i = 0; i < l + 1; i++){
				int nextplace = hospital[i];
				if(needtime[nowplace][nextplace] > m) continue;
				int nexttime = nowtime + needtime[nowplace][nextplace];
				if(resttime >= needtime[nowplace][nextplace]){
					qu.push(make_pair(-nexttime, make_pair(nextplace, resttime - needtime[nowplace][nextplace])));
				} else {
					int freezetime = needtime[nowplace][nextplace] - resttime;
					qu.push(make_pair(-(nexttime + freezetime), make_pair(nextplace, 0)));
				}
			}
		}
		if(result[h] == mod) cout << "Help!" << endl;
		else cout << result[h] << endl;
	}
	return 0;
}

Measured memory_bytes: 3220
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, H, W = mapint()
cnt = 0
for _ in range(N):
    a, b = mapint()
    if a>=H and b>=W:
        cnt += 1
    else:
        continue
print(cnt)

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

int main(int argc, char const *argv[])
{
	string s; cin >> s;
	int ans = 1000;
	rep(i, s.size() - 2) {
		int d = stoi(s.substr(i, 3));
		ans = min(ans, abs(753 - d));
	}
	cout << ans << endl;
	return 0;
}


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

public class AtCoderA
{
    static void Main()
    {
        int h;
        int w;
        {
            var line = Console.ReadLine();
            var words = line.Split(' ');
            h = int.Parse(words[0]);
            w = int.Parse(words[1]);
        }

        bool[,] map = new bool[h, w];
        for (int i = 0; i < h; i++)
        {
            var line = Console.ReadLine();
            for (int j = 0; j < w; j++)
            {
                if (".".Equals(line.Substring(j, 1)))
                {
                    map[i, j] = true;
                }
            }
        }

        long[,] answer = new long[h, w];

        answer[0, 0] = map[0, 0] ? 0 : 1;
        for (int i = 1; i < w; i++)
        {
            if (map[0, i] == false && map[0, i - 1] == true)
            {
                answer[0, i] = answer[0, i - 1] + 1;
            }
            else
            {
                answer[0, i] = answer[0, i - 1];
            }
        }
        for (int i = 1; i < h; i++)
        {
            if (map[i, 0] == false && map[i - 1, 0] == true)
            {
                answer[i, 0] = answer[i - 1, 0] + 1;
            }
            else
            {
                answer[i, 0] = answer[i - 1, 0];
            }
        }

        for (int i = 1; i < h; i++)
        {
            for (int j = 1; j < w; j++)
            {
                long up = answer[i - 1, j];
                if (map[i, j] == false && map[i - 1, j] == true)
                {
                    up++;
                }
                long left = answer[i, j - 1];
                if (map[i, j] == false && map[i, j - 1] == true)
                {
                    left++;
                }
                answer[i, j] = Math.Min(up, left);
            }
        }

        Console.WriteLine(answer[h - 1, w - 1]);
    }
}

Measured memory_bytes: 11124
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int64_t n, k;
    cin>>n>>k;
    if(n % k == 0)
    {
        cout<<"0"<<endl;
    }
    else
    {
        int64_t x = n % k; // 3, 2
        int64_t y = abs(k - x); //1, 4
        if(y > x) // 1>4 false, 4>2 true
        {
            cout<<x<<endl;//k>x
        }
        else if(y <= x) //true,true
        {
            cout<<y<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
using namespace std;
using ll = long long;
#define MAX 10000
#define NIL -1

struct Node {
    int parent, left, right;
};

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d) {
    if (u == NIL) return;
    D[u] = d;
    setDepth(T[u].left, d + 1);
    setDepth(T[u].right, d + 1);
}

int setHeight(int u) {
    int h1 = 0, h2 = 0;
    if (T[u].left != NIL) h1 = setHeight(T[u].left) + 1;
    if (T[u].right != NIL) h2 = setHeight(T[u].right) + 1;
    return H[u] = max(h1, h2);
}

int getSibling(int u) {
    if (T[u].parent == NIL) return NIL;
    if (T[T[u].parent].left != u && T[T[u].parent].left != NIL) return T[T[u].parent].left;
    if (T[T[u].parent].right != u && T[T[u].parent].right != NIL) return T[T[u].parent].right;
    return NIL;
}

void print(int u) {
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].parent);
    printf("sibling = %d, ", getSibling(u));
    int deg = 0;
    if (T[u].left != NIL) ++deg;
    if (T[u].right != NIL) ++deg;
    printf("degree = %d, ", deg);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);
    if (T[u].parent == NIL) printf("root\n");
    else if (T[u].left == NIL && T[u].right == NIL) printf("leaf\n");
    else printf("internal node\n");
}

int main() {
    int v, l, r, root = 0;
    scanf("%d", &n);
    rep(i, n) T[i].parent = NIL;
    rep(i, n) {
        scanf("%d %d %d", &v, &l, &r);
        T[v].left = l;
        T[v].right = r;
        if (l != NIL) T[l].parent = v;
        if (r != NIL) T[r].parent = v;
    }
    rep(i, n) if (T[i].parent == NIL) root = i;
    setDepth(root, 0);
    setHeight(root);
    rep(i, n) print(i);
    return 0;
}


Measured memory_bytes: 3240
n=int(input())
arr=list((map(int, input().split(" "))))
arr.insert(0, 0)
arr.append(0)
total=0
for k in range(len(arr)-1):
    total+=abs(arr[k]-arr[k+1])
for i in range(len(arr)-2):
    diff=abs(arr[i+2]-arr[i+1])+abs(arr[i+1]-arr[i])-abs(arr[i+2]-arr[i])
    print(total-diff)


Measured memory_bytes: 14048
#include "bits/stdc++.h"
using namespace std;

/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define isin(a, b, c) (b <= a && a <= c)
#define println cout << "\n";
#define sz(v) (int)v.size()
#define bin(x) static_cast<bitset<16> >(x)


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef tuple<int, int, int> ti;
typedef map<int, int> mi;
typedef set<int> si;


/* constant */
const int inf = 1LL << 62;
const int mod = 1e9 + 7;
const int dx[8]={1,0,-1,0,-1,1,-1,1};
const int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alphabet = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T, class U, class V> void printx(tuple<T, U, V> t){cout << "{" << get<0>(t) << "," << get<1>(t) <<"," << get<2>(t) << "}" << endl;}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}
template<class T> void printans(vec<T> v){rep(i,0,sz(v)){cout << v[i] << (i == sz(v) - 1 ? "" : " ");}cout << endl;}


/* general_method */
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; }
template<class T>T cut(T &a, int l, int r){return T(a.begin()+l, a.begin()+r);}


/* math_method */
int ceil(int a, int b){return a / b + (a % b > 0);}


/* main */

int k;
void in(){
    cin >> k;
}

void solve(){

    vi ans(50, 49);

    int cnt = k / 50;
    rep(i,0,50){
        ans[i] += cnt;
    }

    rep(i,0,k % 50){
        ans[i] += 51;
    }
    rep(i,0,50){
        ans[i] -= k % 50;
    }
    print(50);
    printans(ans);

}

signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);
    in();
    solve();
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
const int MAX_N = 100000;
int prime[MAX_N];
bool is_prime[MAX_N + 1];
void pre(){
    int n = MAX_N;
    memset(prime, 0, sizeof(prime));
    rep(i, n + 1) is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;
    int p = 0;
    REP(i, 2, n + 1)
      if(is_prime[i]){
          prime[p++] = i;
          for(int j = 2 * i; j <= n; j += i)
            is_prime[j] = false;
      }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    pre();
    int N;
    while(cin >> N && N){
        int sum = 0, it = 0, ans = 0;
        queue<int> que;
        for(; sum < N && it < MAX_N; it++){
            sum += prime[it];
            que.push(prime[it]);
        }
        for(; it < MAX_N && prime[it - 1] <= N; it++){
            while(sum > N){
                sum -= que.front();
                que.pop();
            }
            if(sum == N) ans++;
            sum += prime[it];
            que.push(prime[it]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1708
#include<iostream>
using namespace std;
long long x;
double a;
int tot;
int main()
{
    cin>>x;
    a=100;
    while(a<x)
    {
        a=a*1.01;
        long long t=a;
        a=t;
        tot++;
    }
    cout<<tot;
    return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
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; }
ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a*b/gcd(a,b);}
ll MOD=1000000007;

int main(){
  int n,m;
  cin>>n>>m;
  vi a(m+1);
  rep(i,m) cin>>a.at(i);
  vector<ll> dp(n+1,0);
  dp.at(0)=1;
  int j=0;
  if(a.at(0)==1){
    j++;
    dp.at(1)=0;
  }else{
    dp.at(1)=1;
  }
  for(int i=2;i<n+1;i++){
    if(i==a.at(j)){
      j++;
      continue;
    }
    dp.at(i)=dp.at(i-1)%MOD+dp.at(i-2)%MOD;
  }

  cout<<dp.at(n)%MOD<<endl;
}

Measured memory_bytes: 1408
from collections import deque

n,limit = map(int,input().split())
queue = deque()
total_time = 0

for _ in range(n):
    p,cost = input().split()
    queue.append([p,int(cost)])

while len(queue) > 0:
    head = queue.popleft()
    if   head[1] <= limit:
        total_time += head[1]
        print('{} {}'.format(head[0],total_time))
    elif head[1] > limit:
        head[1] -= limit
        total_time += limit
        queue.append(head)


Measured memory_bytes: 13272
package main

import (
  "fmt"
)

func main(){
  var a,b string
  fmt.Scan(&a, &b)
  if a == b {
    fmt.Println("EQUAL")
  } else if a > b && len(a) >= len(b) {
    fmt.Println("GREATER")
  } else {
    fmt.Println("LESS")
  }
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
typedef long long ll;
ll MOD = 1e9+7;

using namespace std;

int main()
{
	string s;
	int ans=0;
	char c='a';
	bool al[26];
	fill(al,al+26,false);
	
	cin>>s;
	sort(s.begin(),s.end());

	int i=0;
	c=s[0];
	al[c-'a']=true;
	while(i<s.length())
	{
		while(s[i]==c)
		{
			i++;
		}
		c=s[i];
		al[c-'a']=true;
	}
	for(int i=0;i<26;i++)
	{
		if(!al[i])
		{
			char a='a'+i;
			cout<<a<<endl;
			return 0;
		}
	}
	cout<<"None"<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;

inline bool cheak(ll x, ll y, ll xMax, ll yMax){ return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline ll toInt(string s) { ll v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }

#define For(i,a,b)	for(ll (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define rFor(i,a,b)	for(ll (i) = (a-1);i >= (b);(i)--)
#define rrep(i,n)	rFor(i,n,0)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define sz(a)		(sizeof(a))

const ll dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const ll mod = 1e9 + 7;
const ll INF = 1e9 + 9;

int main(){

	int n, m;

	while (cin >> n >> m && n){
		vector<T> vec(m);
		vector<bool> inv(n+1, false);
		inv[1] = true;
		rep(i, m){
			cin >> get<0>(vec[i]) >> get<1>(vec[i]) >> get<2>(vec[i]);
		}
		sort(all(vec));
		rep(i, m){
			int s = get<1>(vec[i]), t = get<2>(vec[i]);
			if (inv[s])inv[t] = inv[s];
		}
		int ans = 0;
		rep(i, inv.size()){
			if (inv[i])ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1988
local ffi=require"ffi"
local modint
do
local MOD=1000000007
local mt={}
modint=setmetatable({new=function(x)return setmetatable({v=x},mt)end},{__call=function(o,x)return setmetatable({v=x%MOD},mt)end})
local function add(a,b)return (a+b)%MOD end
function mt.__add(a,b) return modint.new(add(a.v,b.v))end
local function sub(a,b)return (a-b)%MOD end
function mt.__sub(a,b) return modint.new(sub(a.v,b.v))end
local function mul(a,b)
	local ret=0
	while(b>0)do
		if(b%2==1)then ret=(ret+a)%MOD end
		a=(a+a)%MOD
		b=math.floor(b*.5)
	end
	return ret
end
function mt.__mul(a,b)
	a=a.v b=b.v
	return modint(a<b and mul(b,a)or mul(a,b))
end
local function pow(a,b)
	local ret=1
	while(b>0)do
		if(b%2==1)then ret=mul(ret,a)end
		a=mul(a,a)
		b=math.floor(b*.5)
	end
	return ret
end
function mt.__pow(a,b)return modint(pow(a.v,b.v))end
local function inv(x)
local a=x
local b,u,v=MOD,1,0
repeat
local t=math.floor(a/b)
a,b=b,a-t*b
u,v=v,u-t*v
until(b==0)
return u
end
local function div(a,b)return mul(a,inv(b))end
function mt.__div(a,b)return modint.new(div(a.v,b.v))end
function mt.__tostring(x)return tostring(x.v)end
local method={}
mt.__index=method
function method.inv(x)return modint.new(inv(x.v))end
do
local MAX=510000
local ct=ffi.typeof("int[$]",MAX)
local fac=ffi.new(ct,{1,1})
local inv=ffi.new(ct,{1,1})
local finv=ffi.new(ct,{1,1})
for i=2,MAX-1 do
fac[i]=mul(fac[i-1],i)
inv[i]=MOD-mul(inv[MOD%i],math.floor(MOD/i))
finv[i]=mul(finv[i-1],inv[i])
end
function method.C(n,k)
n=n.v k=k.v
if(n<k)then return 0 end
return mul(mul(finv[k],finv[n-k]),fac[n])
end
end
end --modint define

N=io.read"*n"
K=io.read"*n"

r=modint(0)
for i=K,N+1 do
local min=i*(i-1)/2
local max=(N-i+1+N)*i/2
r=r+modint(max-min+1)
end
print(r)






Measured memory_bytes: 11372
import sys
input = sys.stdin.buffer.readline

n, m = map(int, input().split())
AB = []
for i in range(n):
    a, b = map(int, input().split())
    AB.append((a, b))
#AB.sort(key = lambda x:(-x[0], -x[1]))
AB.sort(reverse=True)
#print(AB)

h = []
import heapq
heapq.heapify(h)
ans = 0
for i in reversed(range(m)):
    while AB:
        a, b = AB.pop()
        if i+a > m:
            AB.append((a, b))
            break
        else:
            heapq.heappush(h, (-b, a))
    #print(i, h)
    if h:
        b, a = heapq.heappop(h)
        b = b*(-1)
        ans += b
print(ans)


Measured memory_bytes: 67676
#include <cstdio>
const int mo=1000000007;
int f[3005],r[3005],a[3005];
char s[3005];
int main(){
	int n,m;
	scanf("%d%d\n%s",&n,&m,s+1);
	for (int i=1;i<=n;i++) r[i]=i,a[i]=a[i-1]+s[i]-'0';
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d\n",&x,&y);
		if (y>r[x]) r[x]=y;
	}
	f[0]=1;
	for (int i=1,R=0;i<=n;i++){
		R=r[i]>R?r[i]:R;
		for (int j=a[R]<i?a[R]:i;j>=0;j--)
			if (j<a[R]-R+i) f[j]=0;
				else if (j) (f[j]+=f[j-1])%=mo;
	}
	printf("%d\n",f[a[n]]);
}

Measured memory_bytes: 256
//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define endl "\n"
#define X first
#define Y second
#define pii pair<int,int>
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)

const int maxn=1e5+5;
const int mod=1e9+7;
const ll inf=8e18;
const int del=728729;

ll poww(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));}
ll n ;
ll h ;
ll a[maxn];
ll b[maxn];
ll dp[10000+5][10000+5];
ll z=0;
int main(){
	migmig;
	cin >> h >> n;
    for(int i =0 ;i < n ; i++){
    	cin>>a[i]>>b[i];
	}
	for(int i = 0 ; i <= n+5 ; i++){
    	for(int j = 0 ; j <= h+5; j++){
    		dp[i][j]=inf;
    	}
    }
    dp[0][0]=0;
    for(int i = 0 ; i <= n+5 ; i++){
    	for(int j = 0 ; j <= h+5; j++){
			dp[i+1][j]=min(dp[i][j],dp[i+1][max(j-a[i],z)]+b[i]);
			//cout<<dp[i+1][j]<<endl;;
		}
	}
	cout<<dp[n][h]<<endl;
	return 0;
}



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

class Program
{
    static long mod = 1000000007;

    static long pow(long x, long k, long mod) {
        k %= mod-1;
        long r = 1;
        while(k>0) {
            if((k&1)>0) r = (r*x)%mod;
            k>>=1;
            x = x*x%mod;
        }
        return r;
    }
    
    static void Main()
    {
        var str = Console.ReadLine().Split(new char[] {' '});
        long N = long.Parse(str[0]), K = long.Parse(str[1]);

        var D = new List<long>[K+1];
        for(long i=1; i<=K; ++i) D[i] = new List<long>();

        var X = new long[K+1];
        
        for(long d=1; d<=K; ++d) {
            for(long c=2; c*d<=K; ++c) D[c*d].Add(d);
            X[d] = pow(K/d, N, mod); //(K/d)**N % mod;
        }

        long ans = 0;
        for(long d=K; d>=1; --d) {
            foreach(var i in D[d]) {
                X[i] -= X[d];
                X[i] %= mod;
            }
            ans += X[d]*d%mod;
        }

        Console.WriteLine(ans%mod);

    }


}


Measured memory_bytes: 50848
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>
using namespace std;
const int N = 1e5+5;
char s[N],t[N];
int nxt[N][26];

int main(){
	scanf("%s%s",s,t);
	int ls = strlen(s);
	memset(nxt[ls],-1,sizeof(nxt[0]));
	for(int i=ls-1;~i;--i){
		memcpy(nxt[i], nxt[i+1], sizeof(nxt[0]));
		nxt[i][s[i]-'a'] = i+1;
	}
	long long ans = 0;
	int i=0;
	char *p = t;
	while(*p){
		int n = nxt[i][*p-'a'];
		if(n == -1){
			if(i==0){
				printf("-1\n");
				return 0;
			}
			else{
				ans += ls - i;
				i = 0;
			}
		}
		else{
			ans += n-i;
			i = n;
			++p;
		}
	}
	printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 10624
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define INF 100100100

using namespace std;

int main()
{
    int N;
    vector<int> t;
    vector<int> cumt;
    vector<int> v;
    t.push_back(0);
    cumt.push_back(0);
    cumt.push_back(0);
    v.push_back(0);
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int ti;
        cin >> ti;
        ti *= 2;
        t.push_back(ti);
        cumt.push_back(cumt[i + 1] + ti);
    }
    for (int i = 0; i < N; i++)
    {
        int vi;
        cin >> vi;
        v.push_back(vi * 2);
    }
    t.push_back(0);
    v.push_back(0);
    cumt.push_back(*(cumt.end() - 1));

    int T = *(cumt.end() - 2);

    int vs = 0.0;
    int ve;
    int ans = 0;
    for (int i = 0; i < T; i++)
    {
        int minv = INF;
        for (int j = 0; j < N + 3; j++)
        {
            int limv;
            int curt = i + 1;
            if (curt <= cumt[j])
            {
                limv = v[j] + cumt[j] - curt;
            }
            else if (cumt[j] <= curt && curt <= cumt[j + 1])
            {
                limv = v[j];
            }
            else if (cumt[j + 1] <= curt)
            {
                limv = v[j] + curt - cumt[j + 1];
            }

            minv = min(minv, limv);
        }
        if (vs + 1 <= minv)
        {
            ve = vs + 1;
        }
        else if (vs == minv)
        {
            ve = vs;
        }
        else
        {
            ve = vs - 1;
        }
        ans += vs + ve;
        vs = ve;
    }

    cout << setprecision(15) << ans / 8.0 << endl;

    return 0;
}

Measured memory_bytes: 256