akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll mod =1000000007;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX*/                      int gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*"lcm"   MIN*/                      int lcm(ll a,ll b){return a*b/gcd(a,b);}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int main(){
int n,m;
cin >> n >> m;
map<int,char>ma;
vector<pair<int,char>>z(m);
for(int i=0;i<m;i++){
   int a;
   char b;
   cin >> a >>b;
   z.at(i).first=a;
   z.at(i).second=b;
   if(ma.count(a)&&ma.at(a)!=b){cout<<-1<<endl; return 0;}
   else ma[a]=b;
   if(a==1&&b=='0'&&n!=1){cout<<-1<<endl; return 0;}
}
string s="";
for(int i=0;i<n;i++){
   s+='Z';
}
for(int i=0;i<m;i++){
 s.at(z.at(i).first-1)=z.at(i).second;
}
for(int i=1;i<n;i++){
   if(s.at(i)=='Z')s.at(i)='0';
}
if(s.at(0)=='Z'&&n==1)s.at(0)='0';
if(s.at(0)=='Z'&&n!=1)s.at(0)='1';
cout << s<<endl;
}





Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const long long LINF = 1000000000000000018ll;
const int INF = 1000000009;
const int mod = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << fixed;

  int h, w;
  cin >> h >> w;
  vector<string> maze(h);
  for (int i = 0; i < h; i++) {
    cin >> maze[i];
  }
  int dp[102][102];
  for (int i = 0; i < 102; i++) {
    for (int j = 0; j < 102; j++) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = (maze[0][0] == '#');
  for (int y = 0; y < h; y++) {
    for (int x = 0; x < w; x++) {
      if (x > 0) {
        if (maze[y][x] == '#' && maze[y][x-1] == '.') {
          dp[y][x] = min(dp[y][x], dp[y][x-1]+1);
        } else {
          dp[y][x] = min(dp[y][x], dp[y][x-1]);
        }
      }
      if (y > 0) {
        if (maze[y][x] == '#' && maze[y-1][x] == '.') {
          dp[y][x] = min(dp[y][x], dp[y-1][x]+1);
        } else {
          dp[y][x] = min(dp[y][x], dp[y-1][x]);
        }
      }
    }
  }
  cout << dp[h-1][w-1] << endl;
  return 0;
}


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    LL K, N;
    cin >> K >> N;
    vector<LL> A(N*2);
    REP(i, N) {
        cin >> A[i];
    }
    FOR(i, N, 2*N) {
        A[i] = A[i - N] + K;
    }
    LL len = 0;
    FOR(i, 1, N) {
        len += A[i] - A[i - 1];
    }
    LL res = len;
    FOR(i, N, 2*N) {
        len += A[i] - A[i - 1];
        len -= A[i - N + 1] - A[i - N];
        res = min(res, len);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3328
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

struct UnionFind{
    vector<int> data;
    UnionFind(int size){
        data=vector<int>(size,-1);
    }
    bool union_set(int x,int y){
        x=root(x);
        y=root(y);
        if(x!=y){
            if(data[y]<data[x])swap(x,y);
            data[x]+=data[y];
            data[y]=x;
        }
        return x!=y;
    }
    bool find(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0?x:data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    GI(N);
    GVI(A,N);
    vector<int> B=A;
    sort(ALL(B));
    int med=B[N/2-1],pmed=B[N/2];
    FOR(i,N){
        if(A[i]<=med){
            print(pmed);
        }else{
            print(med);
        }
    }
    return 0;
}

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

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

    int ans = 0;
    for (int i = 0; i < s.size(); i++)
        if (s[i] != t[i])
            ans++;
    
    cout << ans << endl;
}

Measured memory_bytes: 3912
use List::Util qw/sum/;
$N = <>;chomp $N;

$upper_line = <>;chomp $upper_line;
$under_line = <>;chomp $under_line;

@upper_all = ();
@under_all = ();
$upper_sum = 0;
for my $masu (split / /, $upper_line) {
    push @upper_all, $masu;
    $upper_sum += $masu;
}

for my $masu (split / /, $under_line) {
    push @under_all, $masu;
}

for my $index (reverse 1..$#upper_all) {
    $upper_all[$index] = $under_all[$index-1];

    my $sum = sum @upper_all;
    $upper_sum = $sum if $sum >= $upper_sum;
}

print $upper_sum + $under_all[$#under_all];


Measured memory_bytes: 640
#include<stdio.h>
int n,m,a[105];
int sum=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    scanf("%d",&m);
    while(m--){
        int p,x;
        scanf("%d%d",&p,&x);
        
        printf("%d\n",sum-a[p]+x);
    }
    return 0;
}

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

int main()
{
    std::string s;
    std::cin >> s;
    int p = 2019;
    int n = s.size();
    long long ans = 0;
    if (p == 2)
    {
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '0' || s[i] == '2' || s[i] == '4' || s[i] == '6' || s[i] == '8')
            {
                ans += i + 1;
            }
        }
    }
    else if (p == 5)
    {
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '0' || s[i] == '5')
            {
                ans += i + 1;
            }
        }
    }
    else
    {
        int rem10 = 10 % p;
        int rem10pow = 1;
        std::vector<int> rem;
        rem.resize(n + 1);
        rem[n] = 0;
        for (int i = n - 1; i >= 0; --i)
        {
            rem[i] = (rem[i + 1] + ((s[i] - '0') % p) * rem10pow) % p;
            rem10pow = (rem10pow * rem10) % p;
        }

        std::vector<long long> count;
        count.resize(p);
        std::fill(count.begin(), count.end(), 0);
        for (int i = 0; i <= n; ++i)
        {
            ++count[rem[i]];
        }

        for (int i = 0; i < p; ++i)
        {
            ans += count[i] * (count[i] - 1);
        }
        ans /= 2;
    }
    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 4328
