akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "-1" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  int N, A, B;
  cin >> N >> A >> B;
  if (N - A + 1 < B || (N + A - 1) / A > B) no();
  if (B == 1) {
    if (A != N) no();
    vi32 ans(N);
    reps(i, N) ans[i - 1] = i;
    cout << ans << '\n';
    return;
  }
  if (A == 1) {
    if (B != N) no();
    vi32 ans(N);
    rep(i, N) ans[i] = N - i;
    cout << ans << '\n';
    return;
  }
  vi32 ans(N);
  {
    int j = 0;
    for (int i = N - A + 1; i <= N; i++) {
      ans[j++] = i;
    }
    function<void(int, int, int)> crt = [&](int j, int R, int G) {
      if (R == G) {
        for (int i = R; i >= 1; i--) {
          ans[j++] = i;
        }
        return;
      }
      if (R - A < G - 1) {
        for (int i = G; i <= R; i++) {
          ans[j++] = i;
        }
        crt(j, G - 1, G - 1);
      } else {
        for (int i = R - A + 1; i <= R; i++) {
          ans[j++] = i;
        }
        crt(j, R - A, G - 1);
      }
    };
    crt(j, N - A, B - 1);
    cout << ans << '\n';
  }
}


Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
const int N = 501;
const int mod = 1e9 + 7;
int main(){
    int n, a, ans = 0;
    map<int, int> my;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a);
        my[a]++;
    }
    int prev = 0, tot = 0;
    for(auto it = my.begin(); it != my.end(); it++){
        if((it -> first - prev) % 2){
            ans ^= (n - tot);
        }
        prev = it -> first;
        tot += it -> second;
    }
    if(ans == 0){
        printf("second\n");
    }else{
        printf("first\n");
    }
    return 0;
}

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

int n;
int a[101010];
int b[101010];

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

  int ans = 0;
  int po = 0;
  for (int i = 0; i < 101010; i++){
    if (b[i] & 1){
      ans++;
    } else if (b[i] == 0) {
     continue;
    }
    else {
      po++;
    }
  }

  cout << ans + po / 2 * 2 << endl;
}



Measured memory_bytes: 1024
using System;
using System.Linq;

namespace ABC172
{
    class B
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var T = Console.ReadLine();

            var ans = 0;
            for (int i = 0; i < S.Length; i++)
            {
                if (S[i] != T[i]) ans++;
            }

            Console.WriteLine(ans);

        }
    }
}


Measured memory_bytes: 27552
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		
		while(true)
		{
			int n = scan.nextInt();
			if(n == 0) {break;}
			int[] grades = new int[n];
			
			for(int i = 0; i < n; i++)
			{
				grades[i] = scan.nextInt();
			}
			
			int ans = 9000000;
			
			for(int a = 0; a < n; a++)
			{
				for(int b = a+1; b < n; b++)
				{
					ans = Math.min(ans, Math.abs(grades[a] - grades[b]));
				}
			}
			
			System.out.println(ans);
		}
		
	}

}



Measured memory_bytes: 49592
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef vector <int> vi;
typedef vector <vector <int>> vii;
typedef vector <long long> vll;
typedef vector <string> vs;
typedef vector <char> vc;
typedef set <int> si;
typedef set <string> ss;
typedef queue <int> qi;
typedef queue <long long> qll;
typedef queue <string> qs;
typedef queue <char> qc;
typedef struct board board;
typedef pair <int, int> pi;
typedef pair <long long, long long> pll;
typedef pair <int, pair<int, int>> pii;

#define eb emplace_back
#define ppb pop_back
#define clr(a) a.clear()
#define F first
#define S second
#define mkp make_pair

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define left(x) x * 2
#define right(x) x * 2 + 1

#define meme(a, b, c) fill(a + 1, a + 1 + b, c)

#define max(a, b) (a > b ? a : b)
#define min(a, b) (a > b ? b : a)
#define abs(a) (a > 0? a : -(a))

#define move(s) s += "#"

#define fr(i, a, b) for (ll i = a; i <= b; ++ i)
#define rf(i, a, b) for (ll i = a; i >= b; -- i)

#define eprintf(...) fprintf(stderr, __VA_ARGS__);

void to_pray() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cerr << "Ready\n";
}

const int N = 4e6 + 10;
const int NN = 1e3 + 10;
const int NNN = 2e3 + 9;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e12 + 7;
const ll P = 53;
const int EPS = 1e-9 - 8;
const int vN = 2e4 + 10;
const int sz = (1 << 22) - 1;
const double PI = acos(-1);

int main () {
    to_pray();
    
    int x, y;
    cin >> x >> y;
    
    cout << x + y / 2;
    
    cout << '\n';
    return 0;
}

Measured memory_bytes: 256
k = input()
k = int(k)
x = input().split()

a = int(x[0])
b = int(x[1])

if(k==1):
  print("OK")
  exit()

if(a==b):
  if(a%k==0):
    print("OK")
    exit()
    
for i in range(a,b+1):
  if(i%k == 0):
    print("OK")
    exit()
print("NG")

Measured memory_bytes: 61960
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

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

