akhauriyash/Code-Regression huggingface dataset:
import math

if __name__ == "__main__":
    rectangle = 0
    diamond = 0
    while True:
        try:
            x,y,z = map(int,raw_input().split(","))

            if x == y:
                diamond += 1

            if (pow(x,2)+pow(y,2)) == pow(z,2):
                rectangle += 1

        except EOFError:
            break

    print rectangle
    print diamond

Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>

using namespace std;

int main(){
	int a,b,c;
	cin >> a >> b >> c;
	int ans=a*b/2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import bisect
 
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
 
for i in range(n):
  for j in range(i+1,n):
    temp=l[i]+l[j]
    ans+=(bisect.bisect_left(l,temp)-j-1)
print(ans)

Measured memory_bytes: 3188
import os, sys, re, math, queue

N,K = list(map(int,input().split(' ')))
ans = []

if (N-1)*(N-2) < 2*K:
	print('-1')
	sys.exit()

for i in range(2,N+1):
	ans.append('1 ' + str(i))

for i in range(2, N):
	for j in range(i+1, N+1):
		ans.append(str(i) + ' ' + str(j))

limit = N - 1 + (N-1)*(N-2)//2 - K
print(limit)
for k in range(limit):
	print(ans[k])


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

int A,B,C,D;

int main(){
	cin>>A>>B>>C>>D;

if(A+B<C+D) cout<<"Right"<<endl;
else if (A+B>C+D) cout<<"Left"<<endl;
else if (A+B==C+D) cout<<"Balanced"<<endl;

return 0;
}

Measured memory_bytes: 3556
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;



int main()
{
    char x,y;
    cin >> x >> y;
    if((x-'0') > (y - '0')) cout << '>' << endl;
    else if((x-'0') < (y - '0')) cout << '<' << endl;
    else cout << '=' << endl;
 
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define N 1000
using namespace std;
int c[N],s[N],f[N];
int main(){
//	freopen ("1.in","r",stdin);
	int n;
	scanf ("%d",&n);
	for (int i=1;i<n;++i) scanf ("%d%d%d",&c[i],&s[i],&f[i]);
	for (int i=1;i<n;++i){
		int la=1;
		for (int j=i;j<n;++j){
			la=max(la,s[j]);
			la=((la-1)/f[j]+1)*f[j]+c[j];			
		}
		printf ("%d\n",la);
	}
	printf ("%d\n",0);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
  #define debug(...) printf(__VA_ARGS__)
#else
  #define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAX = 1e6 + 100;
int cnt2[MAX];

int main() {
  cnt2[0] = 0;
  for (int i = 1; i < MAX; i++) {
    int t = i, c = 0;
    while (t % 2 == 0 && t > 0) {
      t /= 2;
      c++;
    }
    cnt2[i] = cnt2[i - 1] + c;
  }

  int N;
  cin >> N;
  string S;
  cin >> S;
  for (char &c : S) {
    c--;
  }
  bool ex1 = false;
  for (char c : S) {
    if (c == '1')
      ex1 = true;
  }

  if (ex1) {
    // 0 or 1
    for (char &c : S) {
      if (c == '2')
        c = '0';
    }
  }
  int r = 0;
  for (int i = 0; i < SZ(S); i++) {
    assert(cnt2[SZ(S) - 1] - cnt2[i] - cnt2[SZ(S) - 1 - i] >= 0);
    if (S[i] > '0') {
      if (cnt2[SZ(S) - 1] - cnt2[i] - cnt2[SZ(S) - 1 - i] == 0)
        r ^= 1;
    }
    debug("%d %d -> %d\n", SZ(S), i, cnt2[SZ(S) - 1] - cnt2[i] - cnt2[SZ(S) - 1 - i] == 0);
  }
  if (r) {
    if (ex1)
      puts("1");
    else
      puts("2");
  } else {
    puts("0");
  }
  return 0;
}


Measured memory_bytes: 5252
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
        	String[] pairstr = input.nextLine().split(",");
        	int[] pairs = new int[pairstr.length];
        	for(int i = 0 ; i < pairstr.length ; i++){
        		pairs[i] = Integer.parseInt(pairstr[i]);
        	}
        	/*for(int i = 0 ; i < pairs.length ; i++){
        		if(pairs[i]==("A")){
        			pairs[i] = "1";
        		}else if(pairs[i]==("K")){
        			pairs[i] = "13";
        		}else if(pairs[i]==("Q")){
        			pairs[i] = "12";
        		}else if(pairs[i]==("J")){
        			pairs[i] = "11";
        		}
        	}*/
        	Arrays.sort(pairs);
        	System.out.println(order(pairs));
        }
    }

    public static String order(int[] pairs){
    	if(pairs[0]==pairs[3] || pairs[1]==pairs[4])return "four card";
    	if((pairs[0]==pairs[1] && pairs[2]==pairs[4]) || (pairs[0]==pairs[2] && pairs[3]==pairs[4]))return "full house";
    	if(pairs[0]+1 == pairs[1] && pairs[1]+1 == pairs[2] && pairs[2]+1 == pairs[3] && pairs[3]+1 == pairs[4])return "straight";
    	if(pairs[0] == 1 && pairs[1] == 10 && pairs[2] == 11 && pairs[3] == 12 && pairs[4] == 13)return "straight";
    	if(pairs[0]==pairs[2] || pairs[1]==pairs[3] || pairs[2]==pairs[4])return "three card";
    	if((pairs[0]==pairs[1] && pairs[2]==pairs[3]) || (pairs[0]==pairs[1] && pairs[3]==pairs[4]) || (pairs[1]==pairs[2] && pairs[3]==pairs[4]))return "two pair";
    	if(pairs[0]==pairs[1] || pairs[1]==pairs[2] || pairs[2]==pairs[3] || pairs[3]==pairs[4])return "one pair";
    	return "null";
    }
}

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