#include<iostream>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define each(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

const int mod = (int)1e8 + 7;
int h, w, pw[11];
char in[12][12];
int dp[2][11][3][60000];

int main(){
	pw[0] = 1;
	rep(i, 10) pw[i + 1] = pw[i] * 3;
	
	cin >> h >> w;
	rep(i, h) cin >> in[i];
	
	int cur = 0, next = 1;
	dp[0][0][0][0] = 1;
	
	rep(i, h){
		memset(dp[next], 0, sizeof(dp[next]));
		rep(j, w){
			rep(l, 3) rep(u, pw[w]) if(dp[cur][j][l][u]){
				
				int tu = u / pw[j] % 3;
				
				if(in[i][j] == '.'){
					if(tu && l) continue;
					(dp[cur][j + 1][l][u] += dp[cur][j][l][u]) %= mod;
					continue;
				}
				int rest = in[i][j] - '0' - tu - l;
				rep(nl, 3){
					int nu = rest - nl;
					if(nu < 0 || nu > 2) continue;
					(dp[cur][j + 1][nl][u + pw[j] * (nu - tu)] += dp[cur][j][l][u]) %= mod;
				}
			}
		}
		rep(u, pw[w]) dp[next][0][0][u] = dp[cur][w][0][u];
		swap(cur, next);
	}
	cout << dp[cur][0][0][0] << endl;
	
	return 0;
}

Measured memory_bytes: 16644
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

