akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> >A;
long h,w,dp[3333],n,mod=1e9+7,fac[2<<17],inv[2<<17];
long p(long a,long b){return b?p(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
long f(long a,long b)
{
	return fac[a+b]*inv[a]%mod*inv[b]%mod;
}
main()
{
	cin>>h>>w>>n;
	fac[0]=inv[0]=1;
	for(int i=1;i<2<<17;i++)fac[i]=fac[i-1]*i%mod,inv[i]=p(fac[i],mod-2);
	for(int i=0;i<n;i++)
	{
		int a,b;cin>>a>>b;
		A.push_back(make_pair(a,b));
	}
	A.push_back(make_pair(h,w));
	sort(A.begin(),A.end());
	for(int i=0;i<=n;i++)
	{
		long now=f(A[i].first-1,A[i].second-1);
		for(int j=0;j<i;j++)
		{
			if(A[j].second<=A[i].second)
			{
				now=(now-dp[j]*f(A[i].first-A[j].first,A[i].second-A[j].second)%mod+mod)%mod;
			}
		}
		dp[i]=now;
	}
	cout<<dp[n]<<endl;
}

Measured memory_bytes: 4480
/*Mrc01*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long 
#define ull unsigned long long 
#define f(i,x,n) for(ll int i=x;i<n;i++) 
#define re(j,x,n) for(ll int j=x;j>=n;j--)
#define f1(k,x,n) for(ll int k=x;k<=n;k++)
#define endl "\n"
#define mp make_pair
#define pb push_back
#define bit(x, i) (x >>(i - 1) & 1ll)
#define MAX 1000001
const int mod=1000000007;
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<ll int,ll int>,null_type, less<pair<ll int,ll int>>, rb_tree_tag,tree_order_statistics_node_update> 
      new_data_set;
vector<ll int > v[1000100],check;
ll int a[1000010],vis[1000100]; 

void solve()
{  
   ll int n;
    cin>>n;
   ll int a[n],fre[n+1];
   memset(fre,0,sizeof(fre));
   f(i,0,n)
   {
     cin>>a[i];
     fre[a[i]]++;
   }
   ll int sum=0;
   f1(i,1,n)
   {
     if(fre[i]!=0)
     {
       sum+=(fre[i]*(fre[i]-1))/2;
     }
   }
   f(i,0,n)
   {
      cout<<sum-fre[a[i]]+1<<endl;
   }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ll int t;
    //  cin>>t;
    // while(t--)
    { 
       solve();
    }
}


Measured memory_bytes: 30464
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//????????????????????????????????????
#define int long long
#define str string
#define rep(i,j) for(int i=0;i<(int)(j);i++)
typedef long long ll;
typedef long double ld;
const ll inf = 4523372036854775807;
struct P {
    ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//??£??\???????????¨???
    ll to, cost;
};
struct S {//???????????±?????\???????????°
    int from, to, cost;
};
struct H {
    int x, y;
};
ll gcm(ll i, ll j) {//?????§??¬?´???°
    if (i > j) swap(i, j);
    if (i == 0) return j;
    return gcm(j%i, i);
}
ld rad(ld a, ld b, ld c, ld d) {
    return sqrt(pow(a - c, 2) + pow(b - d, 2));
}//rad?????§?¨???????2??????????????¢
//---------------------------------------------------
//+++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	string s;
	cin>>s;
	if(s[0]=='9'||s[1]=='9')
		cout<<"Yes\n";
	else
		cout<<"No\n";
    getchar(); getchar();
}


Measured memory_bytes: 256
import collections
n = int(input())
a =list(map(int,input().split()))
col = collections.Counter(a)
a = set(a)
cnt = 0
for letter in a:
    if col[letter]>letter:
        cnt += col[letter] - letter
    elif col[letter]<letter:
        cnt += col[letter]
print(cnt)

Measured memory_bytes: 20592
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
using namespace std;

#define rep(i,n) for(long long i = 0; i < n; i++)

typedef long long ll;
typedef unsigned long long int ulli;

const ll INF = ll(1e18) + 1;

typedef struct {
	ll cost;
	ll damage;
}magic;

unsigned long long int a(ulli n, ulli b) {
	if (b <= 1) {
		return n;
	}
	else {
		return a(n * 2, b - 1);
	}
}

ll mina(ll a, ll b) {
	return (a > b) ? b : a;
}

void Main()
{
	ll n, m; cin >> n >> m;
	if (n >= m) {
		rep(i, n) {
			cout << m;
		}
	}
	else {
		rep(i, m) {
			cout << n;
		}
	}
	cout << endl;
}

int main() {
	Main();
	return 0;
}

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

int res;
int n;
int f[128][128];
vector<int> inv;

void dfs(const vector<int> &v){
	if(v.size() > 2){
		res = max(res, accumulate(v.begin(), v.end(), 0));
	}
	vector<int> w(v.size() + 1);
	for(int i = inv.back() + 1; i <= n; ++i){
		int r = 1010101010;
		for(size_t j = 1; r && j < v.size(); ++j){
			w[j] = min(v[j], f[i][inv[j]]);
			r = min(r, f[i][inv[j]]);
		}
		if(r){
			inv.push_back(i);
			w.back() = r;
			dfs(w);
			inv.pop_back();
		}
	}
}

int main(){
	int m;
	cin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b, c;
		cin >> a >> b >> c;
		f[a][b] = f[b][a] = c;
	}
	inv.assign(1, 0);
	vector<int> v(1);
	dfs(v);
	cout << res << endl;
}

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

int main(){
    int a,b,c,d[3];
    cin>>a>>b>>c;
    if(a>b){
        if(b>c){
            d[0]=c;
            d[1]=b;
            d[2]=a;
        }
        else{
            if(a>c){
                d[0]=b;
                d[1]=c;
                d[2]=a;
            }
            else{
                d[0]=b;
                d[1]=a;
                d[2]=c;
            }
        }
    }
    else{
        if(b>c){
            d[0]=c;
            d[1]=a;
            d[2]=b;
        }
        else{
            if(a>c){
                d[0]=a;
                d[1]=c;
                d[2]=b;
            }
            else{
                d[0]=a;
                d[1]=b;
                d[2]=c;
            }
        }
    }
    
    cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
}


Measured memory_bytes: 3088
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		boolean[] ac = new boolean[n];
		int[] wa = new int[n];
		for (int i = 0; i < m; i++) {
			int p = sc.nextInt();
			String s = sc.next();
			if (s.equals("AC")) {
				ac[p - 1] = true;
			} else if (!ac[p - 1]) {
				wa[p - 1]++;
			}
		}
		sc.close();

		long acc = IntStream.range(0, n).filter(i -> ac[i]).count();
		long wac = IntStream.range(0, n).filter(i -> ac[i]).map(i -> wa[i]).sum();
		System.out.println(String.format("%d %d", acc, wac));
	}
}


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

int solve(long long n) {
    if (n == 1) {
        return 0;
    }
    vector<long long> f;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    if (n > 1) f.push_back(n);

    int ans = 0;
    int i = 0;
    while (i < f.size()) {
        int j = i + 1;
        while (j < f.size() && f.at(j) == f.at(i)) j++;
        int count = j - i;
        i = j;
        int sum = 0;
        for (int x = 1; count >= sum + x; x++, ans++) sum += x;
    }
    return ans;
}

int main() {
    long long n;
    cin >> n;
    cout << solve(n) << endl;
}

Measured memory_bytes: 3632
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
table = [[-1,-1] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a > D:
            table[a-D][0] = i
            table[a-D][1] = j
magic = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a <= H*W-D:
            magic[a] = abs(i-table[a][0])+abs(j-table[a][1])
for i in range(D+1,H*W+1):
    magic[i] += magic[i-D]
Q = int(input())
ans = 0
for i in range(Q):
    L,R = map(int,input().split())
    if L == R:
        print(0)
    else:
        if L <= D:
            print(magic[R-D])
        else:
            print(magic[R-D]-magic[L-D])





Measured memory_bytes: 25916
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstdio>
using namespace std;

void check(vector<string> in, vector<string>v){
  for(int i=0;i<v.size();i++){
    cout << v[i];
    if(i != v.size()-1){
      cout << " ";
    }
  }
  cout << endl;
  for(int i=1;i<v.size();i++){
    if(v[i-1][1] == v[i][1]){
      int num1, num2;
      for(int j=0;j<v.size();j++){
        if(v[i] == in[j]){
          num2 = j;
        }else if(v[i-1] == in[j]){
          num1 = j;
        }
      }
      if(num1 > num2){
        cout << "Not stable" << endl;
        return ;
      }
    }
  }
  cout << "Stable" << endl;
  return;
}

int main(void){
  int n;
  cin >> n;
  vector<string> in(n);
  vector<string> bs(n);
  vector<string> ss(n);
  for(int i=0;i<n;i++){
    cin >> in[i];
    bs[i] = in[i];
    ss[i] = in[i];
  }
  for(int i=0;i<n;i++){
    for(int j=n-1;j>i;j--){
      if(bs[j][1] < bs[j-1][1]){
        swap(bs[j], bs[j-1]);
      }
    }
  }
  check(in, bs);
  for(int i=0;i<n;i++){
    int min = i;
    for(int j=i;j<n;j++){
      if(ss[j][1] < ss[min][1]){
        min = j;
      }
    }
    swap(ss[min], ss[i]);
  }
  check(in, ss);

  return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
int n,arr[101];
int cal(int a,int b){return (arr[a]+arr[b])*(abs(a-b));}
void Min(int &a,int b){a=min(a,b);}

int mem[3][101][101][101];
int dfs(int f,int num,int l,int r){
  if(l>r)return 0;
  if(l==r)return (arr[l]==l+1) ? INF:0;
  if(r-l==1)return (arr[l]==l+1||arr[r]==r+1)? cal(l,r):0;
  if(mem[f][num][l][r]!=-1)return mem[f][num][l][r];

  int res=INF;  
  for(int i=l+1;i<r;i++){
    if(f!=2&&arr[i]!=l+1){
      swap(arr[l],arr[i]);
      Min(res,cal(l,i)+dfs(0,0,l+1,i-1)+dfs(1,arr[i],i,r));
      swap(arr[l],arr[i]);
    }
    if(f!=1&&arr[i]!=r+1){
      swap(arr[i],arr[r]);
      Min(res,cal(i,r)+dfs(2,arr[i],l,i)+dfs(0,0,i+1,r-1));
      swap(arr[i],arr[r]);
    }
  }

  for(int i=l;i<r;i++){
    int a=(f==1)? dfs(f,num,l,i):dfs(0,0,l,i);
    int b=(f==2)? dfs(2,num,i+1,r):dfs(0,0,i+1,r);
    Min(res,a+b);
  }

  return mem[f][num][l][r]=res;
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>arr[i];
  memset(mem,-1,sizeof(mem));
  cout<<dfs(0,0,0,n-1)<<endl;
}

Measured memory_bytes: 15188
def main():
    from collections import Counter

    n = int(input())
    s = [input() for _ in range(n)]

    ctr = Counter(s)

    _, most_cnt = ctr.most_common()[0]

    ret = []
    for key, cnt in ctr.most_common():
        if cnt != most_cnt:
            break
        ret.append(key)

    ret.sort()

    print(*ret, sep='\n')


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 45040
#include<bits/stdc++.h>
using namespace std;
int main()
{
     double d,t,s;
    cin>>d>>t>>s;
   double div=(d/s);

   if(div<=t)
   {
       cout<<"Yes"<<endl;
   }
   else{
    cout<<"No"<<endl;

   }

}


Measured memory_bytes: 3744
S = input()
T = input()


chars = "abcdefghijklmnopqrstuvwxyz"

sp = {}
tp = {}

result = True

for i in range(len(S)):
    sc = S[i]
    sx = i
    tc = T[i]
    tx = i
    if not sc in sp:
        sp[sc] = i
    else:
        sx = sp[sc]
    if not tc in tp:
        tp[tc] = i
    else:
        tx = tp[tc]
    if sx != tx:
        result = False
        break

if result:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    static PrintWriter out;
    static CF_Reader in;
    static int MAX = 1000000;
    static HashSet<Integer> duplicates;

    public static void main(String[] args) throws IOException {
        out = new PrintWriter(new OutputStreamWriter(System.out));
        in = new CF_Reader();


        int n = in.intNext();
        HashMap<Integer, Boolean> unique = new HashMap<>();
        duplicates = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int num = in.intNext();
            if (unique.containsKey(num)) duplicates.add(num);
            else unique.put(num, true);
        }
        out.println(solve(unique));

        out.close();
    }

    static int solve(HashMap<Integer, Boolean> unique){
        int res = 0;
        for (int n: unique.keySet()) {
            if (unique.get(n)) {
                int num = n * 2;
                while (num <= MAX) {
                    if (unique.containsKey(num)) unique.put(num, false);
                    num += n;
                }
            }
        }
        for (int num: unique.keySet()) if (unique.get(num) && !duplicates.contains(num)) {
            res++;
        }
        return res;
    }


    static class CF_Reader {
        BufferedReader br;
        StringTokenizer st;

        public CF_Reader() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine().trim());
            return st.nextToken();
        }

        long longNext() throws IOException {
            return Long.parseLong(next());
        }

        int intNext() throws IOException {
            return Integer.parseInt(next());
        }

        double doubleNext() throws IOException {
            return Double.parseDouble(next());
        }

        char charNext() throws IOException {
            return next().charAt(0);
        }

        public int[] nextIntArray(final int n) throws IOException {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = intNext();
            return a;
        }

        public long[] nextLongArray(final int n) throws IOException {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = longNext();
            return a;
        }

        String line() throws IOException {
            return br.readLine().trim();
        }
    }
}




Measured memory_bytes: 70924
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 1000000007;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;

int main(void) {

  int n, t, a[100010];
  cin >> n >> t;
  rep(i, n) cin >> a[i];

  set<int> s;
  s.insert(a[0]);

  int d = 0;
  for (int i = 1; i < n; i++) {
    d = max(d, a[i] - *(s.begin()));
    s.insert(a[i]);
  }

  int ans = 0;
  s.clear();
  s.insert(a[0]);
  for (int i = 1; i < n; i++) {
    if (*(s.begin()) == a[i] - d) ans++;
    s.insert(a[i]);
  }
  cout << ans << endl;

  return 0;

}


Measured memory_bytes: 5376
/*1  maxHeapify(A, i)
2      l = left(i)
3      r = right(i)
4      // 左の子、自分、右の子で値が最大のノードを選ぶ
5      if l ≤ H and A[l] > A[i]
6          largest = l
7      else
8          largest = i
9      if r ≤ H and A[r] > A[largest]
10         largest = r
11
12     if largest ≠ i　// i の子の方が値が大きい場合
13         A[i] と A[largest] を交換
14         maxHeapify(A, largest) // 再帰的に呼び出し*/

#include<stdio.h>
#define MAX 2000000000

int H, A[MAX];

void maxHeapify(int i){
  int l, r, largest, tmp;
  l = 2 * i;
  r = 2 * i + 1;
  if(l <= H && A[l] > A[i]) largest = l;
  else largest = i;
  if(r <= H && A[r] > A[largest]) largest = r;
  if(largest != i){
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;
    maxHeapify(largest);
  }
}

int main(){
  int i;
  scanf("%d", &H);
  for(i = 1; i <= H; i++){
    scanf("%d", &A[i]);
  }
  for(i = H/2; i >= 1; i--) maxHeapify(i);
  for(i = 1; i <= H; i++){
    printf(" %d", A[i]);
  }
  printf("\n");
  return 0;
}



Measured memory_bytes: 3736
#include <stdio.h>

int main(){
	int n,m,x,y,i;
	scanf("%d %d %d %d",&n,&m,&x,&y);
	int xx[n],yy[n];
	int maxx = -100;
	int maxy = 100;
	for(i = 0;i < n;i++){
		scanf("%d",&xx[n]);
		if(maxx < xx[n])
			maxx = xx[n];
			}
	if(maxx < x)
		maxx = x;
	
	for(i = 0;i < m;i++){
		scanf("%d",&yy[n]);
		if(maxy > yy[n])
			maxy = yy[n];
			}
	if(maxy > y)
		maxy = y;

	if(maxx >= maxy)
		printf("War");
	else
		printf("No War");

	return 0;
}

Measured memory_bytes: 128
#encoding: utf-8                                                                       

require 'complex'

x1, y1, x2, y2 = gets.chomp.split(/\s/).collect { |x| x.to_f }

p1 = Complex(x1, y1)
p2 = Complex(x2, y2)

puts ("%6f" % (p2 - p1).abs)

Measured memory_bytes: 6252
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
e=[[]for _ in[0]*n]
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
f=[0]*n
q=[0]
while q:
 v=q.pop();n-=1;f[v]=c[n]
 for w in e[v]:q+=[w]*(f[w]<1)
print(sum(c[:-1]),*f)

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

using namespace std;
int inf = 1 << 29;

vector<int> dx = {-1,1,0,0};
vector<int> dy = {0,0,1,-1};

bool inrange(int x, int y, int mx, int my) {
    return x >= 0 && y >= 0 && x < mx && y < my;
}

int main() {
    int r, c;
    cin >> r >> c;

    vector<vector<int>> v(r,vector<int>(c,inf));

    queue<pair<int,int>> q;
    
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            char cc; cin >> cc;
            if (cc == '#') {
                int n1 = i, n2 = j;
                q.push({n1,n2});
                v[n1][n2] = 1;
            }
        }
    }

    int hi = 1;

    while(!q.empty()) {
        int currx = q.front().first;
        int curry = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nextx = currx + dx[i];
            int nexty = curry + dy[i];
            if(!inrange(nextx,nexty,r,c)) continue;
            if(v[nextx][nexty] == inf) {
                v[nextx][nexty] = v[currx][curry] + 1;
                hi = v[nextx][nexty];
                q.push({nextx,nexty});
            }
        }
    }

    cout << hi-1 << endl;
}

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