int main() {
    int N; 
    cin >> N;
    vector<int> vec(N);
    int sum=0;
    int m=0;
    for(int i=0; i<N; i++){
        cin >> vec.at(i);
        sum += vec.at(i);
        m = max(m,vec.at(i));
    }
    cout << sum - m/2 << endl;
}

Measured memory_bytes: 256
N = int(input())
A = []
B = []
for i in range(N):
  a, b = map(int, input().split())
  A.append([a, b])
for i in range(N):
  a, b = map(int, input().split())
  B.append([a, b])
A = sorted(A, key=lambda x: (-x[1]))
B = sorted(B, key=lambda x: (x[0]))
count = 0
for i in range(len(B)):
  for j in range(len(A)):
    if A[j][0] < B[i][0] and A[j][1] < B[i][1]:
      A = A[:j] + A[j+1:]
      count += 1
      break
print(count)

Measured memory_bytes: 38896
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
struct __test {} test;
using namespace std;
template <typename T>const __test &operator<<(const __test& d,
const T& v) {return cerr << "\033[31m" << v << "\033[0m",d;}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

const int N = 1e5+5;
ll s[N],b[N];
int n,k;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		int a;
		cin >> a;
		s[i] = s[i-1]+a;
		b[i] = b[i-1] + (a>0)*a;
	}
	ll A = -(1LL<<60);
	for(int i = k; i <= n; ++i) {
		A = max(A,b[i-k]-b[0] + s[i]-s[i-k] + b[n]-b[i]);
		A = max(A,b[i-k]-b[0] + b[n]-b[i]);
	}
	cout << A << "\n";
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
    map<int,bool> m;
    for(int i=1;i<10;i++)for(int j=1;j<10;j++)m[i*j]=1;
    int n;cin>>n;
    if(m[n])cout<<"Yes"<<endl;
    else cout<<"No";
    
}

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

using namespace std;
int n;

bool check(int x){
    string s = to_string(x);
    if(s.find('3') != string::npos && s.find('5') != string::npos &&s.find('7') != string::npos){
        return true;
    }else{
        return false;
    }
}

int dfs(int k, int x){
    if(k == 0){
        if(check(x) && n >= x) return 1;
        else return 0;
    }
    int res = 0;
    res += dfs(k - 1, x * 10 + 3);
    res += dfs(k - 1, x * 10 + 5);
    res += dfs(k - 1, x * 10 + 7);
    return res;
}

int main(){
	int ans = 0;
	cin >> n;
    int t = 3, q = 1000;
    while(q <= n){
        ans += pow(3, t) - (3 * pow(2, t) - 3);
        t++;
        q *= 10;
    }
    q /= 10;
    ans += dfs(to_string(q).size(), 0);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
using namespace std;
int main(void){
   int n;
   cin >> n;
   vector<int> ans(10050);
   
   for(int i = 1;i <= 105;i++){
         for(int j = 1;j <= 105;j++){
               for(int k = 1; k <= 105;k++){
                     int v = i * i + j * j + k * k + i * j + j * k + i * k;
                     if(v < 10050)ans[v]++;
               }
         }
   }
   for(int i = 1;i <= n;i++){
         cout << ans[i] << endl;
   }
}


Measured memory_bytes: 3588
Tenant = [[[0]*10 for j in range (3)] for i in range (4)]
n = int(input())

for i in range(n):
    b, f, r, v = map(int, input().strip().split())
    Tenant[b-1][f-1][r-1] += v

count = 0
for i in range(4):
    if count != 0:
        print('#'*20)
    count += 1

    for j in range(3):
        for k in range(10):
            print(' {}'.format(Tenant[i][j][k]), end='')
        print()


Measured memory_bytes: 5628
#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

template<ll mod>
struct ModInt{
  using M=ModInt;
  ll a;
  M& put(ll v){
    a=(v<mod)?v:v-mod;
    return *this;
  }
  ModInt(ll v=0){put(v%mod+mod);}
  M operator+(M x){return M().put(a+x.a);}
  M operator-(M x){return M().put(a+mod-x.a);}
  M operator*(M x){return M().put(a*x.a%mod);}
  M operator/(M x){return *this*x.inv();}
  M& operator+=(M x){return *this=*this+x;};
  M& operator-=(M x){return *this=*this-x;};
  M& operator*=(M x){return *this=*this*x;};
  M& operator/=(M x){return *this=*this/x;};
  bool operator==(M x){return a==x.a;}

  M pow(ll m){
    M x=*this,res=1;
    while(m){
      if(m&1)res*=x;
      x*=x;
      m>>=1;
    }
    return res;
  }
  M inv(){return pow(mod-2);}
};

using Int = ModInt<MOD>;

int N;
vector<LL> hs;
Int fact = 1;

struct Val {
  Int dp1;
  Int dp2;
};

struct Val Calc(vector<LL> &hs) {
  LL mh = 1LL << 40;
  for (LL h : hs) {
    MN(mh, h);
  }

  struct Val ret = {1, 1};
  vector<LL> vec;
  int w = 0;
  for (LL h : hs) {
    h -= mh;
    if (h > 0) {
      vec.eb(h);
    } else {
      ++w;
      assert(h == 0);
      if (vec.size()) {
        auto res = Calc(vec);
        ret.dp2 *= res.dp2 + res.dp1;
        ret.dp1 *= res.dp1;
      }
      vec.clear();
    }
  }

  if (vec.size()) {
    auto res = Calc(vec);
    ret.dp2 *= res.dp2 + res.dp1;
    ret.dp1 *= res.dp1;
  }

  Int g = Int(2).pow(w);
  ret.dp2 *= g;
  //cout << ret.dp1.a << ", " << ret.dp2.a << endl;
  Int t = Int(2).pow(mh);
  ret.dp2 += ret.dp1 * (t-2);
  ret.dp1 *= t;
  //cout << ret.dp1.a << ", " << ret.dp2.a << endl;
  return ret;
}

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  cin >> N;
  rep(i, N) {
    LL h;
    cin >> h;
    hs.eb(h);
  }
  cout << (fact*Calc(hs).dp2).a << endl;
}