using namespace std;
typedef long long int ll;
const int INF = 100000000;

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

    bool is_reverse = false;
    string before, after;
    rep(i, q) {
        int t, f;
        string c;
        cin >> t;
        if (t == 1) {
            is_reverse = !is_reverse;
        }
        if (t == 2) {
            cin >> f >> c;
            if (f == 1) {
                if (!is_reverse) before = c + before;
                else after = after + c;
            }
            else if (f == 2) {
                if (!is_reverse) after = after + c;
                else before = c + before;
            }
        }
    }
    if (!is_reverse) s = before + s + after;
    else {
        s = before + s + after;
        reverse(s.begin(), s.end());
    }
    cout << s << endl;
    return 0;
}


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


int main(){

  int64_t N,tmp,num;
  vector<int64_t> a;
  
  cin >> N;
  for(int64_t i=0;i<3*N;i++){
    cin >> tmp;
    a.push_back(tmp);
  }
  
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  num=0;
  for(int64_t i=0;i<N;i++){
    num += a.at(2 * i + 1);
  }

  cout << num << endl;
}


Measured memory_bytes: 7444
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;

ll INF = 114514191919119;

int main(){

    string O, E;
    cin >> O >> E;

    vector<char > ans(O.length()+E.length());

    ll cn = 0;
    for(ll i = 0; i < O.length(); i++){
        ans[cn] = O[i];
        cn += 2;
    }

    cn = 1;
    for(ll i = 0; i < E.length(); i++){
        ans[cn] = E[i];
        cn += 2;
    }

    for(ll i = 0; i < ans.size(); i++){
        cout << ans[i];
    }
    cout << endl;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int K, T; cin >> K >> T;
    vector<int> A(T);
    rep(i, T) cin >> A.at(i);
    sort(A.begin(), A.end(), greater<int>());
    if (A[0] < K - A[0]) {
        cout << 0 << endl;
    } else {
        cout << A[0] - (K - A[0]) - 1 << endl;
    }
}


Measured memory_bytes: 3616
#pragma comment(linker, "/STACK:66777216")
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<unordered_set>
#include<unordered_map>
#include<cassert>
#include<bitset>
#include<ctime>
using namespace std;
using ll = long long;

ll Rec(ll N, ll X) {
	if (N == 2LL*X)
		return 3LL*X;
	if (N > 2LL*X)
		return 3LL*X + Rec(N - X, N - 2LL*X);
	ll K = X / (N - X);
	ll R = X % (N - X);
	ll ANS = 2LL*K*(N - X) + X;
	if (R == 0)
		return ANS;
	return ANS + 2LL*R + Rec(N - X, N - X - R);
}

void Solve() {
	ll N, X;
	scanf("%lld%lld", &N, &X);
	printf("%lld", Rec(N, X));
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	Solve();

#ifdef LOCAL
	cerr << double(clock()) / CLOCKS_PER_SEC << endl;
#endif

	return 0;
}

Measured memory_bytes: 256
#define R(i,r)for(int i=0;i<r;i++)
#define P(x,y)x=(x+y)%998244353
b,c,N,A,s[3],dp[1<<18][3][3][2];
main(f){
	for(;read(0,&c,1),c-10;N++)s[c-'a']++,f&=b!=c,b=c;
	dp[0][0][0][0]=dp[0][1][1][0]=dp[0][2][2][0]=1;
	R(n,N-1)R(i,3)R(j,3)R(k,2)R(d,3)P(dp[n+1][d][(j+d)%3][k|i==d],dp[n][i][j][k]);
	R(i,3)P(A,dp[N-1][i][(s[1]+2*s[2])%3][1]);P(A,f);
	printf("%d\n",!s[0]+!s[1]+!s[2]>1?:N<4?(s[0]|s[1]|s[2])&2?6+f:N:A);
}

Measured memory_bytes: 14464
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

int main() {
    long x, y;
    cin >> x >> y;
    if (abs(x - y) <= 1) {
        cout << "Brown" << endl;
    } else {
        cout << "Alice" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

double p[3300];
double dp[3300][3300];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i];

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i; j++){
            dp[i][j] += dp[i-1][j] * (1 - p[i]);
            if(j - 1 >= 0) dp[i][j] += dp[i-1][j-1] * p[i];
        }
    }
    double ans = 0;
    for(int i = 1; i <= n; i++){
        if(i > n - i) ans += dp[n][i];
    }
    printf("%.18lf\n", ans);
}

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

public class Main {
    public static int w,n,x,y,c;
    public static int[] ans;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w=sc.nextInt();
        n=sc.nextInt();
        ans=new int[w+1];
        for(int i=1;i<=w;i++) ans[i]=i;
        for(int i=0;i<n;i++){
            String s;
            s=sc.next();
            String[] split=s.split(",");
            x=Integer.parseInt(split[0]);
            y=Integer.parseInt(split[1]);
            swap();
        }
        sc.close();
        for(int i=1;i<=w;i++) System.out.println(ans[i]);
    }
    private static void swap(){
        c=ans[x];
        ans[x]=ans[y];
        ans[y]=c;
    }
}