using namespace std;

int main(int argc, char* argv[]) {
  int A, B;
  cin >> A >> B;

  string s;
  cin >> s;

  bool invalid = false;
  for (int i = 0; i < s.size(); ++i) {
    if (i == A && s[i] != '-') {
      invalid = true;
      break;
    } else if (i != A && !(s[i] >= '0' && s[i] <= '9')) {
      invalid = true;
      break;
    }
  }

  if (invalid)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;

  return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include <deque>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int main() {
	int a[233] = { 0 };
	for (int i = 1; i <= 3; i++)cin >> a[i];
	swap(a[1], a[2]);
	swap(a[1], a[3]);
	for (int i = 1; i <= 3; i++)cout << a[i] << " ";
	return 0;
}

  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, l, x[MAXN];
pair <int, int> y[MAXN];
ll calc(vector <pair <int, int>> &a) {
	ll ans = 0, sum = 0;
	for (unsigned i = l - 1, j = 0; i < a.size(); i++, j++) {
		sum += a[j].first;
		ans += a[i].second * sum;
	}
	return ans;
}
int main() {
	read(n), read(l);
	for (int i = 1; i <= n; i++) {
		read(x[i]);
		y[i] = make_pair(x[i], i);
	}
	sort(y + 1, y + n + 1); ll ans = n; int val = 0, pos = 1;
	vector <pair <pair <int, int>, pair <int, int>>> a, b;
	while (true) {
		if (a.empty()) {
			if (pos > n) break;
			else val = y[pos].first;
		} else val++;
		while (val == y[pos].first) a.emplace_back(make_pair(y[pos].second, y[pos].second), make_pair(1, 1)), pos++;
		b.clear(), sort(a.begin(), a.end());
		for (unsigned i = 0, j; i < a.size(); i = j + 1) {
			j = i; while (j + 1 < a.size() && a[j + 1].first.first == a[j].first.second + 1) j++;
			int len = j - i + 1, cnt = len / l;
			if (cnt != 0) {
				vector <pair <int, int>> cur, where, value;
				for (unsigned k = i; k <= j; k++)
					cur.push_back(a[k].second);
				ans += calc(cur);
				for (int k = 1; k <= cnt; k++) {
					where.emplace_back(a[i].first.first + k - 1, (k == cnt) ? a[j].first.second : a[i].first.first + k - 1);
					value.emplace_back(0, 0);
				}
				for (unsigned k = i; k <= j; k++) {
					int tl = k - i + 1, tr = j - k + 1;
					if (tl >= l) value[tl / l - 1].second += a[k].second.second;
					if (tr >= l) value[cnt - tr / l].first += a[k].second.first;
				}
				ans -= calc(value);
				for (unsigned k = 0; k < where.size(); k++)
					b.emplace_back(where[k], value[k]);
			} 
		}
		a = b;
	}
	writeln(ans);
	return 0;
}

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

int dp[1001][1001];
char x[1001], y[1001];
int main() {
	int q; scanf("%d", &q);
	rep(i, q) {
		scanf("%s%s", x, y); int a = strlen(x), b = strlen(y);
		rep(i, a)rep(j, b) {
			if (x[i] == y[j])dp[i + 1][j + 1] = dp[i][j] + 1;
			else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
		printf("%d\n", dp[a][b]);
	}
}

Measured memory_bytes: 7080
// Ho-kago Tea Time

#include <bits/stdc++.h>

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline int chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline int chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

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

const int MAXN = (int) 3e5;

int n;

int a[MAXN + 5];

inline void input()
{
	n = read<int>();
	for(int i = 1; i <= n; ++i) a[i] = read<int>();
}

inline void solve()
{
	if(n % 2 == 0)
	{
		int sum[2] = {0, 0};
		for(int i = 1; i <= n; ++i) sum[i & 1] += a[i];
		printf("%d %d\n", max(sum[0], sum[1]), min(sum[0], sum[1]));
		return;
	}

	const int INF = (int) 1e9;

	static int b[MAXN + 5];
	for(int i = 1; i <= n; ++i) b[i] = (i & 1 ? +1 : -1) * a[i];
	for(int i = 1; i <= n; ++i) b[i] += b[i - 1];

	auto check = [&] (int X)
	{
		static int f[MAXN + 5];

		int mn = 0;
		for(int i = 1; i <= n; ++i) if(i % 2 == 1 && (f[i] = (b[i] - mn >= X))) chkmin(mn, b[i + 1]);
		return f[n];
	};

	int l = 0, r = INF;
	while(l < r)
	{
		int mid = (l + r + 1) / 2;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}

	int ans = l, sum = 0;
	for(int i = 1; i <= n; ++i)
	{
		if(i % 2 == 0) ans += a[i];
		sum += a[i];
	}
	printf("%d %d\n", ans, sum - ans);
}

int main()
{
#ifdef K_ON // K-ON!
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	input();
	solve();

	return 0;
}



Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define TEST(...)                                                              \
    { printf("! "), printf(__VA_ARGS__); }
#else
#define TEST(...)
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
  public:
    char s[4444];
    int R[4444], G[4444], B[4444];
    void solve() {
        int n;
        scanf("%d", &n);
        scanf("%s", s + 1);
        for (int i = 1; i <= n; ++i) {
            R[i] += R[i - 1];
            G[i] += G[i - 1];
            B[i] += B[i - 1];
            if (s[i] == 'R')
                R[i]++;
            if (s[i] == 'G')
                G[i]++;
            if (s[i] == 'B')
                B[i]++;
        }
        i64 ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i] == 'R') {
                ans += G[i] * (B[n] - B[i]);
                ans += B[i] * (G[n] - G[i]);
                for (int j = 1; j <= n; ++j) {
                    if (i + j > n || i - j <= 0)
                        break;
                    if (s[i + j] == 'G' && s[i - j] == 'B')
                        ans--;
                    if (s[i + j] == 'B' && s[i - j] == 'G')
                        ans--;
                }
            } else if (s[i] == 'G') {
                ans += R[i] * (B[n] - B[i]);
                ans += B[i] * (R[n] - R[i]);
                for (int j = 1; j <= n; ++j) {
                    if (i + j > n || i - j <= 0)
                        break;
                    if (s[i + j] == 'R' && s[i - j] == 'B')
                        ans--;
                    if (s[i + j] == 'B' && s[i - j] == 'R')
                        ans--;
                }
            } else {
                ans += R[i] * (G[n] - G[i]);
                ans += G[i] * (R[n] - R[i]);
                for (int j = 1; j <= n; ++j) {
                    if (i + j > n || i - j <= 0)
                        break;
                    if (s[i + j] == 'R' && s[i - j] == 'G')
                        ans--;
                    if (s[i + j] == 'G' && s[i - j] == 'R')
                        ans--;
                }
            }
        }
        cout << ans << '\n';
    }
} NSPACE;
int main() {
    FPEN;
    // ios_base::sync_with_stdio(false);
    // cout.tie(0);
    // cin.tie(0);
    NSPACE.solve();
}

