akhauriyash/Code-Regression huggingface dataset:
N,K=map(int, input().split())
AA=list(map(int, input().split()))
A=sorted(AA)
B=sorted(AA)[::-1]
mod=10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
n = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n+1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ans=0
for i in range(N-K+1):
  d=(A[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  e=(B[K-1+i]%mod)*cmb(K-1+i,K-1,mod)
  ans+=d%mod-e%mod
  ans%=mod
print(ans)

Measured memory_bytes: 22548
#include <bits/stdc++.h>
#define rep(i,n) for (int i= 0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const long long INF = 1LL << 60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main(){
    int h,w,k;cin>>h>>w>>k;
    int final =0;
    vector<vector<int>> data(6, vector<int >(6));
    rep(i,h){
        rep(j,w) {
            char sss;
            cin >> sss;
            if(sss=='#')data[i][j]=1;
            else data[i][j] = 0;
        }
    }
    vector<int> wl(6);
    vector<int> hl(6);
    int count =0;
    rep(i,h){
        rep(j,w){
            hl[i]+=data[i][j];
            count+=data[i][j];
        }
       // cout<<hl[i]<<endl;

    }
    rep(i,w){
        rep(j,h){
            wl[i]+=data[j][i];

        }
      //  cout<<wl[i]<<endl;
    }



    for (int tmp = 0; tmp < (1 << h); tmp++) {
        set<int> hh;
        ll ans= count;
        bitset<6> s(tmp);
       // cout<<s<<endl;
        if(s.test(0)){
            ans-=hl[0];
            hh.insert(0);
            //cout<<"one"<<endl;
        }
        if(s.test(1)){
            ans-=hl[1];
            hh.insert(1);
           // cout<<"two"<<endl;
        }
        if(s.test(2)){
            ans-=hl[2];
            hh.insert(2);
        }
        if(s.test(3)){
            ans-=hl[3];
            hh.insert(3);
        }
        if(s.test(4)){
            ans-=hl[4];
            hh.insert(4);
        }
        if(s.test(5)){
            ans-=hl[5];
            hh.insert(5);
        }


        for (int tmp2 = 0; tmp2 < (1 << w); tmp2++) {
            set<int> ww;
            bitset<6> s2(tmp2);
            int ans2 =ans;

            if(s2.test(0)){
                ans2-=wl[0];
                ww.insert(0);
            }
            if(s2.test(1)){
                ans2-=wl[1];
                ww.insert(1);
            }
            if(s2.test(2)){
                ans2-=wl[2];
                ww.insert(2);
            }
            if(s2.test(3)){
                ans2-=wl[3];
                ww.insert(3);
            }
            if(s2.test(4)){
                ans2-=wl[4];
                ww.insert(4);
            }
            if(s2.test(5)){
                ans2-=wl[5];
                ww.insert(5);
            }
            for(auto itr = hh.begin();itr!=hh.end();++itr){
                for(auto itr2 = ww.begin();itr2!=ww.end();++itr2){
                    ans2+=data[*itr][*itr2];
                }
            }

            if(ans2==k)final++;

            }
        }


    cout<<final<<endl;

}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    cout << max({a*c,b*d,a*d,b*c});
}

Measured memory_bytes: 3648
#include <stdio.h>

int main(void) {
  char s[201];
  int i = 0, ch;
  while ((ch = getchar()) != '\n')
    s[i++] = ch;

  for (i = 0; s[i] != '\0' || s[i] == ' '; i++) 
    if ('a' <= s[i] && s[i] <= 'z')
      s[i] += 'A' - 'a';

  for (i = 0; s[i] != '\0' || s[i] == ' '; i++)
    putchar(s[i]);
  putchar('\n');

  return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;

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

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

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

    int imp=0;
    ll total=a[0];
    for (int i = 1; i < N; ++i) {
        if(total*2<a[i]){
            imp=i;
        }
        total+=a[i];
    }
    cout<<N-imp<<endl;
    return 0;
}


Measured memory_bytes: 1024
N=int(input())
M=int(input())
k=[]
for _ in range(N):
    k.append(list(map(int,input().split())))

S=[0 for _ in range(N+1)]
S[0]=M

for i in range(1,N+1):
    S[i]=S[i-1]+k[i-1][0]-k[i-1][1]

S.sort()
if S[0]<0:
    print(0)