#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(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(o) {cerr<<#o<<" "<<o<<endl;}
#define DUMPC(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (string s; cin >> s;) {
		string ans = "d";
		REP(i, 3) {
			if (s[0 + i * 3] == s[1 + i * 3] && s[1 + i * 3] == s[2 + i * 3]) {
				if (s[0 + i * 3] == 'o')ans = "o";
				if (s[0 + i * 3] == 'x')ans = "x";
			}
		}
		REP(i, 3) {
			if (s[0 + i] == s[3 + i] && s[3 + i] == s[6 + i]) {
				if (s[0 + i] == 'o')ans = "o";
				if (s[0 + i] == 'x')ans = "x";
			}
		}
		if (s[0] == s[4] && s[4] == s[8]) {
			if (s[0] == 'o')ans = "o";
			if (s[0] == 'x')ans = "x";
		}
		if (s[2] == s[4] && s[4] == s[6]) {
			if (s[2] == 'o')ans = "o";
			if (s[2] == 'x')ans = "x";
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    // Atcoder
    // template: cpp
    ll x, y, cnt = 0;
    cin >> x >> y;
    for(ll i = x; i <= y; i += i) {
        cnt++;
    }
    cout << cnt;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    float k;
    cin>>n;
    if(n%2==0)
        cout<<"0.5000000000";
    if(n%2!=0)
    {
        k=(n+1)/2;
        k=k/n;
        cout<<k;
    }


}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#include <map>
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using Graph = vector<vector<int>>;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll modinv(ll a, ll m){
    ll b = m, u = 1, v = 0;
    while(b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if(u < 0) u += m;
    cout << u << endl;
    return u;
}

ll paty_counter(ll level, ll x){
    ll size = pow(2, level+2) - 3;
    ll pmi = pow(2, level) - 1;
    if(x == 0){
        return 0;
    }else if(level == 0){    
        return 1;
    }else{
        if(x <= (size - 1)/2){
            return paty_counter(level-1, x-1);
        }else{
            return pmi + 1 + paty_counter(level-1, x - pow(2, level+1) + 3 - 2);
        }
    }

}
 
int main() {
    ll x,k,d;
    cin >> x >> k >> d;
    ll m = abs(x) / d;
    ll mstar;
    ll ans = 0;
    if(m > k){
        // if(k % 2 == 0){
        //     ans = x;
        // }else {
            if(abs(x-k*d)<abs(x+k*d)){
                ans = x-k*d;
            } else {
                ans = x+k*d;
            }
        //}
    }else {
        if((k - m)%2 == 0){
            if(abs(x - m*d)<abs(x + m*d)){
                ans = x-m*d;
            } else {
                ans = x+m*d;
            }
        } else {
            if(x >= 0){
                if(abs(x - d *(m-1)) < abs(x - d*(m+1))){
                    mstar = m-1;
                    ans = x - d *(m-1);
                } else {
                    mstar = m+1;
                    ans = x - d*(m+1);
                }
            }else {
                if(abs(x + d *(m-1)) < abs(x + d*(m+1))){
                    mstar = m-1;
                    ans = x + d *(m-1);
                } else {
                    mstar = m+1;
                    ans = x + d *(m+1);
                }
            }
        }
    }
    cout << abs(ans) << endl;

}



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

int main(){
  int N; cin >> N;
  vector<int>B(N-1);
  for(int i=0;i<N-1;i++){
    cin >> B.at(i);
  }
  long long sum = 0;

  for(int i=0;i<N-2;i++){
    sum += min(B.at(i),B.at(i+1));
  }
  cout << B.at(0)+sum+B.at(N-2) << endl;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
 
using namespace std;
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red
 
inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}
 
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m;
string s;
int dp[N];
int pr[N];
 
int main () {
   SpeedForce;
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i ++) {
		if (s[i] == '0') continue;
		int j = i;
		while (j < n && s[j + 1] == '1') {
			j++;
		} 	
		if (j - i + 1 >= m) {
			cout << -1;
			exit(0);
		}
		i = j;
	}
	for (int i = 1; i <= n; i ++) dp[i] = inf;
   vector < int > ans;
	for (int i = n; i >= 1; ) {
		for (int j = min(i, m); j >= 0; j --) if (s[i-j] == '0') {
			ans.pb(j);
			i -= j;
			break;
		}
	//	cerr << i << '\n';
	}
 
	reverse(every(ans));
 
	//cout << sz(ans) << '\n';
	for (auto it : ans)
		cout << it << ' ';
 
   return Accepted;
}
 
// B...a

Measured memory_bytes: 3144
#include <stdio.h>