Measured memory_bytes: 384
while True:
   n,x=map(int,input().split())
   if n==0 and x==0:
      break
   s=[0]*3
   a=0
   for i in range(1,n+1):
      for j in range(i,n+1):
         for k in range(j,n+1):
            if i+j+k==x and i!=j and j!=k and k!=i:
               s[0]=i
               s[1]=j
               s[2]=k
               a+=1
   print(a)


Measured memory_bytes: 5600
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    long long A, B, C;
    cin >> A >> B >> C;
    
    int res =0;
    
    if (A == B && B == C && A % 2 == 0) res = -1;
    else {
        while (A % 2 == 0 && B % 2 == 0 && C % 2 ==0) {
            long long a = A;
            long long b = B;
            long long c = C;
            
            A = (b + c)/2;
            B = (a + c)/2;
            C = (a + b)/2;
            ++res;
        }
    }
    
    cout << res << endl;  
    
}

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

long long x(long long a) {
    if (a % 4 == 0) return a;
    if (a % 4 == 1) return 1;
    if (a % 4 == 2) return a + 1;
    return 0;
}
int main() {
    long long a, b;
    cin >> a >> b;
    cout << (x(b) ^ x(a - 1)) << endl;
}


Measured memory_bytes: 256
// Shinchan Loves Coding :)))
#include<bits/stdc++.h>
#include<map>
#include<set>
#include<stack>
using namespace std;

#define night_rider ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long int
#define double long double
#define en "\n"
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define toUpper(x) transform(x.begin(), x.end(), x.begin(),::toupper);
#define toLower(x) transform(x.begin(), x.end(), x.begin(),::tolower);
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef pair<int,int> pi;
typedef vector<pair<int,int>> pii;
bool secdes(const pair<int,int>&a , const pair<int,int>&b){if(a.se==b.se){return a.fi>b.fi;}else{return a.se>b.se;}}//second descending !
bool sir(const pair<int,int>&a , const pair<int,int>&b){if(a.fi==b.fi){return a.se>b.se;}else{return a.first>b.first;}}//first descending !
bool bysec(const pair<int,int>&a , const pair<int,int>&b){if(a.se==b.se){return a.fi<b.fi;} else{return a.se<b.se;}}//second ascending !

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

const int no=3e6+5;
const int modulo=1e9+7;
const int inf=1e18;
const int N=1001;
int a[no],b[no],cc[no],dd[no],mat[N][N];
stack<int> S;
stack<int> ma;
int dx[]={-1 , 0 , 1 , 0};
int dy[]={0 , 1 , 0 , -1};
char c[N][N];

//--------------------------------------------------------------------------------------------------------------------------------------------------------------
int mul(int x , int y , int mod) {
    return ((x%mod)*(y%mod))%mod;
}

int powwmod(int x, int y , int mod) { int res=1; while (y) { if (y & 1){ y--; res=mul(res,x,mod); res%=mod; } else { y/=2; x=mul(x,x,mod); x%=mod; } } return res%mod; }

int poww(int x , int y) { int res=1; while(y) { if(y%2) { y--; res=res*x; } else { y/=2; x=x*x; } } return res; }

int div(int x , int y , int mod) {
    return x*poww(y,mod-2)%mod ;
}

bool comp(int x, int y) {
    return (x < y);   // MINIMUM
    return (x > y);   // MAXIMUM
}