else:
    print(S[-1])


Measured memory_bytes: 7064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define in              insert
#define pb              push_back
#define mp              make_pair
#define lb              lower_bound
#define ub              upper_bound
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n]
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int32_t main()
{
	FIO;
	int n, k; cin >> n >> k;
	mk(h, n, int);
	for (int i = 0; i < n; i++)
		cin >> h[i];

	int dp[n] = {};

	for (int i = 1; i < n; i++) {
		dp[i] = inf;

		for (int j = i - 1; j >= max(0ll, i - k); j--)
			dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
	}

	cout << dp[n - 1] << endl;

	return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  long double p[N];
  for(int i=0; i<N; i++) {
    cin >> p[i];
    p[i]=(p[i]+1)/2;
  }
  long double cnt=0,ans=0;
  for(int i=0; i<K; i++) {
    cnt+=p[i];
  }
  long double cnt2=0;
  ans=cnt;
  for(int i=K; i<N; i++) {
    cnt=cnt+p[i]-p[i-K];
    if(ans<cnt) {
      ans=cnt;
    }
  }
  cout << setprecision(10) << ans << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod=1e9+7;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a==0 && b==0 && c==1) cout << 1;
    if(a+b>=c){
        cout << b+c;
    }else{
        cout << 2*b+a+1;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define pii pair<int, int>
//#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define jai_shree_ram  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i, a, b, d) for (int i = a; i <= b; i += d)
#define brep(i, a, b, d) for (int i = a; i >= b; i -= d)
#define pb push_back
#define all(x) x.begin(), x.end()
#define endl '\n'
int MOD = 1e9 + 7;
////////////////////////////////


int32_t main(){
    jai_shree_ram
    int n;
    cin >> n;
    int a[n+1];
    rep(i,1,n,1) cin >> a[i];
    int ans = 0;
    map <int, int> m;
    rep(i,1,n,1){
        if(!m[a[i]-1]) m[a[i]] = 1;
        else m[a[i]] = m[a[i]-1] + 1;
        ans = max(ans, m[a[i]]);
    }
    cout << n - ans << endl;
    return 0; 
}


Measured memory_bytes: 14336
n = gets.to_s.to_i
a = gets.to_s.split.map{|t|t.to_i}

r =  a.map.with_index(0){ |h, i|  h + i }.tally
l =  a.map.with_index(0){ |h, i| -h + i }.tally

ans = 0
(r.keys & l.keys).each do |k|
  ans += r[k] * l[k]
end

puts ans

Measured memory_bytes: 53660
#include<iostream>
using namespace std;
int main()
{

int a,b,c;
cin>>a>>b>>c;
if(a%2==b%2 and b%2==c%2) {cout<<(max(max(a,b),c)*3-a-b-c)/2;
                           system("pause");
                           return 0;} 
int x=a%2;
int y=b%2;
int z=c%2;
if(x==y) {a++;
          b++;}
if(y==z) {c++;
          b++;}
if(z==x) {a++;
          c++;}
cout<<(max(max(a,b),c)*3-a-b-c)/2+1;

system("pause");
return 0;
}

Measured memory_bytes: 504
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int str = scan.nextInt();
        int s2 = scan.nextInt();
        int a = 0;
        switch (str) {
            case 1:
                if (s2 == 2) {
                    a = 3;
                } else {
                    a = 2;
                }
                break;

            case 2:
                if (s2 == 1) {
                    a = 3;
                } else {
                    a = 1;
                }
                break;
            case 3:
                if (s2 == 1) {
                    a = 2;
                } else {
                    a = 1;
                }
                break;
        }

        System.out.println(a);
    }
}

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

using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::vector;