Measured memory_bytes: 26196
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vpii         vector<pair<int,int>>
#define gph          map<int, vector<int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define FORS(i, n) for(; i < (int)(n); i++)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define printArr(A,n) { cout << #A << " = "; FOR(i,n) cout << A[i] << ' '; cout << endl; }
using namespace std;
#define int long long int
const int mod = (int)1e9 + 7;
vi fac((int)3e5 + 10);
long long inv(long long a, long long b = mod){
 return 1<a ? b - inv(b%a,a)*b/a : 1;
}
int choose(int a, int b){
    assert(b >= 0 && b <= a);
    int ans = fac[a] * inv(fac[b]);
    ans %= mod;
    ans *= inv(fac[a-b]);
    ans %= mod;
    assert(ans >= 0);
    return ans;
}
int p(int base, int exp){
    if(exp == 0)return 1;
    int sub = p(base, exp/2);
    sub *= sub;
    assert(sub >= 0);
    sub %= mod;
    if(exp & 1)sub *= base;
    sub %= mod;
    assert(sub >= 0);
    return sub;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int n, a, b, c;cin >> n >> a >> b >> c; 
    a = a*inv(100);
    a %= mod;
    b = b*inv(100);
    b %= mod;
    c = c*inv(100);
    int denom= inv(a + b);
    a *= denom;
    a %= mod;
    b *= denom;
    b %= mod;
    //debug(a);debug(b);
    fac[0] = 1;
    FOR1(i, (int)2e5){
        fac[i] = fac[i-1]*i, fac[i] %= mod;
        assert(fac[i] >= 0);
    }
    int ans = 0;
    for(int other = 0; other < n ; other++){
        int prob = p(a, n) * p(b, other);
        prob %= mod;
        int prob2= p(a, other) * p(b, n);
        prob2 %= mod;
        int ways = fac[other + n -1]*inv(fac[other]);
        ways %= mod;
        ways *= inv(fac[n-1]);
        ways %= mod;
        ways *= (n + other);
        ways %= mod;
        ans += ways*(prob + prob2);
        ans %= mod;
        assert(ans >= 0);
    }
    ans *= denom; 
    ans %= mod;
    cout << ans;

}




Measured memory_bytes: 2560
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<int, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

const int N = 805;

int dis[N][N];
int dr[4][2] = {{-1,0}, {+1,0}, {0,+1}, {0,-1}};

int main(){
    fastIO;
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 0 ; i < N ; i ++ )
        for(int j = 0 ; j < N; j ++ )
            dis[i][j] = (int)-1;
    queue<pii> ff;
    char t;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            cin >> t;
            if(t == 'S'){
                ff.push(mp(i,j));
                dis[i][j] = 0;
            }
            else if(t == '.'){
                dis[i][j] = (int)1e7;
            }
            else{
                dis[i][j] = -1;
            }
        }
    }
    int vi, vj;
    while(!ff.empty()){
        vi = ff.front().fi;
        vj = ff.front().se;
        ff.pop();
        if(dis[vi][vj] == k)
            continue;
        for(int i = 0  ; i < 4; i ++ ){
            if(dis[vi + dr[i][0]][vj + dr[i][1]] > dis[vi][vj] + 1){
                dis[vi + dr[i][0]][vj + dr[i][1]] = dis[vi][vj] + 1;
                ff.push(mp(vi + dr[i][0], vj + dr[i][1]));
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            if(dis[i][j] == -1){
                dis[i][j] = (int)1e7;
            }
            else if(dis[i][j] <= k){
                dis[i][j] = k;
                ff.push(mp(i,j));
            }
        }
    }
    while(!ff.empty()){
        vi = ff.front().fi;
        vj = ff.front().se;
        ff.pop();
        for(int i = 0 ; i < 4; i ++ ){
            if(dis[vi + dr[i][0]][vj + dr[i][1]] > dis[vi][vj] + 1){
                dis[vi + dr[i][0]][vj + dr[i][1]] = dis[vi][vj] + 1 ;
                ff.push(mp(vi + dr[i][0], vj + dr[i][1]));
            }
        }
    }
    int res = (int)1e7;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            if(i == 1 || j == 1 || i == n || j == m){
                if(dis[i][j] != -1)
                    res = min(res, dis[i][j]);
            }
        }
    }
    cout << (res + k - 1) / k << "\n";
    return 0;
}

Measured memory_bytes: 7936
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long[] arr = new long[5];
        long min = Long.MAX_VALUE;
        for (int i = 0; i < 5; i++) {
            arr[i] = sc.nextLong();
            min = Math.min(min, arr[i]);
        }
        System.out.println(5L + (long)Math.ceil((double)n / (double)min) - 1);
    }
}


Measured memory_bytes: 23252
use std::io;
use std::str::FromStr;

fn input<T:FromStr>() -> T {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().parse().ok().unwrap()
}

fn main() {
    let n: u64 = input();
    if n % 1000 == 0 {
        println!("0");
    } else {
        println!("{}", 1000 - n % 1000);
    }
}


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


int main() {
  int n, k;
  cin >> n >> k;
  int ans = 0;
  char d = 'a';
  rep(i,n) {
    char c;
    cin >> c;
    if(c==d) ans++;
    d = c;
  }
  cout << min(n-1,ans+2*k) << endl;
  return 0;
}

Measured memory_bytes: 3628
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
#define LL long long
#define F(x,y,z) for(int x=y;x<=z;++x)
#define D(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int N=210;
LL Min(LL x,LL y){return x<y?x:y;}
LL Max(LL x,LL y){return x>y?x:y;}
LL R(){
    LL ans=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if (c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) ans=ans*10+c-'0';
    return ans*f;
}