int main(void) {
	int h, w;
	int i, j;
	
	while(1) {
		scanf("%d %d", &h, &w);
		if(h == 0 && w == 0) {
			break;
		}
		
		for(i = 0; i < h; i++) {
			for(j = 0; j < w; j++) {
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 572
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
x,a,b = LI()
if abs(a-x) < abs(b-x):
    print("A")
else:
    print("B")
#B

#C
"""
n = I()
d = defaultdict(int)
a = LI()
for i in a:
    d[i] += 1
d = list(d.items())
d.sort(key = lambda x:-x[0])
l = 0
k = 0
for i,j in d:
    if j >= 2:
        if l == 0:
            l = i
        else:
            k = i
        if j >= 4:
            k = i
    if k != 0:break
print(l*k)
"""

#D
"""
n = I()
s1 = S()
s2 = S()
ans = 0
i = 0
key = 1
d = defaultdict(int)
while i < n:
    if s1[i] == s2[i]:
        if not d[s1[i]]:
            d[s1[i]] = 1
            if i == 0:
                ans = 3
            else:
                if key:
                    ans *= 2
        key = 1
    else:
        if not d[s1[i]] and not d[s2[i]]:
            d[s1[i]] = 1
            d[s2[i]] = 1
            if i == 0:
                ans = 6
            else:
                if key:
                    ans *= 2
                else:
                    ans *= 3
        if not d[s1[i]]:
            d[s1[i]] = 1
            if not key:
                ans *= 2
        if not d[s2[i]]:
            d[s2[i]] = 1
            if not key:
                ans *= 2
        key = 0
        i += 1
    i += 1
    ans %= mod
print(ans)
"""

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 38512
n, k = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort(reverse=True)
# print(A)
l = -1
r = 10**12 + 2
mid = (l+r)//2
while r-l>1:
    m = 0
    for i in range(n):
        aa = mid // F[i]
        m += max(0, A[i]-aa)
    if m > k:
        l = mid
    else:
        r = mid
    mid = (l+r)//2

print(l+1)

Measured memory_bytes: 119756
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 1000000000
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main(){
  ll N;
  cin >> N;
  vector<ll> P(N);
  rep(i, N){
    cin >> P.at(i);
  }
  ll cnt = 0;
  ll mini = INF;
  rep(i, N){
    if(chmin(mini, P.at(i))){
      cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 1792
# Problem https://atcoder.jp/contests/abc082/tasks/abc082_b
# Python 1st Try


yes = "Yes"
no = "No"


def solver(wordStrS, wordStrT):
    result = ""
    wordSStr = ''.join(list(sorted(wordStrS)))
    strTSort = ''.join(list(reversed(list(sorted(wordStrT)))))
    if wordSStr < strTSort:
        result = yes
    else:
        result = no
    return result


if __name__ == "__main__":
    result = ''
    s = input()
    t = input()
    result = solver(s, t)
    print(result)


Measured memory_bytes: 3060
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    long A, B;
    scan(A, B);
    writeln(A * B);
}


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

using namespace std;

#define REP(i, n)   for(int i = 0; i < (n); i++)
#define REPS(i, n)  for(int i = 1; i <= (n); i++)
#define RREP(i, n)  for(int i = (n)-1; i >= 0; i--)
#define RREPS(i, n) for(int i = (n); i > 0; i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define mt make_tuple
#define pb push_back

using ll  = long long;
using pi  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vs  = vector<string>;
using vb  = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll  INFL = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-9;

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

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll x; cin >> x;
    ll ans = x / 11 * 2;
    x %= 11;
    if(x == 0);
    else if(x > 6) ans += 2;
    else ans++;
    cout << ans << endl;
}


Measured memory_bytes: 3624
n, c, k = map(int, raw_input().split())
t = [int(raw_input()) for _ in xrange(n)]
t.sort()
cnt = 0
check = [False] * n
for i in xrange(n):
    if check[i]:continue
    check[i] = True
    lt = t[i] + k
    for j in xrange(i, min(i + c, n)):
        if t[j] > lt :break
        check[j] = True
    cnt += 1
print cnt


Measured memory_bytes: 6712
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int v[3][3];
  rep(i, 3){
    rep(j, 3){
      cin >> v[i][j];
    }
  }
  int n;
  cin >> n;
  vector<int> t(n);
  rep(i, n) cin >> t[i];
  rep(i, 3){
    rep(j, 3){
      for(int k = 0; k < n; k++){
        if(v[i][j] == t[k]){
          v[i][j] = -1;
        }
      }
    }
  }
  for(int i = 0; i < 3; i++){
    int cnt = 0;
    for(int j = 0; j < 3; j++){
      if(v[i][j] == -1){
        cnt++;
      }
    }
    if(cnt == 3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  for(int i = 0; i < 3; i++){
    int cnt = 0;
    for(int j = 0; j < 3; j++){
      if(v[j][i] == -1) cnt++;
    }
    if(cnt == 3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  int cnt = 0;
  for(int i = 0; i < 3; i++){
    if(v[i][i] == -1)cnt++;
  }
  if(cnt == 3){
    cout << "Yes" << endl;
    return 0;
  }
  if(v[0][2] == -1 && v[1][1] == -1 && v[2][0] == -1){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  system("pause");
}

Measured memory_bytes: 504
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  vector<int> b(103);
  for(int i=0;i<103;i++){
    b[i]=0;
  }
  
  for(int i=0;i<k;i++){
    int d;
    cin>>d;
    for(int j=0;j<d;j++){
      int a;
      cin>>a;
      b[a-1]=1;
    }
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(b[i]==0)ans++;
  }
  cout<<ans<<endl;
  
  
  
}

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

using namespace std;
int n,maxim,ans,lgmax,pozmax,lungime1[100001],lungime2[100001],poz;
pair<int,int> v[100001];
bool comp(pair<int,int> a, pair<int,int> b)
{
    if(a.first<b.first)
        return 1;
    else if(a.first==b.first&&a.second<b.second)
        return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].first>>v[i].second;
    sort(v+1,v+n+1,comp);
    for(int i=1;i<=n;i++)
        if(v[i].second-v[i].first+1>lgmax)
    {
        lgmax=v[i].second-v[i].first+1;
        poz=i;
    }
    ans+=lgmax;
    int l=1;
    int r=1000000000;
    for(int i=1;i<=n;i++)
        if(i!=poz)
    {
        l=max(v[i].first,l);
        r=min(v[i].second,r);
    }
    ans+=max(0,r-l+1);
    maxim=ans;
    l=1;
    r=1000000000;
    for(int i=1;i<=n;i++)
    {
        l=max(v[i].first,l);
        r=min(v[i].second,r);
        lungime1[i]=max(0,r-l+1);
    }
    l=1;
    r=1000000000;
    for(int i=n;i>=1;i--)
    {
        l=max(v[i].first,l);
        r=min(v[i].second,r);
        lungime2[i]=max(0,r-l+1);
        if(i>1)
        {
            if(lungime2[i]+lungime1[i-1]>maxim)
                maxim=lungime2[i]+lungime1[i-1];
        }
    }
    cout<<maxim;
    return 0;
}


Measured memory_bytes: 1792
//submitted by HimJ
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define pb push_back
#define fi first
#define se second
#define fr(i,s,e) for(i=s;i<e;i++)
#define ms(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
const int mxn=1e5+1;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  ll t=1;
  //cin>>t;
    while(t--){
            int n,i;
    string s;
    cin>>n>>s;
    int le[n]={0},re[n]={0},lw[n]={0},rw[n]={0};
    fr(i,0,n)
    {
    	if(i!=0)
        lw[i]+=lw[i-1];
        if(s[i]=='W')
            lw[i]++;
    }
    for(i=n-1;i>=0;i--)
    {
    	if(i!=n-1)
        re[i]+=re[i+1];
        if(s[i]=='E')
            re[i]++;
    }
    int ans=n;
    fr(i,0,n)
    {
    	int lef=0,rig=0;
    	if(i!=0)
    	lef=lw[i-1];
    	if(i!=n-1)
    	rig=re[i+1];
        ans=min(ans,lef+rig);
    }
    cout<<ans;
    

    }
  return 0;
  }



Measured memory_bytes: 5396
import std.stdio;
import std.string;
import std.conv;
import std.range;
import std.array;
import std.algorithm;

void main() {
    string input = "4823108376";

    while ((input = readln.chomp).length != 0) {
        while (input.length > 1) {
            string output;
            for (int i = 0; i < input.length-1; i++) {
                output ~= (((input[i] - '0')+(input[i+1] - '0'))%10).to!string;
            }
            input = output;
        }

        writeln(input);
    }
}

Measured memory_bytes: 1060
from collections import deque

class Queue:

  def __init__(self):
    self.Q = deque()

  #0:enqueue
  def enqueue(self,x):
    self.Q.appendleft(x)

  #1:front
  def front(self):
    if len(self.Q) > 0:
      print(self.Q[-1])
      
  #2:dequeue
  def dequeue(self):
    if len(self.Q) > 0:
      self.Q.pop()

n,q = map(int,input().split())
QList = list()

for i in range(n):
  QList.append(Queue())

for i in range(q):
  cmd = input()
  
  if cmd.startswith("0"):
    c,t,x = map(int,cmd.split(" "))
    QList[t].enqueue(x)
    
  if cmd.startswith("1"):
    c,t = map(int,cmd.split(" "))
    QList[t].front()
  
  if cmd.startswith("2"):
    c,t = map(int,cmd.split(" "))
    QList[t].dequeue()



Measured memory_bytes: 14700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> a(N);
    for(int i = 0; i < N; i++) cin >> a[i];
    a.push_back(2000000000);
    sort(a.begin(), a.end(), greater<int>());
    bool win;
    bool before = true;
    bool after = true;
    int checked = 0;
    int left;
    int right;
    a.push_back(-1);
    for(int i = N; i >= 1; i--) {
        if(a[i] != a[i + 1]) {
            left = checked + 1;
            right = a[i];
            win = ((i+a[i]-1) % 2 == 0);
        }
        checked = right;
        //cerr << i << " " << a[i] << " " << win << " " << left << " " << right << endl;
        if(win == false) {
            if(left <= i && right >= i - 1) before = false;
            if(left <= i + 1 && right >= i) after = false;
        }
    }
    if(before || after) cout << "First" << endl;
    else cout << "Second" << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {


    public static void main(String[] args) throws IOException {
        Scanner s = new Scanner(System.in);
        String word = s.next();
        String res = "";
        for(int i=0;i<word.length();i++){
            if(word.charAt(i)=='1')res+='9';
            else if(word.charAt(i)=='9')res+='1';
            else res+=word.charAt(i);
        }
        System.out.println(res);


    }




}


class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

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

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

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

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}

Measured memory_bytes: 25304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

ll calc(ll x) {
    return x * x * x * x * x;
}

int main() {
    ll x;
    cin >> x;
    for (ll a = -1000; a <= 1000; a++) {
        for (ll b = -1000; b <= 1000; b++) {
            if (calc(a) - calc(b) == x) {
                cout << a << " " << b << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD (int)(1e9+7)
#define ceil(x, y) (x%y==0? (x/y) : (x/y+1))
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define FOR1(i, N) for(int i = 1; i <= N; ++i)
#define vi vector <int>
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mset(a, v) memset(a, v, sizeof(a))
#define all(v) (v).begin(), (v).end()
#define INF 2e9
#define EPS 1e-9
#define int long long
#define MAX 3009
double dp[MAX][MAX];
double fun(double p[], int N, int heads, int heads_required){
    if(dp[N][heads] != -1.0) return dp[N][heads];
    if(N == 0){
        if(heads > heads_required) return dp[N][heads] = 1.0;
        else return 0.0;
    }
    else return dp[N][heads] = p[N]*fun(p, N-1, heads+1, heads_required) + (1-p[N])*fun(p, N-1, heads, heads_required);
    /*Hint: make probability tree starting from last coin. Each coin can be either heads or tails
    If on a path from root to leaf there are more than N/2 heads then the path is valid else invalid*/

}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	int T = 1;
	//cin >> T;
	FOR1(i, T)
	{
		//cout << "Case #" << i << ": ";
		int N; cin >> N;
        double p[N+1];
        FOR1(i, N) cin >> p[i];
        cout << fixed << setprecision(10);
        FOR(i, MAX){
            FOR(j, MAX){
                dp[i][j] = -1.0;
            }
        }
        cout << fun(p, N, 0, N/2);
		cout<<'\n';
	}
	return 0;
}


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

using namespace std;

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

  vector<pair<int,int>> movie;
  int num[100] = {0};
  
  for(int i = 0;i < n;++i){
    int a,b;
    cin>>a;
    cin>>b;

    movie.push_back(make_pair(a,b));
  }
  sort(movie.begin(),movie.end());

  int sum = 0;
  for(int i = 1;i <= 31;++i){
    int begin = 0;
    int end = 0;
    int place = 0;
    int times = 0;
    int check = 0;

    for(pair<int,int> e : movie){
      if(i >= e.first && i <= e.second){
        if(check == 0){
          begin = e.first;
          end = e.second;
          place = times;
          check = 1;
        }
        else{
          if(num[place] == 1 && num[times] == 0){
            begin = e.first;
            end = e.second;
            place = times;
          }
          else if(num[place] == 0 && num[times] == 0){
            if(end > e.second){
              begin = e.first;
              end = e.second;
              place = times;
            }
          }
        }
      }
      ++times;
    }

    if(num[place] == 0){
      sum += 100;
      num[place] = 1;
    }
    else{
      sum += 50;
    }
  }

  cout<<sum<<endl;

  return 0;
}


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

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

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  int a,b; cin >> a >> b;

  if(a > b) swap(a,b);

  int ans;
  if(a == 1 && b == 2) { 
    ans = 3;
  }
  if(a == 2 && b == 3) { 
    ans = 1;
  }
  if(a == 1 && b == 3) { 
    ans = 2;
  }
  cout << ans << endl;

}


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

using namespace std;

int main() {
    int n, l, ans = 0, apple = 999999;
    cin >> n >> l;
    for (int i = 0; i < n; i++) {
        ans += l + i;
        if (abs(apple) > abs(l + i))
            apple = l + i;
    }
    ans -= apple;
    printf("%d\n", ans);
}


Measured memory_bytes: 256
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。
string upper(string str);       // 英字を大文字に変換する。
string lower(string str);       // 英字を小文字に変換する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>
#define GCD(a,b)      __gcd((a),(b))
#define LCM(a,b)      (a)/GCD((a),(b))*(b)

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  string s;
  cin >> s;

  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3])
    cout << "Bad";
  else cout << "Good";
  
  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

string upper(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(97 <= *itr && *itr <= 122)
    {
      *itr = *itr - 32;
    }
  }
  return str;
}

string lower(string str)
{
  for(auto itr = str.begin();itr != str.end() ; itr++)
  {
    if(65 <= *itr && *itr <= 90)
    {
      *itr = *itr + 32;
    }
  }
  return str;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<cmath>

const int N=2005,M=N*N;

std::bitset<M> f;

int A[N];
int n,m;

int main()
{
	scanf("%d",&n);

	f.reset();

	f[0]=1,m=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",A+i);
		m+=A[i];
		f=f|(f<<A[i]);
	}

	m=(int)ceil(m/2.0);


	while(!f[m])m++;
	printf("%d\n",m);
	return 0;
}


Measured memory_bytes: 2176
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<numeric>
#include<map>

#define REP(i, a) for(int i=0;i<(int)a;++i)
#define ALL(a) (a).begin(),(a).end()
#define V vector
#define INF 1145141919

template<class T, size_t N>
size_t countof(const T (&array)[N]) { return N; }

typedef long long ll;
typedef long double ld;

using namespace std;

void solver() {
    int n, m;
    cin >> n >> m;
    V<V<int>> left(n,V<int>(m));
    V<int> right(m);
    V<int> ans(n);
    REP(i,n){
        REP(j,m){
            int t;
            cin>>t;
            left[i][j]=t;
        }
    }
    REP(i,m){
        int t;
        cin>>t;
        right[i]=t;
    }
    REP(i,n){
        int sum=0;
        REP(j,m){
            sum+=left[i][j]*right[j];
        }
        ans[i]=sum;
    }
    REP(i,n){
        cout<<ans[i]<<endl;
    }

}

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


Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
int a[20];
int x[20][20];
int y[20][20];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    for (int j = 0; j < a[i]; j++) {
      cin >> x[i][j] >> y[i][j];
    }
  }
  int mx = 0;
  for (int i = 0; i < (1 << n); i++) {
    int cur[20];
    int h[20];
    int cnt = 0;
    memset(cur, -1, sizeof(cur));
    for (int j = 0; j < n; j++)
      h[j] = ((i & (1 << j)) > 0), cnt += (h[j] > 0);
    // for (int j = 0; j < n; j++)
    //   cout << h[j] << ' ';
    // cout << endl;
    for (int j = 0; j < n; j++) {
      if (h[j])
        for (int k = 0; k < a[j]; k++) {
          if (y[j][k] != h[x[j][k] - 1])
            goto e;
        }
    }
    mx = max(cnt, mx);
  e:
    void(0);
  }
  cout << mx << endl;
}

Measured memory_bytes: 256
import math
a = []
cnt = 0
n = int(input())
for _ in range(n) : 
	a.append(int(input()))

def isPrime(x) :
	if x == 2 : 
		return True
	if x < 2 or x % 2 == 0 : 
		return False
	i = 3
	while i <= math.sqrt(x) :
		if x % i == 0 :
			return False
		i += 2
	return True
	
for i in a : 
	if isPrime(i) :
		cnt += 1
	
print(cnt)


Measured memory_bytes: 6004
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
acc = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    for j in range(1, W + 1):
        acc[i][j] = acc[i][j - 1] + int(S[i][j - 1])


ans = INF
for bit in range(1 << (H - 1)):
    base = 0
    vertical = []
    for i in range(H - 1):
        if bit & 1 << i > 0:
            vertical.append((base, i))
            base = i + 1
    vertical.append((base, H - 1))

    tmp_ans = len(vertical) - 1
    prev = 0
    j = 1
    valid = False
    while j <= W:
        ok = True
        for v in vertical:
            now = 0
            for i in range(v[0], v[1] + 1):
                now += acc[i][j] - acc[i][prev]
            if now > K:
                ok = False
        if ok:
            valid = True
        else:
            if valid:
                prev = j - 1
                tmp_ans += 1
                valid = False
                continue
            else:
                break
        j += 1
    if valid:
        ans = min(tmp_ans, ans)
print(ans)

Measured memory_bytes: 9672
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int l = sc.nextInt();
		while(a != 0 || l != 0){
			String[] list = new String[21];
			list[0] = zeroPad(Integer.toString(a), l);
			for(int i = 1; i <= 20; i++){
				int max = Integer.parseInt(getMax(list[i - 1]));
				int min = Integer.parseInt(getMin(list[i - 1]));
				list[i] = zeroPad(String.valueOf(max - min), l);
//				System.out.println(max +"-"+ min +"="+ list[i]);

				boolean flg = false;
				for(int j = 0; j < i; j++){
					if(list[i].equals(list[j])){
						System.out.println(j + " " + Integer.parseInt(list[i]) + " " + (i - j));
						flg = true;
						break;
					}
				}
				if(flg){
					break;
				}
			}
			a = sc.nextInt();
			l = sc.nextInt();
		}
		
		sc.close();
	}
	static String zeroPad(String str, int length){
		String res = str;
		while(res.length() < length){
			res = "0" + res;
		}
		return res;
	}
	static String getMax(String str){
		char[] res = str.toCharArray();
		
		for(int i = 1; i < res.length; i++){
			char tmp = res[i];
			int cmpi = Character.getNumericValue(tmp);
			for(int j = i; j > 0; j--){
				int cmpj = Character.getNumericValue(res[j - 1]);
				if(cmpj > cmpi){
					res[j] = tmp;
					break;
				}
				res[j] = res[j - 1];
				res[j - 1] = tmp;
			}
		}
		
		return String.valueOf(res);
	}
	static String getMin(String str){
		char[] res = str.toCharArray();
		
		for(int i = 1; i < res.length; i++){
			char tmp = res[i];
			int cmpi = Character.getNumericValue(tmp);
			for(int j = i; j > 0; j--){
				int cmpj = Character.getNumericValue(res[j - 1]);
				if(cmpj < cmpi){
					res[j] = tmp;
					break;
				}
				res[j] = res[j - 1];
				res[j - 1] = tmp;
			}
		}
		
		return String.valueOf(res);
	}
}