Measured memory_bytes: 3740
// warm heart, wagging tail,and a smile just for you!
//
//                            ▒█████▒▒
//                             ██████████▒
//                             ▒████████████▒
//                            ██████████████████
//                           ████████████████████▒
//                          ▒██████████████████████▒
//                          ▒███████████████████████
//                      ▒████▒▒▒▒▒▒█████████████████▒
//                    ███▒▒▒▒▒▒██████████████████████▒▒▒
//                  ▒██▒▒███████████████████████▒▒▒▒▒██████
//                 ▒█████████████████████████▒▒▒▒▒▒█████████▒
//                 ▒█████████████████████▒▒▒▒▒▒██████████████
//                  ▒████         ████▒▒▒▒▒████         ████▒
//              ▒█████▒    ████    ▒▒▒▒███████    ████    ██████▒
//            ▒██▒▒▒▒▒    ██████    █████████    ██████    ██▒▒▒██▒
//           █████████   ████████   █████████   ████████   ▒▒▒▒█████
//          ▒█████████    ██████    ████████▒    ██████    █████████
//          ▒██████████    ████    █████▒▒▒▒▒▒    ████    ██████████
//           ████████████        ▒▒▒▒▒▒▒████████        ███████████▒
//       ▒██████████▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒███████████████████████████████████▒
//     ███▒▒▒▒▒▒▒▒▒▒▒▒█████████████████████████████████████████▒▒████████▒
//   ▒▒▒▒▒▒▒▒▒██████████████                         ███████▒▒▒▒███████████
//   █████████████████████████                     ███████▒▒▒██████████████▒
//   █████████████████████████████             ███████▒▒▒██████████████████▒
//   ██████████████████████████████████████████████████████████████████████
//    ██████████████████████████████████████████████████████████████████▒
//      ▒█████████████████▒▒▒▒▒▒▒██████████████████████████████████▒▒▒
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<63-1)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

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

  int n,t;
  cin >> n >> t;

  vector<P> a(n);
  REP(i,n) cin >> a[i].fs >> a[i].sc;

  vec x(n),y(n);
  REP(i,n) x[i] = a[i].fs, y[i] = a[i].sc;

  sort(x.begin(),x.end());
  sort(y.begin(),y.end());

  int ans = INF;
  REP(i,n){
    FOR(j,i,n){
      REP(k,n){
        FOR(l,k,n){
          int cnt = 0;
          REP(c,n){
            if(range(a[c].fs,x[i],x[j]+1)&&range(a[c].sc,y[k],y[l]+1)) cnt++;
          }
          if(cnt >= t) ans = min(ans,(x[j]-x[i])*(y[l]-y[k]));
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
num = input()
arr = input().split()

def hoge(fuga):
    new_list = []
    for i in fuga:
        if int(i) % 2 == 0:
            new_list.append(int(i)/2)
        else:
            return False
    return new_list


count = 0
while True:
    arr = hoge(arr)
    if arr == False:
        break
    count += 1

print(count)


Measured memory_bytes: 2940
import java.util.Scanner;


public class Main {
	
       public static void main(String[] args) {
    	  Scanner input=new Scanner( System.in);
    	  
    	  String string=input.next();
    	  int len=string.length();
    	  int ans=0;
    	  for(int i=0;i<len;i++)
    	  {
    		  if(i%2==0)
    		  {
    			  if(string.charAt(i)=='p')
    				  ans--;
    		  }
    		  else
    		  {
    			  if(string.charAt(i)=='g')
    				  ans++;
    		  }
    	  }
    	  System.out.println(ans);
          
	}
}


Measured memory_bytes: 27052
import itertools

N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

# print(A * K)

ans = 0
meets = [0] * N
for i in range(N):
    for j in range(N):
        ans += int(i < j and A[i] > A[j])
        meets[i] += int(A[i] > A[j])
ans *= K
# print(meets)

ans += sum(meets) * K * (K - 1) // 2

print(ans % MOD)


Measured memory_bytes: 42988
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <iomanip>
using namespace std;
const double PI = acos(-1.0);
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int INTMAX = 2147483647;
const int INTMIN = -2147483648;
const unsigned int UINTMAX = 4294967295;
const long LONGMAX = 9223372036854775807;
const long LONGMIN = -9223372036854775808;
const unsigned long ULONGMAX = 18446744073709551615;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define UNIQ(c) (c).erase(unique((c).begin(), (c).end()), (c).end());
#define Yn(b) puts(b?"Yes":"No")
#define YN(b) puts(b?"YES":"NO")
#define fsp(c) fixed << setprecision(c)

bool isprime(int p) {
  if (p==1) return false;
  FOR(i,2,p) {
    if (p%i==0) return false;
  }
  return true;
}

int dig(int n, int a) {return n/(int)pow(10,a)%10;}
int digl(long n, int a) {return n/(long)pow(10,a)%10;}
int digsum(int n) {int r=0;REP(i,10){r+=dig(n,i);}return r;}
int digsuml(long n) {int r=0;REP(i,19){r+=digl(n,i);}return r;}
int dignum(int n) {return n?to_string(n).length():0;}
int dignuml(long n) {return n?to_string(n).length():0;}

double cutl(int i,double n,double r) {
  if (i<=0||n<=i) return 0;
  return r*sqrt(1-((double)i-n/2)*((double)i-n/2)*4/n/n);
}

int main(){
  long n,m=INTMAX,r,s;
  cin >> n;
  REP1(i,3500){
    FOR(j,i,3501){
      if(4*i*j>n*(i+j)){
        if((n*i*j)%(4*i*j-n*(i+j))==0){
          if((n*i*j)/(4*i*j-n*(i+j))<m){
            m=(n*i*j)/(4*i*j-n*(i+j));
            r=i;
            s=j;
          }
        }
      }
    }
  }
  cout << r << ' ' << s << ' ' << m;
  return 0;
}

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

int main() {
  int A11, A12, A13, A21, A22, A23, A31, A32, A33, N;
  cin >> A11 >> A12 >> A13;
  cin >> A21 >> A22 >> A23;
  cin >> A31 >> A32 >> A33;
  cin >> N;
  for (int i = 0; i < N; i++) {
    int b;
    cin >> b;
    if (b == A11) {
      A11 = 0;
    } else if (b == A12) {
      A12 = 0;
    } else if (b == A13) {
      A13 = 0;
    } else if (b == A21) {
      A21 = 0;
    } else if (b == A22) {
      A22 = 0;
    } else if (b == A23) {
      A23 = 0;
    } else if (b == A31) {
      A31 = 0;
    } else if (b == A31) {
      A31 = 0;
    } else if (b == A32) {
      A32 = 0;
    } else if (b == A33) {
      A33 = 0;
    }
  }
  if ((A11 + A12 + A13 == 0) || (A21 + A22 + A23 == 0) || (A31 + A32 + A33 == 0) || (A11 + A21 + A31 == 0) || (A12 + A22 + A32 == 0) || (A13 + A23 + A33 == 0) || (A11 + A22 + A33 == 0) || (A13 + A22 + A31 == 0)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


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

using namespace std;

#define LL long long
#define pb push_back
#define pLL pair<LL,LL>
#define ff first
#define ss second
#define rep(i,a,b) for(LL i=a;i<=b;++i)
#define ld double
#define mp make_pair
#define vLL vector<LL>
#define vpLL vector<pLL>
#define vld vector<ld>
#define pld pair<ld,ld>
#define vpld vector<pld>
#define SLL set<LL>
#define SpLL set<pLL>
#define FIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

string s;
LL n;

int main()
{
    FIO;
    cin>>s;
    LL cnt=0,ans=0;
    char cur='A';
    rep(i,0,s.size()-1){
        if(s[i]!=cur){
            ans++;
            cnt=1;
            cur=s[i];
        }
        else cnt++;
    }
    cout<<ans-1<<endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)

typedef pair< pair<int, ll> , int> P;

bool pairCompare(const P & firstElof, const P& secondElof)
{
    return firstElof.first < secondElof.first;
}

int dig(int x){
    int dig=0;
    while(x>0){
        dig++;
        x /= 10;
    }
    return dig;
}

string str(int x,int y){
    string str="";
    rep(i,6-dig(x)) str += '0';
    str += to_string(x);
    rep(i,6-dig(y)) str += '0';
    str += to_string(y);
    return str;
}

string s[110000];

int main(){
    int n,m;
    cin >> n >> m;
    vector<P> v(m);
    rep(i,m){
        cin >> v[i].first.first >> v[i].first.second;
        v[i].second = i;
    }

    sort(v.begin(), v.end(), pairCompare);
    int cnt=1;
    rep(i,m){
        if(i == 0) s[v[i].second] = str(v[i].first.first, 1);
        else{
            if(v[i].first.first == v[i-1].first.first){
                cnt++;
            }
            else{
                cnt=1;
            }
            s[v[i].second] = str(v[i].first.first, cnt);
        }
    }
    rep(i,m) cout << s[i] << endl;
}

Measured memory_bytes: 11008
#include <iostream>
using namespace std;
int main(){
    int k,x;
    cin>>k>>x;
    int low,high;
    low = (x-k+1>=-1000000)?x-k+1:-1000000;
    high = (x+k-1<=1000000)?x+k-1:1000000;
    for(int i=low;i<=high;i++){
        printf("%d ",i);
    }
    printf("\n");
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ll long long

using namespace std;

double dist(pair<int, int> l, pair<int, int> r){
  double dx = l.first-r.first;
  double dy = l.second-r.second;
  return pow(dx*dx+dy*dy, 0.5);
}

int main(){
  int n;
  cin>>n;
  vector<pair<int,int>> xy;
  rep(i, n){
    int x,y;
    cin>>x>>y;
    xy.emplace_back(x,y);
  }
  
  vector<int> ar;
  rep(i,n){
    ar.push_back(i);
  }
  
  double sum = 0;

  do {
    rep(i,n-1){
      sum += dist(xy[ar[i]], xy[ar[i+1]]);
    }
  } while( next_permutation(ar.begin(), ar.end()) );
  
  int fac = 1;
  rep(i,n) fac *= (i+1);

  cout<<setprecision(8)<<(sum/fac)<<setprecision(6);

  return 0;
}


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

using namespace std;

using ll = long long int;

// GCDを計算します
template <typename NumType>
NumType calcGCD(NumType a, NumType b) {
    if (a < b) {
        NumType tmp = a;
        a = b;
        b = tmp; 
    }

    NumType r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

// 約数を数えます
template <typename NumType>
NumType cntDivisor(const NumType & num) {
    NumType cnt = 0;
    for(NumType i = 1; i * i <= num; ++i) {
        if(num % i == 0) {
            cnt++;
            if(i * i != num) cnt++;
        }
    }

    return cnt;
}

// [beg, end)の範囲を，添え字indexでループするfor文に置換します
#define FOR_RANGE(index, beg, end)     for (ll index = beg; index < N; ++index)

#define DEBUG(x)     std::cout << #x << " : " << x << "\n"

int main() {

    int N, K;

    cin >> N >> K;

    cout << N - K + 1;

    return 0;
}



Measured memory_bytes: 256
N, x = [int(t) for t in input().split()]
a = [int(t) for t in input().split()]

ans = 0
if a[0] > x:
    ans = a[0] - x
    a[0] = x

for i in range(1, len(a)):
    much = a[i] + a[i-1] - x
    if 0 < much <= a[i]:
        ans += much
        a[i] -= much
    elif a[i] < much:
        t = a[i]
        a[i] = 0
        ans += t
        much -= t
        a[i-1] -= much
        ans += much
print(ans)


Measured memory_bytes: 14600
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  int a,b;
  char c;
  cin>>a>>c>>b;
  if(c=='+') cout<<a+b<<endl;
  if(c=='-') cout<<a-b<<endl;

  return 0;
}







Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N = int(input())
ga,sa,ba = map(int,input().split())
gb,sb,bb = map(int,input().split())

t1 = []
t2 = []
if ga < gb:
    t1.append((ga,gb))
else:
    t2.append((gb,ga))
if sa < sb:
    t1.append((sa,sb))
else:
    t2.append((sb,sa))
if ba < bb:
    t1.append((ba,bb))
else:
    t2.append((bb,ba))

dp = [0] * (N+1)
N1 = N
for i in range(1,N+1):
    for c,r in t1:
        if c <= i:
            dp[i] = max(dp[i], dp[i-c] + r)
    N1 = max(N1, N-i+dp[i])

ans = N1
dp = [0] * (N1+1)
for i in range(1,N1+1):
    for c,r in t2:
        if c <= i:
            dp[i] = max(dp[i], dp[i-c] + r)
    ans = max(ans, N1-i+dp[i])

print(ans)


Measured memory_bytes: 266620
#include<cstdio>
#include<algorithm>
int main(){
    int n,x,m,min=1e9;
    scanf("%d%d",&n,&x);
    for(int i=0;i<n;i++){
        scanf("%d",&m);
        x-=m;
        min=std::min(min,m);
    }
    printf("%d",n+x/min);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define repm(i,a,b) for(ll i=(ll)(a);i>(ll)(b);i--)
#define all(v) v.begin(), v.end()
#define rall(x) (x).rbegin(),(x).rend()
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vc vector<char>
#define vvc vector<vc>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;
using vb =vector<bool>;
using vvb=vector<vb>;
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; }
//snippets:tmp,cl,cvl,cs,co,coy,con,cov,setp

int main(){
  ll n;
  cin >> n;
  ll m;
  cin >> m;
  ll k;
  cin >> k;
  vll a(n);
  rep(i, n){
    ll x;
    cin >> x;
    if(i==0) a[0]=x;
    else a[i]=a[i-1]+x;
  }
  vll b(m);
  rep(i, m){
    ll x;
    cin >> x;
    if(i==0) b[0]=x;
    else b[i]=b[i-1]+x;
  }
  ll i=0;
  ll ans=0;
  while(true){
    if(i==n+1) break;
    ll time=0;
    if(i!=0) time+=a[i-1];
    if(time>k) break;
    auto key=upper_bound(all(b),k-time);
    ll aa=key-b.begin();
    ans=max(ans,aa+i);
    i++;
  }
  cout<<ans<<endl;
}

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

using namespace std;

const int MAX = 200001;
const int MOD = 998244353;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main(void) {
  COMinit();
  int N, M, K; cin >> N >> M >> K;

  long long same[N];
  long long patn[N];
  same[N-1] = M;

  long long p = M;

  for (int i = N-2; i >= 0; i--) {
    p *= M-1;
    p %= MOD;
    same[i] = p * COM(N-1, i) % MOD;
  }

  long long ans = 0;

  for (int i = 0; i <= K; i++) {
    ans += same[i];
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 9848
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n,c = map(int,input().split())
    xv = [list(map(int,input().split())) for i in range(n)]
    x = [xv[i][0] for i in range(n)]
    v = [xv[i][1] for i in range(n)]
    r1,r2,l1,l2 = [0]*(n+1),[0]*(n+1),[0]*(n+1),[0]*(n+1)
    ans = 0
    dis = 0
    for i in range(n):
        r1[i+1] = r1[i]+v[i]-(x[i]-dis)
        r2[i+1] = r2[i]+v[i]-2*(x[i]-dis)
        dis = x[i]
    dis = c
    for i in reversed(range(n)):
        l1[n-i] = l1[n-i-1]+v[i]-(dis-x[i])
        l2[n-i] = l2[n-i-1]+v[i]-2*(dis-x[i])
        dis = x[i]
    for i in range(n):
        l1[i+1] = max(l1[i+1],l1[i])
        r1[i+1] = max(r1[i+1],r1[i])
    for i in range(n+1):
        ans = max(ans,max(r2[i]+l1[n-i],l2[i]+r1[n-i]))
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================
    

Measured memory_bytes: 49732
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

ll M;
int N;
string C;

ll val[10];

void add(ll &a,ll b){
  a=(a+b)%MOD;
}

int main(){
  cin>>M;
  cin>>C;
  N=C.size();

  vector<int> v;
  for(int i=0;i<=9;i++) v.push_back(i);

  ll ten=1;
  for(int i=N-1;i>=0;i--){
    add(val[C[i]-'0'],ten);
    ten=ten*10%MOD;
  }

  do{
    if(v[C[0]-'0']==0&&N>1) continue;
    ll res=0;
    for(int j=0;j<=9;j++){
      ll c=v[j]*val[j]%MOD;
      add(res,c);
    }
    res=(res+MOD)%MOD;
    if(res==M){
      string ans="";
      for(int i=0;i<N;i++) ans+=char(v[C[i]-'0']+'0');
      cout<<ans<<endl;
      return 0;
    }
  }while(next_permutation(v.begin(),v.end()));

  cout<<-1<<endl;

  return 0;
}



Measured memory_bytes: 3428
#include <bits/stdc++.h>
#define re return
#define ll long long
#define ld long double
#define f first
#define s second
#define pi acos(-1)
#define oo (int)1e9
#define OO (ll)1e18
#define EPS 1e-7
#define FX(n) fixed<<setprecision(n)
#define mm(o,k) memset(o,k,sizeof o)
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int maxn=55;
int a[maxn][maxn];
int main()
{
    IO;
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            char x;
            cin >> x;
            a[i][j]=x=='.';
        }
    }
    for(int i=1;i<n-1;++i)
        for(int j=1;j<m-1;++j)
            if(!a[i][j]&&a[i][j+1]&&a[i][j-1]&&a[i+1][j]&&a[i-1][j])re cout<<"No\n",0;
    puts("Yes");
    re 0;
}

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

class AtCoder
{
    public AtCoder() { }
    public static int Main()
    {
        new AtCoder().calc();
        return 0;
    }

    void calc()
    {
        int A, B, M;
        string[] st = Console.ReadLine().Split(' ');
        A = int.Parse(st[0]);
        B = int.Parse(st[1]);
        M = int.Parse(st[2]);
        int[] a = new int[A];
        int[] b = new int[B];
        st = Console.ReadLine().Split(' ');
        for (int i = 0; i < A; i++)
        {
            a[i] = int.Parse(st[i]);
        }

        st = Console.ReadLine().Split(' ');
        for (int i = 0; i < B; i++)
        {
            b[i] = int.Parse(st[i]);
        }

        int[] x = new int[M];
        int[] y = new int[M];
        int[] c = new int[M];
        for (int i = 0; i < M; i++)
        {
            st = Console.ReadLine().Split(' ');
            x[i] = int.Parse(st[0]) - 1;
            y[i] = int.Parse(st[1]) - 1;
            c[i] = int.Parse(st[2]);
        }

        long ans = 99999999999999L;

        //割引券を使わないパターン

        long amin = ans;
        long bmin = ans;

        for (int i = 0; i < A; i++)
        {
            amin = Math.Min(a[i], amin);
        }
        for (int j = 0; j < B; j++)
        {
            bmin = Math.Min(b[j], bmin);
        }
        ans = amin + bmin;

        //割引券を使うパターン
        for (int i = 0; i < M; i++)
        {
            ans = Math.Min(ans, a[x[i]] + b[y[i]] - c[i]);
        }

        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 35676