int vis[N],a[N][N],n;
queue<int> que;
int Sol(int x){
	memset(vis,0,sizeof(vis));
	while(!que.empty())que.pop();
	vis[x]=1;que.push(x);
	while(!que.empty()){
		int u=que.front();que.pop();
		F(i,1,n)
			if(a[u][i]){
				if(!vis[i]){
					vis[i]=vis[u]+1;
					que.push(i);
					continue;
				}
				if(vis[i]==vis[u]-1)continue;
				if(vis[i]==vis[u]+1)continue;
				return -1;
			}
	}
	int an=0;
	F(i,1,n)an=max(an,vis[i]);
	return an;
}
int main(){
	cin>>n;
	F(i,1,n)F(j,1,n){
		char c;cin>>c;
		a[i][j]=c=='1';
	}
	int ans=-1;
	F(i,1,n)ans=max(ans,Sol(i));
	cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 384
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

R = ni()
import math
print(math.pi*2*R)



Measured memory_bytes: 65272
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MAX 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ub upper_bound
#define lb lower_bound
#define zoom ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define precise cout.precision(8); cout << fixed;
#define seed srand(chrono::steady_clock::now().time_since_epoch().count());
const double PI = acos(-1);
using namespace std;

ll findLower(vector<ll>& B, ll M, ll val) {
    ll lb = 0, ub = M + 1, ans = 0;
    while(lb < ub) {
        ll mid = lb + ((ub - lb) / 2);
        if(B[mid] <= val) {
            ans = mid;
            lb = mid + 1;
        }
        else {
            ub = mid;
        }
    }
    return ans;
}

void solve() {
    ll N, M, K, i; cin >> N >> M >> K;
    vector<ll> A(N + 1, 0), B(M + 1, 0);
    for(i = 1; i <= N; i += 1) {
        cin >> A[i];
        A[i] += A[i - 1];
    }
    for(i = 1; i <= M; i += 1) {
        cin >> B[i];
        B[i] += B[i - 1];
    }
    ll ans = 0;
    for(i = 0; i <= N; i += 1) {
        if(A[i] > K) {
            break;
        }
        ll pos = findLower(B, M, K - A[i]);
        ans = (ll)max(ans, i + pos);
    }
    cout << ans;
}

int main() {
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 6380
n=int(input())
l=list(map(int,input().split()))
p=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for h in range(j+1,n):
            if l[i]+l[j]>l[h] and l[i]+l[h]>l[j] and l[j]+l[h]>l[i] and l[i]!=l[j] and l[i]!=l[h] and l[j]!=l[h]:
                p+=1
print(p)

Measured memory_bytes: 9048
local mod = 1000000007

local function bmul(x, y)
  return (x * y) % mod
end

local function badd(x, y)
  return (x + y) % mod
end

local function bsub(x, y)
  return x < y and x - y + mod or x - y
end

local function modpow(src, pow)
  local res = 1
  while 0 < pow do
    if pow % 2 == 1 then
      res = bmul(res, src)
      pow = pow - 1
    end
    src = bmul(src, src)
    pow = pow // 2
  end
  return res
end

local function modinv(src)
  return modpow(src, mod - 2)
end

local fact = {1}
local invs = {1}
local invfact = {1}
for i = 2, 200010 do
  fact[i] = bmul(fact[i - 1], i)
  invs[i] = bmul(mod // i, mod - invs[mod % i])
  invfact[i] = bmul(invfact[i - 1], invs[i])
end

local function getComb(n, k)
  if k == 0 or k == n then return 1 end
  return bmul(fact[n], bmul(invfact[k], invfact[n - k]))
end

local h, w = io.read("*n", "*n")
local a, b = io.read("*n", "*n")
local mid = {}
local mh = h - a
for i = b + 1, w do
  mid[i - b] = getComb(i - 1 + mh - 1, i - 1)
end
local ret = 0
for i = b + 1, w do
  local r = getComb(w - i + a - 1, w - i)
  ret = badd(ret, bmul(mid[i - b], r))
end
print(ret)


Measured memory_bytes: 16496
from __future__ import print_function

import sys
input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return


def reverse_range(Large_a, Small_b, i):  # b < a ,  get [b, a)
    return range(Small_b, Large_a, -i)[::-1]  # range(a, b+1, -1)


def crange(a, b, i):
    return range(a, b + 1, i)


def reverse_crange(Large_a, Small_b, i):
    return range(Small_b, Large_a, -i)


# import math
# import string
# import fractions
# from fractions import Fraction
# from fractions import gcd

# def lcm(n,m):
#     return int(n*m/gcd(n,m))

# import re
# import array
# import copy
# import functools
# import operator

# import collections
# import itertools
# import bisect
# import heapq

# from heapq import heappush
# from heapq import heappop
# from heapq import heappushpop
# from heapq import heapify
# from heapq import heapreplace

# from queue import PriorityQueue as pq

# def reduce(p, q):
#     common = fractions.gcd(p, q)
#     return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

# from operator import mul
# from functools import reduce

# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom

# import random
# import time


def main():
    s = input().strip()
    lll = [i for i in range(1, len(s)-1)[::-2]]
    for i in lll:
        eprint("range", end=": ")
        eprint(lll)
        # closed_i = i + 1
        if s[0: i//2] == s[i//2: i]:
            print(i)
            return
        else:
            eprint("debug ", end=": ")
            eprint("false this time")
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 38512
#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;

int main(void)
{
	string a,b;
	cin >> a >> b;
	int cnt=0;
	for(int i=0;i<=2;i++)
		if(a[i]==b[i])
			cnt++;
	cout << cnt;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main () {
	int n, tmp1, tmp2, tmp;
	int sum = 0;
	scanf ("%d", &n);
	scanf ("%d", &tmp2);
	scanf ("%d", &tmp1);
	for (int i=2; i<n; i++) {
		scanf ("%d", &tmp);
		if (tmp<=tmp1 && tmp1<tmp2)
			sum++;
		else if (tmp>tmp1 && tmp1>=tmp2)
			sum++;
		tmp2 = tmp1;
		tmp1 = tmp;
	}
	printf ("%d\n", sum);
	return 0;
}

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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T1, class T2> inline void minup(T1& m, T2 x){ if(m>x) m=static_cast<T2>(x); }
template<class T1, class T2> inline void maxup(T1& m, T2 x){ if(m<x) m=static_cast<T2>(x); }

#define INF 1000000000
#define MOD 1000000009
#define EPS 1E-9

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void visit(const Graph &g, int v, vector< vector<int> >& scc, stack<int> &S, vector<bool> &inS, vector<int> &low, vector<int> &num, int& time) {
  low[v] = num[v] = ++time;
  S.push(v); inS[v] = true;
  vrep(e, g[v]) {
    int w = e->dst;
    if (num[w] == 0) {
      visit(g, w, scc, S, inS, low, num, time);
      low[v] = min(low[v], low[w]);
    } else if (inS[w])
      low[v] = min(low[v], num[w]);
  }
  if (low[v] == num[v]) {
    scc.push_back(vector<int>());
    while (1) {
      int w = S.top(); S.pop(); inS[w] = false;
      scc.back().push_back(w);
      if (v == w) break;
    }
  }
}

void StronglyConnectedComponents(const Graph& g, vector< vector<int> >& scc) {
  const int n = g.size();
  vector<int> num(n), low(n);
  stack<int> S;
  vector<bool> inS(n);
  int time = 0;
  rep(u, n) if (num[u] == 0) visit(g, u, scc, S, inS, low, num, time);
}

int V, E;
int s, t;
int Q;
int u, v;

int main()
{
  cin >> V >> E;
  Graph g(V);
  vector<vi>scc;
  vi num(V);

  while(E--){
    cin >> s >> t;
    g[s].pb(Edge(s, t, 1));
  }

  StronglyConnectedComponents(g, scc);

  rep(i, scc.size()) rep(j, scc[i].size()) num[scc[i][j]] = i;

  cin >> Q;
  while(Q--){
    cin >> u >> v;
    puts((num[u] == num[v]) ? "1" : "0");
  }

  return 0;
}

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

using namespace std;
using ll = long long;

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

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

  vector<int> a(n + 1);
  for (int i = 1; i < n; ++i) {
    a[i + 1] = a[i];
    if (s[i] == 'C' && s[i - 1] == 'A') ++a[i + 1];
  }

  rep(i, q) {
    int l, r;
    cin >> l >> r;
    int ans = a[r] - a[l - 1];
    if (l >= 2 && s[l - 1] == 'C' && s[l - 2] == 'A') --ans;
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 3844
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N;
  cin >> N;
  ll A[200010];
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] -= i + 1;
  }
  sort(A, A + N);
  ll b = A[N / 2];
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    ans += abs(A[i] - b);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const int N = 10004, MOD = 1E9 + 7;
int dp[N][100][2], d;
vector<int> k;
string s;
int cal(int idx, int sum, int f)
{
	if (idx == k.size())
		return sum == 0;
	if (dp[idx][sum][f] != -1)
		return dp[idx][sum][f];
	int ans = 0, lim;
	if (f)
		lim = k[idx];
	else
		lim = 9;
	for (int i = 0; i <= lim ; ++i)
	{
		if (f)
		{
			if (i < lim)
				ans = (1LL * ans + cal(idx + 1, (sum + i) % d, 0)) % MOD;
			else
				ans = (1LL * ans + cal(idx + 1, (sum + i) % d, 1)) % MOD;
		}
		else
			ans = (1LL * ans + cal(idx + 1, (sum + i) % d, 0)) % MOD;
	}
	return dp[idx][sum][f] = ans;
}
int main(int argc, char const *argv[])
{
	memset(dp, -1, sizeof(dp));
	cin >> s;
	cin >> d;
	for (char c: s)
		k.push_back(c - '0');
	cout << (1LL * cal(0, 0, 1) - 1 + MOD) % MOD;
	return 0;
}


Measured memory_bytes: 9088
import java.util.Scanner;

class Main{
    
    public static void main(String[] args){
        
        Scanner sc =new Scanner(System.in);
        
        int sum=0;
        
        while(true) {
        	
         String s=sc.next();
         if(s.equals("0")) break;
        
         for(int i = 0; i < s.length(); i++) 
			sum+=s.charAt(i)-'0';
		 
         System.out.println(sum);
        
         sum=0;
        }
    }
}


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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    int N;
    cin>>N;
    int c = (N-1)/1000+1;
    cout << c*1000 - N << endl;
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int n = scan.nextInt();
        int c = scan.nextInt();
        int[][] d = new int[c][c];
        for (int i = 0; i < c; i++) {
            for (int j = 0; j < c; j++) {
                d[i][j] = scan.nextInt();
            }
        }
        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = scan.nextInt() - 1;
            }
        }
        Main main = new Main();
        System.out.println(main.solve(n, c, d, g));
    }
    public int solve(int n, int c, int[][] d, int[][] g) {
        if (n == 1) {
            return 0;
        }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if (!map.containsKey((i+j) % 3)) {
                    Map<Integer, Integer> t = new HashMap<>();
                    map.put((i+j) % 3, t);
                }
                Map<Integer, Integer> entry = map.get((i+j) % 3);
                if (!entry.containsKey(g[i][j])) {
                    entry.put(g[i][j], 0);
                }
                Integer count = entry.get(g[i][j]);
                entry.put(g[i][j], count+1);
            }
        }
        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < c; i++) {
            int i_diff = subAnswer(d, map.get(0), i);
            for (int j = 0; j < c; j++) {
                if (i == j) {
                    continue;
                }
                int j_diff = subAnswer(d, map.get(1), j);
                for (int k = 0; k < c; k++) {
                    if (i == k || j == k) {
                        continue;
                    }
                    int k_diff = subAnswer(d, map.get(2), k);
                    answer = Math.min(answer, i_diff + j_diff + k_diff);
                }
            }
        }
        return answer;
    }
    public int subAnswer(int[][] d, Map<Integer, Integer> base, int color) {
        int diff = 0;
        for(int i : base.keySet()) {
            if (i == color) {
                continue;
            }
            int count = base.get(i);
            diff += count * d[i][color];
        }
        return diff;
    }

}