int gcd(int x, int y) { if(y==0) return x; else return gcd(y,x%y); }

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

pii adj[no];
int dist[no];

void solve (){
    int n,m,k=0,x,y,z,p,q;
    cin>>n;
    for(int i=0 ; i<n ; i++) {cin>>a[i];k+=a[i];k%=modulo;}
    int prev=0;
    int ans=0;
    for(int i=0 ; i<n ; i++) {
        ans+=((((k-(prev+a[i]))%modulo+modulo)%modulo*a[i])%modulo);
        prev+=a[i];
        prev=prev%modulo;
    }
    cout<<ans%modulo<<en;
}

void runn(){
        #ifndef ONLINE JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        #endif
}

signed main()
{
    night_rider
    //runn();
    int t=1;
   // cin>>t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 75472
def f(n):
    if n % 2 == 0:
        return int(n / 2)
    else:
        return 3 * n + 1


if __name__ == "__main__":
    s = int(input())

    a = s
    arr = [s]
    for i in range(1000000):
        a = f(a)
        if a in arr:
            print(len(arr) + 1)
            break
        arr.append(a)

Measured memory_bytes: 3060
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):M<t[2*i]or v[t[2*i]-1].append(t[2*i+1])
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

Measured memory_bytes: 24932
// 愚直に2重ループ
//
//   https://kimiyuki.net/writeup/algo/atcoder/arc-092-d/
// で紹介されている
//   https://atcoder.jp/contests/arc092/submissions/2242270
//   https://atcoder.jp/contests/arc092/submissions/2251371
// を参考に、
//   #pragma GCC optimize ("-O3", "unroll-loops")
//   __attribute__((target("avx")))
// を指定した。これで3秒以内に間に合った。
// ("avx2"の指定だとRE)
//
// さらに追加で、アラインメントを保証してメモリ確保した
// (参考: https://stackoverflow.com/questions/15067119/how-can-i-use-simd-to-accelerate-xor-two-blocks-of-memory)

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple


#pragma GCC optimize ("-O3", "unroll-loops")

__attribute__((target("avx"))) int main(void)
{
    cin.sync_with_stdio(false);
    int N;
    scanf("%d", &N);

    int* As = (int*)aligned_alloc(128, N * 4);
    int* Bs = (int*)aligned_alloc(128, N * 4);

    REP(n, N) scanf("%d", &As[n]);
    REP(n, N) scanf("%d", &Bs[n]);

    int ans = 0;
    int i = 0;
    for( ; i < (N / 8) * 8; i += 8) {
        int a0 = As[i];
        int a1 = As[i + 1];
        int a2 = As[i + 2];
        int a3 = As[i + 3];
        int a4 = As[i + 4];
        int a5 = As[i + 5];
        int a6 = As[i + 6];
        int a7 = As[i + 7];
        for(int j = 0; j < N; j++) {
            int b = Bs[j];
            ans ^= a0 + b;
            ans ^= a1 + b;
            ans ^= a2 + b;
            ans ^= a3 + b;
            ans ^= a4 + b;
            ans ^= a5 + b;
            ans ^= a6 + b;
            ans ^= a7 + b;
        }
    }
    for( ; i < N; i++) {
        int a = As[i];
        for(int j = 0; j < N; j++) {
            ans ^= a + Bs[j];
        }
    }
    cout << ans << endl;
    free(As);
    free(Bs);
    return 0;
}


Measured memory_bytes: 1792
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int w = scan.nextInt();
		int a = scan.nextInt();
		int b = scan.nextInt();
		if((a-w)<=b&&b<=(a+w)){
			System.out.println("0");
		}
		else if(a<(b-w)){
			System.out.println(b-(a+w));
		}
		else if((b+w)<a){
			System.out.println(a-(b+w));
		}
	}
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
 
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, s, n, m) for(ll i = s; i < (ll)(n); i+=m)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e5)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;

template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) 
{ 
    for (int i = 0; i < (int)v.size(); ++i) { 
        os << v[i]; 
        if (i != (int)v.size() - 1) 
            os << " "; 
    } 
    return os; 
} 

int main()
{
    ll N;
    cin >> N;
    vector<ll> A(N);
    double sum = 0;
    rep(i, 0, N, 1) { 
        cin >> A[i];
        sum += 1. / A[i];
    }
    print(1 / sum);
    return 0;
}

Measured memory_bytes: 256
#import<iostream>
using namespace std;main(){unsigned long Q,a,b,c,d,M{205891132094649UL};cin>>Q;const auto& C=[&M](auto a,auto b,auto c,auto d){auto u{b},l{b},p{M};while(p/=3)if((a/p+(4-a/p%3)%3)*p<=c){if(u/p%3==1)u=u/(3*p)*3*p+2*p;if(l/p%3==1)l=l/(3*p)*3*p+p-1;}return c-a+min(u-b+max(u,d)-min(u,d),b+d-2*l);};while(Q--){cin>>a>>b>>c>>d;if(--a>--c)swap(a,c),swap(b,d);if(--b>--d){b=M-b-1;d=M-d-1;}cout<<max(C(a,b,c,d),C(b,a,d,c))<<endl;}}