int
main()
{
  int N;
  cin >> N;
  vector<int> L(N);
  for (int n = 0; n < N; n++)
  {
    cin >> L[n];
  }
  sort(L.begin(), L.end());
  int count = 0;
  for (int x = 0; x < N - 2; x++)
  {
    int a = L[x];
    for (int y = x + 1; y < N - 1; y++)
    {
      int ab = a + L[y];
      for (int z = y + 1; z < N; z++)
      {
        if (ab <= L[z])
        {
          break;
        }
        count++;
      }
    }
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
N=int(input())
A=[int(input()) for _ in range(N)]

A.sort(reverse=True)
if len(A)%2==0:
  print(A[len(A)//2-1]-A[len(A)//2]+2*sum(A[:len(A)//2-1])-2*sum(A[len(A)//2+1:]))
else:
  tmp1=-A[len(A)//2]-A[len(A)//2+1]+2*sum(A[:len(A)//2])-2*sum(A[len(A)//2+2:])
  tmp2=A[len(A)//2-1]+A[len(A)//2]+2*sum(A[:len(A)//2-1])-2*sum(A[len(A)//2+1:])
  print(tmp1 if tmp1>tmp2 else tmp2)

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

int main(){
int n;cin>>n;
vector<int> a(n),b(n),v(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
if(a==b){cout<<0;return 0;}
for(int i=0;i<n;i++)v[i]=a[i];
sort(v.begin(),v.end());
int x,y,t=1;
while(a!=v){
    next_permutation(v.begin(),v.end());
    t++;
    x=t;
}
sort(v.begin(),v.end());t=1;
while(b!=v){
    next_permutation(v.begin(),v.end());
    t++;
    y=t;
}
cout<<abs(x-y);
}


Measured memory_bytes: 3168
def gcd(a,b):
        while b:
            a,b=b,a%b
        return a
def solve(lis,x):
    if len(lis)==1:
        return abs(lis[0]-x)
    lis=[abs(c-x) for c in lis]
    ans=gcd(lis[0],lis[1])
    for x in lis[2:]:
        if x!=0:
            ans=gcd(ans,x)
    return ans 
n,x=map(int,input().split())
l=list(map(int,input().split()))
print(solve(l,x))


Measured memory_bytes: 14480
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 15
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)

ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;


int main() {
	scanf("%lld %lld %lld", &N, &A, &B);
	fei(i, A, B, 1) {
		if(i % N == 0) {
			printf("OK\n");
			quit;
		}
	}	
	printf("NG\n");
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 3760
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define MAX 100100
inline int gi(){
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
int n,f[MAX<<1];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
int sz1[MAX<<1],sz2[MAX<<1];
ll ans;
int main(){
    n=gi();
    for(int i=1;i<MAX+MAX;++i)f[i]=i;
    for(int i=1;i<=n;++i)
    {
        int u=gi(),v=gi();
        f[getf(u)]=getf(v+MAX);
    }
    for(int i=1;i<=MAX;++i)
        sz1[getf(i)]+=1;
    for(int i=MAX+1;i<MAX+MAX;++i)
        sz2[getf(i)]+=1;
    for(int i=1;i<MAX+MAX;++i)ans+=1ll*sz1[i]*sz2[i];
    cout<<ans-n<<endl;
    return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    string S;
    cin>>S;

    string T="CODEFESTIVAL2016";

    int ans=0;
    rep(i,S.size()){
        if(S[i]!=T[i])ans++;
    }
    cout << ans << endl;

    



}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int ds[MAXN];
char S[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;

    for(int i=1;i<=n;i++)
        ds[i] = ds[i/10]+(i%10);

    for(int i=1;i<n;i++)
        mn = min(ds[i]+ds[n-i],mn);

    cout<<mn<<"\n";

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    string S;
    cin >> S;
    int N = S.size();
    ll dp[N+1][4];
    fill(dp[0], dp[N+1], 0);
    dp[0][0] = 1;
    rep(i, N){
        if(S[i] == 'A' || S[i] == '?'){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1] + dp[i][0];
            dp[i+1][2] += dp[i][2];
            dp[i+1][3] += dp[i][3];
        }
        if(S[i] == 'B' || S[i] == '?'){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1];
            dp[i+1][2] += dp[i][2] + dp[i][1];
            dp[i+1][3] += dp[i][3];
        }
        if(S[i] == 'C' || S[i] == '?'){
            dp[i+1][0] += dp[i][0];
            dp[i+1][1] += dp[i][1];
            dp[i+1][2] += dp[i][2];
            dp[i+1][3] += dp[i][3] + dp[i][2];
        }
        rep(j, 4){
            dp[i+1][j] %= MOD;
        }
    }
    cout << dp[N][3] << endl;
}

Measured memory_bytes: 3584
A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(A[K-1])

Measured memory_bytes: 38756
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

ll n, m, Q;
vector<ll> ve[100005];
ll c[100005];
ll d[100005];
ll x[100005], y[100005], z[100005];
queue<ll> qu, qc, qi;

int main()
{
    scanf("%lld%lld", &n, &m);
    while(m--)
    {
        ll t1, t2;
        scanf("%lld%lld", &t1, &t2);
        ve[t1].push_back(t2);
        ve[t2].push_back(t1);
    }
    scanf("%lld", &Q);
    for(ll i = 0; i < Q; i++)
    {
        ll t1, t2, t3;
        scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
    }
    for(ll i = 1; i <= n; i++) d[i] = -1;
    for(ll i = Q - 1; i >= 0; i--)
    {
        qi.push(x[i]), qc.push(z[i]), qu.push(y[i]);
        while(!qi.empty())
        {
            ll t1 = qi.front(), t2 = qc.front(), t3 = qu.front();
            qi.pop(), qc.pop(), qu.pop();
            if(c[t1] == 0) c[t1] = t2;
            if(d[t1] >= t3) continue;
            d[t1] = t3;
            if(t3 == 0) continue;
            for(ll j = 0; j < ve[t1].size(); j++)
            {
                qi.push(ve[t1][j]), qc.push(t2), qu.push(t3 - 1);
            }
        }
    }
    for(ll i = 1; i <= n; i++)
    {
        printf("%lld\n", c[i]);
    }
    return 0;
}


Measured memory_bytes: 13300
import numpy as np

num = list(map(int,input().split()))
num_list = np.ones(num[0])*(num[1] - num[2])
reward = []

for i in range(0,num[2]):
  reward.append(int(input()))

for i in range(0,num[2]):
  num_list[reward[-i-1] - 1] = num_list[reward[-i-1] - 1] + 1
 
    
for i in range(0,num[0]):
  if num_list[i]>0:
    print("Yes")
  elif num_list[i] <=0:
    print("No")



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

int main(){
	int N;
	cin >> N;
	for(int i=N/7; i>=0; i--){
		if((N-i*7)%4 == 0){
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
N, K, Q = map(int, input().split())
A = [int(input())-1 for _ in range(Q)]

def solve():
    points = [0 for _ in range(N)]
    for a in A:
        points[a] += 1
    sum_points = sum(points)
    for p in points:
        if sum_points - p >= K:
            print('No')
        else:
            print('Yes')

if __name__ == '__main__':
    solve()

Measured memory_bytes: 8628
// Undone
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
using namespace std;
signed main() {
  string a, b;
  cin>>a>>b;
  for (int i = 0; i < a.length(); i++) {
    cout << a[i];
    if (i < b.length()) {
      cout<< b[i];
    }
  }
  cout<<endl;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
	int64_t x;
	mint(int64_t x=0):x((x%mod+mod)%mod){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
	mint operator+(const mint a) const { return mint(*this) += a;}
	mint operator-(const mint a) const { return mint(*this) -= a;}
	mint operator*(const mint a) const { return mint(*this) *= a;}
	mint pow(int64_t t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}

	//for prime mod
	mint inv() const { return pow(mod-2);}
	mint& operator/=(const mint a) { return *this *= a.inv();}
	mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

//head

using V = vector<mint>;
using M = vector<V>;

M mul(M a, M b) {
	int n = a.size();
	M res(n, V(n));
	rep(i, n) rep(j, n) rep(k, n) res[i][j] += a[i][k] * b[k][j];
	return res;
}
M pow(M &a, ll p) {
	int n = a.size();
	if(!p) {
		M res(n, V(n));
		rep(i, n) res[i][i] = 1;
		return res;
	}
	M res = pow(a, p>>1);
	res = mul(res, res);
	if(p&1) res = mul(res, a);
	return res;
}

int n;
ll k;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	M a(n, V(n));
	rep(i, n) rep(j, n) cin >> a[i][j];
	a = pow(a, k);
	mint ans;
	rep(i, n) ans += accumulate(a[i].begin(), a[i].end(), mint());
	cout << ans << endl;
}

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

typedef long long ll;


ll dp[101][2][5];
int main() {
  string s; cin >> s;
  int K; cin >> K;
  int n = s.size();
  dp[0][0][0] = 1;
  for (int i = 0; i < n; ++i) { 
    int d = s[i]-'0';
    for (int k = 0; k < 4; ++k) {
      dp[i+1][1][k] += dp[i][1][k]; // 0
      dp[i+1][1][k+1] += 9*dp[i][1][k]; // 1-9
      if (d > 0) {
        dp[i+1][1][k] += dp[i][0][k]; // 0
        dp[i+1][1][k+1] += (d-1)*dp[i][0][k]; // 1-(d-1)
        dp[i+1][0][k+1] += dp[i][0][k]; // d
      }
      else {
        dp[i+1][0][k] += dp[i][0][k]; // d = 0
      }
    }
  }
  cout << dp[n][0][K]+dp[n][1][K] << endl;
}



Measured memory_bytes: 256
from collections import deque


def solve(string):
    n, *ab = map(int, string.split())
    # i != j => (ai, bi) != (aj, bj)
    next_ = [dict([]) for _ in range(n + 1)]
    color = [set([]) for _ in range(n + 1)]
    queue = deque([1])
    for a, b in zip(*[iter(ab)] * 2):
        next_[a][b] = 0
        next_[b][a] = 0
    while len(queue) > 0:
        c = queue.popleft()
        _next = next_[c].items()
        use = set(range(1, len(_next) + 1)) - color[c]
        _next = (k for k, v in _next if v == 0)
        for _n, u in zip(_next, use):
            queue.append(_n)
            next_[c][_n] = u
            next_[_n][c] = u
            color[c].add(u)
            color[_n].add(u)
    return str("{}\n{}".format(max(map(lambda x: len(x.keys()), next_)),
                               "\n".join(str(next_[a][b]) for a, b in zip(*[iter(ab)] * 2))))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


Measured memory_bytes: 74996
#include <bits/stdc++.h>
using namespace std;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
typedef long long ll;
typedef unsigned long long ull;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(ll i = (a); i < (ll) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define MOD 1000000007
ll binser(ll k)
{
    ll a=0, b=k*k+k, med;
    while(b-a>1)
    {
        med=(a+b)/2;
        if((med*(med+1))/2<k) a=med;
        else b=med;
    }
    return b;
}

int main() {
    FIN;
    int x, y, z;
    cin >> x >> y >> z;
    swap(x,y); swap(x,z);
    cout << x << " " << y << " " << z << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
#include<regex>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define dup(x,y) (((x)+(y)-1) / (y)) //整数型のまま切り上げ演算する
#define PI 3.14159265359
typedef long long LL;
template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> inline T gcd(T x, T y) { if (y == 0) { return x; } else if (x == 0) { return y; }return gcd(y, x % y); }
template<class T> inline T lcm(T x, T y) { return (x * y) / gcd(x, y); }
template<class T> inline void print_vector(vector<T> vec) { for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl; }
const LL MOD = 1e9 + 7;
const LL LLINF = 1LL << 60;
const int INF = 1 << 30;

vector<vector<LL> > dp(5010, vector<LL>(5010));

int main(void) {
	LL N;
	string S;
	cin >> N >> S;

	for (int i = N - 1; i >= 0; i--) {
		for (int j = N - 1; j >= 0; j--) {
			dp[i][j] = (S[i] == S[j]) ? (1 + dp[i + 1][j + 1]) : 0;
		}
	}


	LL ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (abs(i-j) >= dp[i][j]) {
				chmax(ans, dp[i][j]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 196736
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}

int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

  ll K = input();
  ll sum = 0;
  for(int a=1;a<=K;a++){
    for(int b=1;b<=K;b++){
      for(int c=1;c<=K;c++){
        sum += gcd(gcd(a,b),c);
      }
    }
  }

  output(sum);

  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
const int INF = 1e17;
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, w, a, b;
    cin >> n >> w;
    long long tab[w+1];
//    int cosas[2][n];
    for(int i = 0; i <=w; i++){
        tab[i] = 0;
    }
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        for(int  j = w; j > a; j--){
            if(tab[j-a]!= 0){
                tab[j] = max(tab[j-a]+b, tab[j]);
            }
        }
        tab[a] = max(tab[a], tab[0]+b);

    }
    long long maxi =0;
    for(int i =0 ;  i<=w; i++){
        maxi= max(maxi, tab[i]);
    }
    cout << maxi;
    return 0;
}



Measured memory_bytes: 1024
l = [int(input()) for _ in range(4)]
ans = 0
if l[0] < l[1]:
    ans += l[0] * l[2]
else:
    ans += l[1] * l[2]
if (l[0]-l[1]) > 0:
    for _ in range(l[0]-l[1]):
        ans += l[3]
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<cmath>
#include<map>
#include<functional>
#include<queue>
#include<set>
#include<stack>
#include<iomanip>
#include<algorithm>
#include<unordered_map>
#include <numeric>
#include<string_view>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(i) i.begin(),i.end()
template<typename T =ll> using v = vector<T>;
template<typename T =ll> using vv = v<v<T>>;
template<typename T =ll,typename U =ll> using p = pair<T,U>;
template<typename T> T chmin(T &a,T b) {return a=min(a,b);}
template<typename T> T chmax(T &a,T b) {return a=max(a,b);}
const ll INF = (ll)1e9;
template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept { return is >> x.val; }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

class d{
    ll N;
    ll A;
    ll B;
    mint chouse(ll r){
        mint X = 1;
        rep(i,r){
            X*=(N-i);
        }
        mint Y = 1;
        rep(i,r){
            Y*=(i+1);
        }
        return X/Y;
    }

    mint f(ll t){
      if(t==0) return 1;
      mint X = f(t/2);
      X*=X;
      if(t%2==1) X*=2;
      return X;
    }
    public:
    d(){
        cin >> N >> A >> B;
        auto ans = f(N) - 1;       
        ans -= chouse(A);
        ans -= chouse(B);
        cout << ans << endl;
    }
};

int main(void){
    d();
    return 0;
 }

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define sqr(x) ((x) * (x))
#define bit(n) (1LL<<(n))
#define pcnt(x) __builtin_popcountll(x)
#define PB push_back
#define MP make_pair
#define endl "\n"
using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// 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;}

ll dp[110][110];
const ll MAX = 1001001001001001;

int main() {
  int n; cin >> n;
  ll p[n+1];
  FOR(i,0,n-1){
    cin >> p[i] >> p[i+1];
  }
  FOR(i,1,n){
    FOR(j,1,n){
      if(i==j) continue;
      else dp[i][j] = MAX;
    }
  }
  
  FOR(l,2,n){
    FOR(i,1,n-l+1){ //連鎖長がlのものでループ
      int j = i+l-1;
      FOR(k,i,j-1){
        ll q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
        chmin(dp[i][j],q);
      }
    }
  }
  cout << dp[1][n] << "\n";

}



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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int x,y; cin >> x >> y;
  if(y % 2 == 0 && y - 2*x >= 0 && 4*x - y >= 0){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

using namespace std;


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

    int dp[100000+5];
    dp[0] = 0;
    for(int i=0;i<n;i++){
        dp[i+1]=dp[i]+1;
    }
    for(int i=0;i<=n;i++){
        for(int j=6;i+j<=n;j*=6){dp[i+j]=min(dp[i]+1, dp[i+j]);}
        for(int j=9;i+j<=n;j*=9){dp[i+j]=min(dp[i]+1, dp[i+j]);}
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i=a; i<n; i++)
#define RREP(i, a, n) for(ll i=n-1; i>=a; i--)
typedef long long ll;
const ll mod =1e9+7;
const ll inf =1e18;
using namespace std;

ll n, h, w;
ll cnt;
int main(){
    cin>>n>>h>>w;
    REP(i, 0, n){
        ll a, b;
        cin>>a>>b;

        if(a>=h && b>=w) cnt++;
    }

    cout<<cnt<<endl;
    return 0;
}

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

int main()
{
    int H, W;

    for (int k = 0; k<10000; k++)
    {
        cin >> H >> W;
        if (H != 0 && W != 0)
        {
            for (int x=1; x<=W; x++)
            {
                cout << "#";
            }
            cout << endl;
            for (int i=3; i<=H; i++)
            {
                cout << "#";
                for (int j=1; j<=W-2; j++)
                {
                    cout << ".";
                }
                cout << "#" << endl;
            }
            for (int x=1; x<=W; x++)
            {
                cout << "#";
            }
            cout << "\n" << endl;
        }
        else k = 10000;
    }
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

class arc093_c {
public:
    void solve(istream& in, ostream& out) {
        int N;
        in >> N;
        vector<int> A(N + 1);
        A[0] = 0;
        for (int i = 0; i < N; ++i) {
            in >> A[i + 1];
        }
        ++N;
        vector<int> sufa(N + 1);
        sufa[N] = 0;
        sufa[N - 1] = abs(A[N - 1] - A[0]);
        for (int i = N - 2; i >= 0; --i) {
            sufa[i] = sufa[i + 1] + abs(A[i] - A[i + 1]);
        }
        int cur = 0;
        for (int i = 1; i < N; ++i) { // skip i
            out << cur + abs(A[i - 1] - A[(i + 1) % N]) + sufa[i + 1] << "\n";
            cur += abs(A[i - 1] - A[i]);
        }
    }
};

int main() {
	std::ios::sync_with_stdio(false); cin.tie(nullptr);
	arc093_c solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

MOD = 10**9+7
n = N*M-2
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

C = comb(N*M-2, K-2)
ans = 0
for d in range(N):
    ans += d*(N-d)*(M**2)*C
    ans %= MOD

for d in range(M):
    ans += d*(M-d)*(N**2)*C
    ans %= MOD

print(ans)

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
#define int ll

signed main(void)
{
  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    string s[45];
    REP(i, n) cin >> s[i];

    REP(i, n) {
      int tmp = 0, cnt = 0;
      FOR(j, i, n) {
        tmp += s[j].size();
        //cout << cnt << " " << tmp << endl;
        if(cnt == 0) {
          if(tmp == 5) {cnt = 1; tmp = 0;}
          else if(tmp > 5) break;
        } else if(cnt == 1) {
          if(tmp == 7) {cnt = 2; tmp = 0;}
          else if(tmp > 7) break;
        } else if(cnt == 2) {
          if(tmp == 5) {cnt = 3; tmp = 0;}
          else if(tmp > 5) break;
        } else if(cnt == 3) {
          if(tmp == 7) {cnt = 4; tmp = 0;}
          else if(tmp > 7) break;
        } else if(cnt == 4) {
          if(tmp == 7) {cnt = 5; tmp = 0;}
          else if(tmp > 7) break;
        }
      }
      if(cnt == 5) {
        cout << i+1 << endl;
        break;
      }
    }
  }

  return 0;
}

Measured memory_bytes: 3136
/*

*/
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <cstdlib>
#include <cmath>
#include <bitset>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define ld long double
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x)
#define rf(x) scnaf("%lf",&x)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
#define sz(x) ((int) x.size())
#define ld long double

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

//mt19937 myrand(time(0));
//int get_rand(int n){return myrand()%n + 1;}
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5;

struct abc{
    int t,a,id;
    bool operator < (const abc & tmp) const{
        return t < tmp.t;
    }
};

int X,K,n,ans[N+10];
abc q[N+10];

int main(){
    //Open();
    //Close();
    ri(X),ri(K);
    rep1(i,1,K) {
        int x;
        ri(x);
        q[++n].t = x;
    }
    ri(K);
    rep1(i,1,K){
        int t,a;
        ri(t),ri(a);
        q[++n].t = t,q[n].a = a,q[n].id = i;
    }
    sort(q+1,q+1+n);
    int a = 0,b = X,l = 0,r = X,pre = 0,sign = -1;
    rep1(i,1,n)
        if (q[i].id){
            //是一个询问
            int rest = q[i].t - pre,temp;
            if (q[i].a <= l){
                temp = a;
            }else if (q[i].a >= r){
                        temp = b;
                  }else
                        temp = a + q[i].a - l;
            temp += sign*rest;
            if (temp > X) temp = X;
            if (temp < 0) temp = 0;
            ans[q[i].id] = temp;
        }else{
            //是一个翻转操作
            int v = q[i].t - pre;
            if (sign==-1){//如果要做减法
                if (a<v){//如果最小的那个不够减了,则肯定
                    b = max(b-v,0);
                    l = min(l + (v-a),X);
                    r = max(l,r);
                    a = 0;
                }else{
                    a-=v,b-=v;
                }
            }else{
                if (b+v<=X){//最大的加上v之后都小于等于X则可行,a+v<=x,a+1+v<=x...a+b-a+v<=x
                    a+=v,b+=v;
                }else{
                    //b+v>X
                    a = min(a+v,X);//a加上之后可能大于X了.最大让他为X
                    r = max(r - (b+v-X),0);//倒数第1+(b+v-X)个数到最后一个数都变成X了
                    l = min(l,r);//r要是小于l了,就把l变成r就好.
                    b = X;//b是肯定变成x了
                }
            }
            pre = q[i].t;
            sign = sign*(-1);
        }
    rep1(i,1,K)
        oi(ans[i]),puts("");
    return 0;
}


Measured memory_bytes: 3968
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define ll long long
#define INF 1000000000
#define P std::pair<int,int>
#define LP std::pair<ll,ll>


int main(){
    int n,d,a; std::cin >> n >> d >> a;
    d *= 2;
    std::vector<P> xh(n);
    rep(i,n)
        std::cin >> xh[i].first >> xh[i].second;

    std::sort(xh.begin(), xh.end());
    std::queue<LP> que;
    ll ans=0, dmg=0;
    rep(i,n){
        int x=xh[i].first;
        int h=xh[i].second;
        while(que.size() && que.front().first < x){
            dmg -= que.front().second;
            que.pop();
        }
        h -= dmg;
        if(h > 0){
            ll cnt=(h+a-1)/a;
            ans += cnt;
            ll tmp=cnt*a;
            dmg += tmp;
            que.push(LP(x+d, tmp));
        }
    }
    std::cout << ans << std::endl;
    return 0;
}

Measured memory_bytes: 6252
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
//#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (10);   小数点以下１０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//string s = to_string(int数);
//int n = stoi(string文字列);

int main() {
  int a;
  cin >>a;
  
  cout << fixed << setprecision (10);
  
  cout << 2*pi*a << endl;
  
}


Measured memory_bytes: 3776
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int a = scanner.nextInt(), b = scanner.nextInt();
			System.out.println((1 == ((a * b) & 1)) ? "Yes" : "No");
		}
	}
}


Measured memory_bytes: 35680
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion

n = inp()
data = [inpl() for _ in range(n)]
lotate_x = [x - y for x, y in data]
lotate_y = [x + y for x, y in data]
ans = max(max(lotate_x) - min(lotate_x), max(lotate_y) - min(lotate_y))
print(ans)


Measured memory_bytes: 116068
k, n = map(int ,input().split())
a = list(map(int ,input().split()))

max_i = -1
for i in range(n-1):
  max_i = max(a[i+1]-a[i], max_i)
max_i = max((k-a[-1])+a[0], max_i)
print(k-max_i)

Measured memory_bytes: 32304
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
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; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

int cnt=0;
ll ans=0;

vector<int>a(50),b(50),c(50),d(50);
int Q;

void check(vector<int>&v){
  ll num=0;
  rep(i,Q){
    if(v[b[i]]-v[a[i]]==c[i])num+=d[i];
  }
  chmax(ans,num);
}

void f(int n,int m,int i,int last,vector<int>&v){
  // cout<<i<<" "<<last<<endl;
  if(i==n){
    // cnt++;
    check(v);
    // debag(v);
    return;
  }
  for(int j=last;j<=m;j++){
    v.push_back(j);
    f(n,m,i+1,j,v);
    v.pop_back();
  }
  return;
}

bool solve(){
  int n,m;cin>>n>>m;
  vector<int>v;
  cin>>Q;
  rep(i,Q)cin>>a[i]>>b[i]>>c[i]>>d[i];
  rep(i,Q)a[i]--;
  rep(i,Q)b[i]--;
  f(n,m,0,1,v);

  cout<<ans<<endl;
  return false;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(30);
    solve();
}


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

typedef long long LL;

const int N=100,INF=(1<<30)-1;

int n,m;
char s[N+9][N+9];

void into(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=n;++i)
	scanf("%s",s[i]+1);
}

int dp[N+9][N+9];

void Get_dp(){
  dp[1][1]=s[1][1]=='#';
  for (int i=1;i<=n;++i)
	for (int j=1;j<=m;++j){
	  if (i==1&&j==1) continue;
	  dp[i][j]=INF;
	  if (i>1) dp[i][j]=min(dp[i][j],dp[i-1][j]+(s[i-1][j]=='.'&&s[i][j]=='#'));
	  if (j>1) dp[i][j]=min(dp[i][j],dp[i][j-1]+(s[i][j-1]=='.'&&s[i][j]=='#'));
	}
}

void work(){
  Get_dp();
}

void outo(){
  printf("%d\n",dp[n][m]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 3760