Measured memory_bytes: 94212
#-*-coding:utf-8-*-

def main():
    n = int(input())
    station_list = list(tuple(map(int, input().split())) for _ in range(n-1))
    for i in range(n-1):
        ans = 0
        for j in range(i, n-1):
            c, s, f = station_list[j]
            if ans <= s:
                ans = s
            elif ans % f != 0:
                ans += f - (ans % f)
            ans += c
        print(ans)
    print(0)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
//
//  main.cpp
//  A
//
//  Created by 耿英俊 on 2020/1/10.
//  Copyright © 2020 耿英俊. All rights reserved.
//
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
int main(int argc, const char * argv[]) {
    int k,x;
    cin>>k>>x;
    if(k*500>=x)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define INF (1LL << 60)
using namespace std;
typedef long long ll;

struct edge {
  ll v, dist;
};

struct state {
  ll v, cost;

  bool operator>(const state s) const {
    return cost > s.cost;
  }
};

vector<ll> dijkstra(vector< vector<edge> > &E, ll S) {
  vector<ll> dp(E.size(), INF);
  priority_queue<state, vector<state>, greater<state> > q;
  q.push((state) { S, 0 });

  while(!q.empty()) {
    ll v = q.top().v, cost = q.top().cost;
    q.pop();

    if(dp[v] <= cost) continue;
    dp[v] = cost;

    REP(i, 0, E[v].size()) {
      ll nv = E[v][i].v, ncost = cost + E[v][i].dist;
      if(dp[nv] > ncost) q.push((state) { nv, ncost });
    }
  }

  return dp;
}

int main(void) {
  ll N, M, S, T;
  cin >> N >> M >> S >> T;
  S--; T--;
  vector< vector<edge> > E(N);
  REP(i, 0, M) {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    A--; B--; C--;
    E[A].push_back((edge) { B, D });
    E[B].push_back((edge) { A, D });
    E[B].push_back((edge) { C, D });
    E[C].push_back((edge) { B, D });
    E[C].push_back((edge) { A, D });
    E[A].push_back((edge) { C, D });
  }

  cout << dijkstra(E, S)[T] << endl;
}



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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

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

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  string a, b;
  cin >> a >> b;
  if (a.size() > b.size()) {
    cout << "GREATER" << '\n';
    return 0;
  }
  if (a.size() < b.size()) {
    cout << "LESS" << '\n';
    return 0;
  }
  for (int i = 0; i < a.size(); i++) {
    if (a[i] > b[i]) {
      cout << "GREATER" << '\n';
      return 0;
    }
    if (a[i] < b[i]) {
      cout << "LESS" << '\n';
      return 0;
    }
  }
  cout << "EQUAL" << '\n';
}


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