Measured memory_bytes: 384
import java.util.*;
 
public class Main{
  public static void main(String[]args){
    Scanner sc =  new Scanner(System.in);
    String[] S = sc.nextLine().split(" ");
    int N = Integer.parseInt(S[0]);
    int K = Integer.parseInt(S[1]);
    if(N>=K){
      System.out.println(0);
      return;
    }
    
    List<Integer> list1 = new ArrayList<>();
    String[] T = sc.nextLine().split(" ");
    for(int i = 0; i < K; i++){
      list1.add(Integer.parseInt(T[i]));
    }
    Collections.sort(list1);
    
    List<Integer> list2 = new ArrayList<>();
    for(int i = 0; i < K-1; i++){
      list2.add(list1.get(i+1)-list1.get(i));
    }
    Collections.sort(list2, Collections.reverseOrder());
    
    for(int i = 0; i < N-1 && list2.size() > 0; i++){
      list2.remove(0);
    }
    int ans = 0;
    for(int i = 0; i < list2.size(); i++){
      ans += list2.get(i);
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 48732
// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

struct InitIO {
    InitIO() {
        cin.tie(nullptr);
        ios_base::sync_with_stdio(false);
        cout << fixed << setprecision(30);
    }
} init_io;

}

#ifdef DEBUGGING
// #include "../debug/debug.cpp"
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

int main() {
    ll K, X;
    cin >> K >> X;
    V<ll> ans;
    ll lower = max<ll>(-1000000, X - (K - 1));
    ll upper = min<ll>(1000000, X + (K - 1));
    for(ll i = lower; i <= upper; i++) cout << i << ' ';
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    long M = 1_000_000_007;
    int N = scanner.nextInt();
    int K = scanner.nextInt();
    int[] a = new int[N];
    for (int i = 0; i < N; i++) a[i] = scanner.nextInt();

    long[][] dp = new long[N][K + 1];
    for (int i = 0; i <= a[0]; i++) dp[0][i] = 1;
    for (int i = 1; i < N; i++) {
      long sum = 0;
      for (int j = 0; j <= K; j++) {
        sum += dp[i - 1][j];
        if (j > a[i]) sum -= dp[i - 1][j - a[i] - 1];
        if (sum > M) sum -= M;
        if (sum < 0) sum += M;
        dp[i][j] = sum;
      }
    }
    System.out.println(dp[N - 1][K]);
  }
}


Measured memory_bytes: 127828
package main

import "fmt"

func main() {
	//変数の定義
	var N, A int
	//変数の読み込み %dは整数を表す。
	fmt.Scanf("%d %d", &N, &A)

	if N%A == 0 {
		fmt.Println(N / A)
	} else {
		fmt.Println(N/A + 1)
	}

}


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

const ll mod = 1e9 + 7;

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    ll a;
    cin >> a;
    cout << a + a * a + a * a * a;
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

void solve() {
	int n;
	cin >> n;
	
	vi a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	
	vi ans(n);
	for(int i = 0; i < n; i++) ans[a[i] - 1] = i + 1;
	
	for(int i : ans) cout << i << " ";
	cout << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}

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

int main(void)
{
    int N;
    cin >> N;
    long power{1};
    for(long i{1}; i<=N; ++i){
        power *= i;
        power = power % 1000000007;
    }
    cout << power << endl;
}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int r = sc.nextInt();
            int c = sc.nextInt();
            int q = sc.nextInt();
            if ((r | c | q) == 0)
                break;
            Query qs[] = new Query[q];
            for (int i = 0; i < q; i++) {
                qs[i] = new Query(sc.nextInt(), sc.nextInt(), sc.nextInt());
            }
            Set<String> set = new HashSet<String>();
            long stand_r = 0;
            long stand_c = 0;
            long sit_r = 0;
            long sit_c = 0;
            long ans = 0;
            for (int i = q - 1; i >= 0; i--) {
                if (set.contains(qs[i].toString()))
                    continue;
                set.add(qs[i].toString());
                if (qs[i].a == 1) {
                    if (qs[i].o == 0) {
                       sit_r++;
                    } else {
                       stand_r++;
                        ans += r;
                        ans -= sit_c;
                        ans -= stand_c;
                    }

                } else {
                    if (qs[i].o == 0) {
                        sit_c++;
                    } else {
                        stand_c++;
                        ans += c;
                        ans -= sit_r;
                        ans -= stand_r;
                    }
                }
            }
            System.out.println(ans);
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }
}

class Query {
    int a;
    int b;
    int o;

    Query(int a, int b, int o) {
        this.a = a;
        this.b = b;
        this.o = o;
    }

    public String toString() {
        return "a:"+a + "," + "b:"+b;
    }
}

Measured memory_bytes: 20000
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int N,W;
int table[50005],ruisekiwa[50005];
bool check[50005];

bool one_line_check(int left,int right){ //left～rightの単語を一行に詰め込めるか

	if(ruisekiwa[right]-ruisekiwa[left-1]+(right-left) <= W){
		return true;
	}else{
		return false;
	}
}