Measured memory_bytes: 27448
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
const ll INF = 1e10;


int main() {
    int n,m,r; cin >> n >> m >> r;
    vector<int> dest(r); 
    for (int i = 0; i < r ; i ++) {
        int town; cin >> town;
        dest[i] = town - 1;
    }
    sort(dest.begin(),dest.end());

    vector<vector<ll>> dist(n,vector<ll>(n,INF));
    for (int i = 0; i < m; i ++) {
        int a,b; cin >> a >> b;
        ll c; cin >> c;

        a --; b --;
        dist[a][b] = c;
        dist[b][a] = c;
    }

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

    ll ans = INF;
    do {
        ll tmp = 0;
        for (int i = 0; i < r - 1; i ++) {
            tmp += dist[dest[i]][dest[i + 1]];
        }
        ans = min (ans, tmp);
    }while(next_permutation(dest.begin(),dest.end()));
    cout << ans << endl;
}

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

int main(){
    ll N, M;
    cin >> N >> M;
    ll A[N];
    for(ll i = 0; i < N; i++) cin >> A[i];
    map<ll, ll> m;
    m[0]++;
    ll sum = 0;
    for(ll i = 0; i < N; i++){
        sum += A[i];
        m[sum % M]++;
    }
    ll ans = 0;
    for(auto e : m) ans += e.second * (e.second - 1) / 2;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#include <variant>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin>>n;
  vecint a(n);
  for(auto&&e:a)cin>>e;
  sort(ALL(a),greater<int>());
  ll ans = 0;
  REP(i,n-1) {
    ans += a[(i+1)/2];
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3992
#include <iostream>
#include <algorithm>

using namespace std;

#define PRIMEMAX 1000000
bool isPrime[PRIMEMAX];
//ツエツδ可トツスツテツネツスツづ個づ督づゥツつ「ツづーツ用ツつ「ツづ渉可甘コツ可サ
void initErt() {
	//ツ全ツ閉杯rueツづ鳴づ淞づゥ
	fill_n(isPrime, PRIMEMAX, true);
	isPrime[0] = false;
	isPrime[1] = false;
	//ツ閉スツ陛サツ債ェツづ慊づ個ゥツづェツづ篠づヲツつ「
	for (int i = 2; i * i < PRIMEMAX; i++) {
		if (!isPrime[i]) continue;
		//iツづ債素ツ青板ィツつサツづ個倍ツ青板づ債全ツづ素ツ青板づづ債づ按つ「
		for (int j = (i << 1); j < PRIMEMAX; j += i) {
			if (!isPrime[j]) continue;
			isPrime[j] = false;
		}
	}
}

int main() {
	initErt();
	
	int a, d, n;
	while (1) {
		cin >> a >> d >> n;
		if (a == 0 && d == 0 && n == 0) break;
		
		int count = 0;
		for (;;a += d) {
			if (isPrime[a]) {
				count++;
				if (count == n) {
					cout << a << endl;
					break;
				}
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int INF = 0x3f3f3f3f;
//static const auto _____ = []()
//{
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr);
//	return nullptr;
//}();
typedef long long ll;

int main(int argc, char *argv[]) {
    int N, V;
    cin >> N >> V;
    vector<ll> v(N + 1, 0);
    vector<ll> w(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i];
    }
    vector<ll> dp(V + 1, 0);
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= v[i]; j--) {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V];
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <set> 
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector <int> v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    sort(v.begin(),v.end());
    ll ans=0;
    for(int i=0;i<k;i++)ans+=v[i];
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3660