int n, x, y, k[2005], dist[2005][2005];
vector<vector<int>> adjList;

void bfs(int s) {
	queue<int> q;
	q.push(s);
	dist[s][s] = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < adjList[u].size(); i++) {
			int v = adjList[u][i];
			if (dist[s][v] == -1) {
				dist[s][v] = dist[s][u] + 1;
				q.push(v);
			}
		}
	}
}

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

	cin >> n >> x >> y;
	adjList.resize(n+5);
	memset(dist, -1, sizeof(dist));

	for (int i = 1; i < n; i++) {
		adjList[i].push_back(i+1);
		adjList[i+1].push_back(i);
	}
	adjList[x].push_back(y);
	adjList[y].push_back(x);

	for (int i = 1; i <= n; i++) {
		bfs(i);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i+1; j <= n; j++) {
			k[dist[i][j]]++;
		}
	}

	for (int i = 1; i <= n-1; i++) {
		cout << k[i] << '\n';
	}
	
	return 0;
}

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

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

  if (x =="A") {
    cout << "T" << endl;
  }
  else if (x =="T") {
    cout << "A" << endl;
  }
  else if (x =="G") {
    cout << "C" << endl;
  }
  else {
    cout << "G" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
 
const int N=1e5+5,MAX=3e7,MOD=1e9+7;
 
using namespace std;


int main()
{


    	int n;

    	cin>>n;

    	priority_queue<double,vector<double>,greater<double>>q;

    	for(int i=0,x;i<n;i++)cin>>x,q.push(x);

    	while(sz(q)>1){
    		double x = q.top();
    		q.pop();
    		x = (x+q.top())/2;
    		q.pop();
    		q.push(x);
    	}
    	printf("%.9lf\n",q.top() );	
	
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}


fn main() {
    /*
    assert_eq!(abc(), "Yes");
    assert_eq!(abc(101), "No");
    assert_eq!(abc(999999999), "Yes");
    */

    input!{
        x: i64,
        y: i64,
    }
    let result = x + y /2;
    println!("{}", result);
}


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

X, Y, A, B, C = map(int, input().split())
P = sorted(list(map(int, input().split())), reverse=True)
Q = sorted(list(map(int, input().split())), reverse=True)
R = sorted(list(map(int, input().split())), reverse=True)

ans = sum(P[:X]) + sum(Q[:Y])
x = X-1
y = Y-1
for z in range(C):
    if x < 0:
        if R[z] > Q[y]:
            ans += R[z] - Q[y]
            y -= 1
    elif y < 0:
        if R[z] > P[x]:
            ans += R[z] - P[x]
            x -= 1
    else:
        if R[z] > P[x] >= Q[y]:
            ans += R[z] - Q[y]
            y -= 1
        elif R[z] > Q[y] > P[x]:
            ans += R[z] - P[x]
            x -= 1
        elif P[x] >= R[z] > Q[y]:
            ans += R[z] - Q[y]
            y -= 1
        elif Q[y] >= R[z] > P[x]:
            ans += R[z] - P[x]
            x -= 1
print(ans)


Measured memory_bytes: 94180
using System;
using System.Collections.Generic;
using System.Linq;

namespace ProgramingStudying2
{
    class Program
    {

        static void Main(string[] args)
        {
            var nm = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var n = nm[0];
            var m = nm[1];
            Console.WriteLine((n - 1) * (m - 1));
        }
    }
}


Measured memory_bytes: 28288
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
#include <cstdlib>
#include <sstream>
#include <bitset>
using namespace std;

typedef long long ll;


int main()
{
    ll N;
    cin >> N;
    ll mod=1000000007;
    vector< vector <ll> > cnt(60, vector<ll>(2, 0));
    for(int i=0; i<N; i++){
        ll a;
        cin >> a;
        for(int j=0; j<60; j++){
            cnt[j][a%2]++;
            a/=2;
        }
    }
    ll ans=0, tmp=1;
    for(int i=0; i<60; i++){
        ans+=tmp*cnt[i][0]%mod*cnt[i][1]%mod;
        ans%=mod;
        tmp*=2;
        tmp%=mod;
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
N=int(input())

ans=[1]
cnt=1
while 6**cnt<100000:
  ans.append(6**cnt)
  cnt+=1
cnt=1
while 9**cnt<100000:
  ans.append(9**cnt)
  cnt+=1

bfs=[10**10 for x in range(N+1)]
bfs[0]=0
for i in range(N+1):
  for j in range(len(ans)):
    if i+ans[j]<=N:
      bfs[i+ans[j]]=min(bfs[i+ans[j]],bfs[i]+1)

print(bfs[N])

Measured memory_bytes: 3864
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w,g; cin>>h>>w>>g;
  string arr[h];
  for(int i=0;i<h;i++) cin>>arr[i]; 
  int tb=0;
  for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(arr[i][j]=='#') tb++; 
  int dp1[h],dp2[w],res=0;
  for(int i=0;i<h;i++){int cnt=0; for(int j=0;j<w;j++) if(arr[i][j]=='#') cnt++; dp1[i]=cnt;  }
  for(int i=0;i<w;i++){int cnt=0; for(int j=0;j<h;j++) if(arr[j][i]=='#') cnt++; dp2[i]=cnt; }
  for(int i=0;i<(1<<h);i++){
    int ans=tb;
    //cout<<ans<<endl;
    for(int j=0;j<h;j++)
      if(i&(1<<j)) ans-=dp1[j];
    for(int k=0;k<(1<<w);k++){
      int tmp=ans;
      for(int m=0;m<w;m++) 
        if(k&(1<<m)) tmp-=dp2[m]; 
      for(int p=0;p<h;p++)
        for(int q=0;q<w;q++)
          if((i&(1<<p))&&(k&(1<<q))&&arr[p][q]=='#') tmp++;
       if(tmp==g) res++;
    }
    }
         cout<<res<<endl;
    }

Measured memory_bytes: 3484
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const int inf = 1e9;

int N;
vector<int> hurui_v(int n) {
    vector<int> v;
    bool *isPrime_v;
    isPrime_v = new bool[n + 1]; // 処理用のメモリ確保

    // 初期化
    isPrime_v[0] = isPrime_v[1] = false;
    for (int i = 2; i < n + 1; i++) isPrime_v[i] = true;

    // isPrime[0~n]で素数のものだけtrueにする
    for (int i = 2; i*i <= n; i++) {
        for (int j = i * 2; j < n + 1; j += i) {
            isPrime_v[j] = false;
        }
    }

    // 素数のみ追加
    for (int i = 0; i < n + 1; i++) {
        if (isPrime_v[i]) v.push_back(i);
    }

    delete[] isPrime_v; //メモリ解放
    return v;
}

int mo[10];
vector<int> ans;
int main(){
    cin>>N;
    vector<int> v = hurui_v(55555);
    for(auto vv:v){
        mo[vv%5]++;
        if(vv%5==1){
            ans.push_back(vv);
            if(ans.size()==N) break;
        }
    }
    for(auto a: ans){
        if(a==ans.back()){
            p(a);
        }
        else cout<<a<<" ";

    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
#define i64 int64_t
void d()
{
  i64 a, b;
  cin >> a >> b;
  i64 count[64];
  memset(count, 0, sizeof(count));
  for (i64 i = a; i <= b; i++)
  {
    for (int j = 0; j < 64; j++)
    {
      if (i & (1ll << j))
      {
        count[j]++;
      }
    }
  }
  i64 sum = 0;
  for (int i = 0; i < 64; i++)
  {
    if (count[i] % 2 != 0)
    {
      sum += (1ll << i);
    }
  }
  cout << sum;
}
void c()
{
  i64 n, m;
  cin >> n >> m;
  map<i64, i64> ab;
  for (int i = 0; i < n; i++)
  {
    i64 a, b;
    cin >> a >> b;
    auto itr = ab.find(a);
    if (itr == ab.end())
    {
      ab[a] = b;
    }
    else
      ab[a] += b;
  }
  i64 sum_x = 0;
  i64 sum_y = 0;
  for (auto itr = ab.begin(); itr != ab.end(); itr++)
  {
    //cout << itr->first << " " << itr->second << endl;
    if (m - sum_x - itr->second > 0)
    {
      sum_x += itr->second;
      sum_y += itr->second * itr->first;
    }
    else
    {
      sum_y += (m - sum_x) * itr->first;
      sum_x += m - sum_x;
    }
    if (sum_x == m)
      break;
  }
  cout << sum_y;
}
void b()
{
  int n, m, c;
  cin >> n >> m >> c;
  int b[m], a[n][m];
  for (int i = 0; i < m; i++)
    cin >> b[i];
  for (int j = 0; j < n; j++)
  {
    for (int i = 0; i < m; i++)
      cin >> a[j][i];
  }
  int count = 0;
  for (int j = 0; j < n; j++)
  {
    int sum = c;
    for (int i = 0; i < m; i++)
      sum += a[j][i] * b[i];
    if (sum > 0)
      count++;
  }
  cout << count;
}
void a()
{
  int H, W, h, w;
  cin >> H >> W >> h >> w;
  cout << H * W - (h * W + H * w - h * w);
}
int main(void)
{
  a();
  //b();
  //c();
  //d();
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include "algorithm"
#include "bits/stdc++.h"
#define ll long long
using namespace std ;
int count(int a){
    int ans=0;
    while(a){
        a=a&(a-1);
        ans++;
    }
    return ans;
}
ll fastpow(int n,int modn){
    ll b=2;
    ll res=1;
    while(n){
        if(n&1)
            res = (b*res)%modn;
        b=(b*b)%modn;
        n>>=1;
    }
    return res%modn;
}
int main(){
    int m;
    string n;
    cin>>m>>n;
    int c=0;
    for(int i=0;i<m;i++){
        if(n[i]=='1')
            c++;
    }
    int p=0,q=0;
    for(int i=0;i<m;i++){
        if(n[i]=='1'){
            p+=fastpow(m-1-i,c+1);
            p%=c+1;
            if(c!=1){
                q+=fastpow(m-1-i,c-1);
                q%=c-1;
            }
        }
    }
    if(c==1)
        q=0;
    for(int i=0;i<m;i++){
        int flag=0;
        int pp=0;
        if(n[i]=='0')
            pp=(p+fastpow(m-1-i,c+1))%(c+1);
        else if(c==1)
            flag++;
        else pp=(q-fastpow(m-1-i,c-1)+c-1)%(c-1);
        if(flag)
            cout<<"0"<<endl;
        else {
            int anss = 1;
            while (pp) {
                pp %= count(pp);
                anss++;
            }
            cout << anss << endl;
        }
    }
    return 0;
}

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

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    priority_queue<LL> pq;
    for(int i = 0; i < N; i++){
        LL a;
        scanf("%lld", &a);
        pq.push(a);
    }
    
    // 2. priority_queue の 先頭要素 に, 常に 割引券 を 使用.
    while(M > 0){
        LL a = pq.top();
        pq.pop();
        a /= 2;     // 先頭要素に割引券使用.
        pq.push(a); // 割引券適用後の金額を追加.
        M--;
    }
    
    // 3. すべての品物を買うために必要なお金の最小値は？
    LL ans = 0;
    while(!pq.empty()){
        LL a = pq.top();
        pq.pop();
        ans += a;
    }
    
    // 4. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

Measured memory_bytes: 1400
#include <iostream>

using namespace std;

int main(){
  long long n;
  cin>>n;
  
  long long a;
  cin>>a;
  for(int i=1;i<5;i++){
    long long temp;
    cin>>temp;
    if(temp<a)a=temp;
  }
  
  if(n<=a)cout<<5;
  else{
    long long time=n/a+4;
    if(n%a==0)cout<<time;
    else cout<<(time+1);
  }
  
  return 0;
}

Measured memory_bytes: 256