bool put_check(int left,int right,int limit){

	if(right == N)return true; //最終文字は、右端に詰めなくて良い

	if(ruisekiwa[right]-ruisekiwa[left-1]+limit*(right-left) >= W){
		return true;
	}else{ //★★各幅を全てlimitにしても、一行の文字数に足りない→少なくとも一か所、limit+1以上のスペースを入れなければならない!!
		return false;
	}
}


bool is_OK(int limit){

	if(one_line_check(1,N))return true;

	check[0] = true;
	bool FLG;

	int left_start = 1;

	for(int right_id = 1; right_id <= N; right_id++){ //右端のループ
		while(left_start <= right_id && one_line_check(left_start,right_id) == false || check[left_start-1] == false)left_start++;
		FLG = false;
		for(int left_id = left_start; left_id <= right_id; left_id++){
			if(check[left_id-1] == false)continue;
			if(put_check(left_id,right_id,limit) == true){
				FLG = true;
				break;
			}else{
				break;
			}
		}
		check[right_id] = FLG;
		if(check[right_id]){
			if(right_id == N || one_line_check(right_id+1,N) == true){
				return true;
			}
		}
	}

	return false;
}

void func(){

	ruisekiwa[0] = 0;
	for(int i = 1; i <= N; i++){
		scanf("%d",&table[i]);
		ruisekiwa[i] = table[i];
		ruisekiwa[i] += ruisekiwa[i-1];
	}

	int left = 1,right = W,m = (left+right)/2;
	int ans = W;

	while(left <= right){
		if(is_OK(m)){
			ans = m;
			right = m-1;
		}else{
			left = m+1;
		}
		m = (left+right)/2;
	}

	printf("%d\n",ans);

}

int main(){

	while(true){
		scanf("%d %d",&W,&N);
		if(W == 0 && N == 0)break;

		func();
	}

	return 0;
}



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

#include <bits/stdc++.h>

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define ll long long int

int main(){
    int n;
    cin>>n;
    vector<vector<int>> a(n,vector<int> (3));
    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++)cin>>a[i][j];
    }
    vector<vector<int>> dp(n,vector<int> (3));
    dp[0]=a[0];
    for(int i=1;i<n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(j!=k){
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
                }
            }
        }
    }
    cout<<*max_element(dp[n-1].begin(),dp[n-1].end())<<"\n";
    return 0;
}


Measured memory_bytes: 14020
import java.io.PrintWriter;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int sx = Integer.parseInt(sc.next());
		int sy = Integer.parseInt(sc.next());
		int tx = Integer.parseInt(sc.next());
		int ty = Integer.parseInt(sc.next());
		int h = ty - sy;
		int w = tx - sx;
		int[] c = {w, h, 1, h + 1, w + 1, h + 1, w, 1, w + 1, h + 1, 1};
		String[] s = {"R","U","R","D","L","U","R","U","L","D","R"};
		for (int i = 0; i < 11; i++)
			for (int j = 0; j < c[i]; j++)
				out.print(s[i]);
		out.flush();
	}
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

    int n = s.size();
    for(int i = 0; i < n / 2; i++) {
        int j = n - 1 - i;
        if(s[i] != s[j]) {
            cout << "No" << endl;
            return 0;
        }
    }

    for(int i = 0; i < (n - 1) / 4; i++) {
        int j = (n - 1) / 2 - i - 1;
        if(s[i] != s[j]) {
            cout << "No" << endl;
            return 0;
        }
    }

    for(int i = (n + 2) / 2; i < n; i++) {
        int j = n - 1 - (i - (n + 2) / 2);
        if(s[i] != s[j]) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
 int W, H, x, y, r;

 scanf("%d",&W);

 scanf("%d",&H);

 scanf("%d",&x);

 scanf("%d",&y);

 scanf("%d",&r);

 if(x>=W || x<=0){
  printf("No\n");
 }
 else if(y>=H || y<=0){
  printf("No\n");
 }
 else if(x+r>W || x-r<0){
  printf("No\n");
 }
 else if(y+r>H || y-r<0){
  printf("No\n");
 }
 else{
 printf("Yes\n");
 }

 return 0;
}
 

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

int main (void) {
  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N)
    cin >> A[i];
  int negs = 0;
  for (const auto& x : A) {
    if (x < 0)
      negs++;
  }
  ll ans = 0;
  for (const auto& x : A)
    ans += abs(x);
  if (negs % 2 != 0) {
    ll minabs = 1e9;
    for (const auto& x : A)
      minabs = min(minabs, abs(x));
    ans -= 2 * minabs;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
package main

import "fmt"

func main() {
	var a, b, c, d int
	fmt.Scan(&a, &b, &c, &d)

	for {
		c -= b
		if c <= 0 {
			fmt.Println("Yes")
			return
		}
		a -= d
		if a <= 0 {
			fmt.Println("No")
			return
		}
	}
}


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

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

    int d=1;
    rep(i,n){
        if(d<=k)d=d*2;
        else d=d+k;
    }
    cout<<d<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
  using namespace std;
  #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define ll  long long
  #define ld long double
  #define pb push_back
  #define mp3 make_pair
  #define rep1(i,a,b) for(ll i=a;i<=b;i++)
  #define rep2(i,a,b) for(ll i=a;i<b;i++)
  const ll  mod=998244353;
  template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
  template<typename T> T add(T a,T b,ll m){a+=b;while(a>=0)a-=m;while(a<0)a+=m; return a;}
  template<typename T> T mul(T a,T b,ll m){return (a*1ll*b)%m;}

 int main(){
   IOS;
  ll n,k,x;
  cin>>n>>k>>x;
  ll p=n/k;
  if(n%k!=0)
  p++;
  cout<<p*x<<endl;
 }

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s,t;cin>>s>>t;
    ll n=s.length(),m=t.length();
    ll dp[n+1][m+1];
    for(int i=0;i<=n;++i)
    {
        dp[i][0]=0;
    }
    for(int i=0;i<=m;++i)
    {
        dp[0][i]=0;
    }
    for(int i=0;i<=n;++i)
    {
        for(int j=0;j<=m;++j)
        {
            dp[i][j]=0;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(s[i-1]!=t[j-1])
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
            else
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
        }
    }
    //cout<<dp[n][m]<<endl;
    if(dp[n][m]==0)
    {
        cout<<" \n";
        return 0;
    }
    string ans="";
    int ti=n,tj=m;
    while(ti>0 && tj>0)
    {
        
        if(s[ti-1]==t[tj-1])
        {
            ans+=s[ti-1];
            ti--;tj--;
        }
        else if(dp[ti][tj-1]>=dp[ti-1][tj])
        {
            tj--;
        }
        else
        {
            ti--;
        }
        
        
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[(" << __LINE__ << ") " << #x << "]: " << (x) << endl;

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

    ll n, x, MOD;
    cin >> n >> x >> MOD;

    vector<pair<ll, int>> m(MOD+1);

    ll ans = 0;
    ll i=1;
    while (!m[x].second && i <= n) {
        m[x] = {ans, i++};
        ans += x;
        x = x*x % MOD;
    }

    n -= i;
    if (n < 0) { 
        cout << ans << "\n";
        return 0;
    }
    ll duh = n / (i-m[x].second);
    ans += duh * (ans-m[x].first);
    n %= i-m[x].second;
    n++;

    while (n-- > 0) {
        ans += x;
        x = x*x % MOD;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 4780
#include <iostream>

int main(){
  int a , b;
  char op;

  std::cin >> a >> op>> b;

  while (op != '?') {
    /* code */
    if (op == '+') {
      /* code */
      std::cout << a + b<< '\n';
    }else if(op == '-'){
      std::cout << a - b<<'\n';

    }else if(op == '*'){
      std::cout << a*b <<'\n';
    }else if(op == '/'){
      std::cout << a/b<< '\n';
    }
    std::cin >> a >> op>> b;
  }

  return 0;
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <tuple>

#define rep(i,n) for(ll i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
//	std::cout<<std::fixed<<std::setprecision(10);

ll f(ll n) {
	ll res = 0;
	ll tmp_n = n;
	while(tmp_n%2==0) {
		res++;
		tmp_n = tmp_n >> 1;
	}
	return res;
}

int main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> a(N);
	
	ll tmp_a;
	cin >> tmp_a;

	ll fa = f(tmp_a);
	if(fa==0) {
		cout << 0 << endl;
		return 0;
	}

	a[0] = tmp_a>>fa;

	for(ll i = 1; i<N; i++) {
		cin >> tmp_a;
		if(fa == f(tmp_a)) {
			a[i] = tmp_a>>fa;
		} else {
			cout << 0 << endl;
			return 0;
		}
	}

	ll L = 1;
	M >>= fa-1;
	rep(i, N) {
		L = lcm(L, a[i]);
		if(L > M) {
			cout << 0 << endl;
			return 0;
		}
	}

	ll ans = dup(M/L, 2);
	cout << ans << endl;
	return 0;
}

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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  string S;
  cin >> S;

  int tot = 0;
  int Btot = 0;
  for (int i = 0; i < N; i++) {
    if (S.at(i) == 'a' && tot < (A + B)) {
      cout << "Yes" << endl;
      tot++;
      continue;
    }
    if (S.at(i) == 'b' && tot < (A + B) && Btot < B) {
      cout << "Yes" << endl;
      tot++;
      Btot++;
      continue;
    }
    cout << "No" << endl;
  }
}

Measured memory_bytes: 896
n = int(input())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
maxSum = 0
for i in range(n):
    s = 0
    for j in range(n):
        if j < i:
            s += a1[j]
        elif j == i:
            s += a1[j] + a2[j]
        else:
            s += a2[j]
        if s > maxSum:
            maxSum = s

print(maxSum)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	int a[n];
	long long res=0, k=1e18;
	for(int i=0; i<n; i++){
		cin >> a[i];
		if(a[i]<=k){
			k=a[i];
			res++;
		}
	}
	cout << res;
}

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

using namespace std;

int main()
{
    int N,K;
    cin>>N>>K;
    set<int> snuke;
    while(K--)
    {
        int d;
        cin>>d;
        while(d--)
        {
            int x;
            cin>>x;
            snuke.insert(x);
        }
    }

    cout<<N - snuke.size();

    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

template<typename value_type>
class fast_combination
{
public:
	value_type mod_value;

	vector<value_type> mod_inv;
	vector<value_type> fact;
	vector<value_type> fact_inv;

public:
	fast_combination(const value_type& limit, const value_type& m)
		: mod_value(m), mod_inv(), fact(), fact_inv()
	{
		mod_inv.assign(limit + 1, 0);
		fact.assign(limit + 1, 0);
		fact_inv.assign(limit + 1, 0);

		mod_inv[1] = 1;
		fact[0] = 1;
		fact[1] = 1;
		fact_inv[0] = 1;
		fact_inv[1] = 1;

		for (value_type i = 2; i <= limit; i++)
		{
			mod_inv[i] = (mod_value - ((mod_value / i) * mod_inv[mod_value % i] % mod_value)) % mod_value;
			fact[i] = (fact[i - 1] * i) % mod_value;
			fact_inv[i] = (fact_inv[i - 1] * mod_inv[i]) % mod_value;
		}
	}

public:
	value_type process(const value_type& n, const value_type& r)
	{
		if (n < 0 || r < 0) return 0;
		if (n < r) return 0;

		return (fact[n] * (fact_inv[r] * fact_inv[n - r] % mod_value)) % mod_value;
	}
};

//fast_combination<long long> fc(N, MOD);
//int result = fc.process(n, r);

const long long MOD = 1e9 + 7;

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

	fast_combination<long long> fc(3e6, MOD);

	int r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;

	long long result = fc.process(r2 + 1 + c2 + 1, r2 + 1);
	result = (result + (MOD - fc.process(r2 + 1 + c1, c1))) % MOD;
	result = (result + (MOD - fc.process(r1 + c2 + 1, r1))) % MOD;
	result = (result + fc.process(r1 + c1, r1)) % MOD;
	cout << result;

	return 0;
}

Measured memory_bytes: 70528
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d):
        self.e[u].append([v, d])
        self.e[v].append([u, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        """
        :param s: 始点
        :return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))

        return d


N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(S)
result_b = graph2.search(T)
ans_list = [float('inf')]
for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10**15-ans_list[-(i+1)])

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);

    i32 h,w,k; cin >> h >> w >> k;
    vii g(h, vi(w, -1));
    char tmp;
    rep(i,h) rep(j,w) {
        cin >> tmp;
        if(tmp =='.') g[i][j] = 0;
        else g[i][j] = 1;
    }

    //debug
//    rep(i,h)rep(j,w) cout << g[i][j] << (j == w-1? '\n' : ' ');

    i32 cnt = 0;
    for(i32 bit1 = 0; bit1 < (1<<h); ++bit1) {
        for(i32 bit2 = 0; bit2 < (1<<w); ++bit2) {

            i32 tmp_cnt = 0;
            rep(i,h) if(bit1>>i & 1) {
                rep(j,w) if(bit2>>j & 1) {
                    if(g[i][j]) ++tmp_cnt;
                }
            }
            if(tmp_cnt == k) ++cnt;
//            debug(tmp_cnt);

        }
    }

    cout << cnt << '\n';

    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 3596
n,m= map(int,input().split())

B = [0]*n
C = [0]*n
ans = 0
pna = 0
for i in range(m):
    a,b= input().split()
    a = int(a)
    if b=="AC":
        if B[a-1]==0 :
            B[a-1] =1
            ans += 1
            pna += C[a-1]
    else:
        C[a-1] = C[a-1]+1 
print(ans,pna)

Measured memory_bytes: 4724
from math import floor
A, B, C, D, E, F = map(int, input().split())
P = []
for i in range(31):
    for j in range(31):
        W=A*i+B*j
        if 100*W>F: break
        for k in range(3001):
            l = floor(min(F-100*W-C*k,W*E-C*k)/D)
            S = C*k+D*l
            if l<0 or S+W==0: continue
            P.append((100*S/(W*100+S),(W*100+S,S)))
P.sort(key=lambda x:x[0])
print(*P[-1][1])

Measured memory_bytes: 73916
//
//  header_useful.h
//  c++_acm
//
//  Created by 李弘辰 on 2019/7/23.
//  Copyright © 2019 李弘辰. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it with "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */


int main()
{
    itn n;
    scanf("%d",&n);
    string in;
    set<string> k;
    while (n --) {
        cin >> in;
        k.insert(in);
    }
    printf("%lu\n",k.size());
    return 0;
}


Measured memory_bytes: 15656
def enqueue(x):
  global tail
  que.append(x)
  tail = (tail + 1) % N

def dequeue():
  head_v = que.pop(0)
  return head_v


N, Q = map(int, input().split())
list = [input().split() for _ in range(N)]
que = []
elaps = 0

for i in range(N):
  que.append([list[i][0], int(list[i][1])])
tail = N

while que:
  target = dequeue()
  c = min(Q, target[1])
  target[1] -= c
  elaps += c
  if target[1] > 0:
    enqueue(target)
  else:
    print(target[0], elaps)




Measured memory_bytes: 21268