akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cassert>
#include<vector>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<cmath>

using namespace std;
#define REP(i,m,n) for(int i=m;i<n;++i)
#define REPll(i,m,n) for(ll i=m;i<n;++i)
#define INF 10000000000000000
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define all(v) v.begin(),v.end()

vector<vector<char>>v(100, vector<char>(100, 0));
vector<vector<int>>dist(100,vector<int>(100,10000));
vector<vector<bool>>check(100, vector<bool>(100, false));
queue<pair<int, int>>q;

int main() {
	int h, w;
	cin >> h >> w;
	int ans = 0;
	REP(i, 0, h + 2) {
		REP(j, 0, w + 2) {
			if (i == 0 || i == h + 1 || j == 0 || j == w + 1) {
				v[i][j] = '#';
			}
			else {
				char tmp;
				cin >> tmp;
				v[i][j] = tmp;
				if (tmp == '.') {
					ans++;
				}
			}
		}
	}
	q.push(mp(1, 1));
	dist[1][1] = 0;
	check[1][1] = true;
	while (q.empty() == false) {
		int x = q.front().first, y = q.front().second; q.pop();
		if (v[x + 1][y] == '.'&&check[x + 1][y] == false) {
			q.push(mp(x + 1, y));
			dist[x + 1][y] = dist[x][y] + 1;
			check[x + 1][y] = true;
		}
		if (v[x - 1][y] == '.'&&check[x - 1][y] == false) {
			q.push(mp(x - 1, y));
			dist[x - 1][y] = dist[x][y] + 1;
			check[x - 1][y] = true;
		}
		if (v[x][y + 1] == '.'&&check[x][y + 1] == false) {
			q.push(mp(x, y + 1));
			dist[x][y + 1] = dist[x][y] + 1;
			check[x][y + 1] = true;
		}
		if (v[x][y - 1] == '.'&&check[x][y - 1] == false) {
			q.push(mp(x, y - 1));
			dist[x][y - 1] = dist[x][y] + 1;
			check[x][y - 1] = true;
		}
	}
	if (dist[h][w] == 10000) {
		printf("-1\n");
	}
	else {
		ans -= dist[h][w] + 1;
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define fr(i,a,b) for(int i = a ; i <= b ; ++i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define pb push_back
#define fst first
#define snd second
using namespace __gnu_pbds;
using ordered_set =
 tree<int, null_type,less<int>,
 rb_tree_tag,tree_order_statistics_node_update>;
//find_by_order(k):returns iterator to kth element starting from 0
//order_of_key(k):returns count of elements strictly smaller than k
typedef long long ll;typedef pair<int, int> pii;
typedef vector<int> vi;typedef long double ld;
template<class T>
using min_heap = priority_queue<T,vector<T>,greater<T>>; 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
template<typename T> 
void remdup(vector<T>& v) {
	sort(all(v)); v.erase(unique(all(v)), v.end());
}
template<typename T> void re(vector<T> &v) {trav(i,v) cin >> i;}
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
#ifdef np
#include "C:\Users\navodit\Desktop\mycodes\pr.h"
#else
#define trace(...)
#endif

#define MOD 1000000007  




void solve(){
	int n , h ;
	cin >> h >> n; 
	vi a(n);
	re(a);
	int s = accumulate(all(a),0);
	if(s>=h) cout << "Yes\n";
	else cout << "No\n";
}
//void solve(){
	//int a , h ;
	//cin >> h >> a ;
	//int cnt =0 ;
	//while(h>=0){
		//h-=a;
		//cnt++;
	//}
	//if(a==1)cout << cnt-1 << endl;
	//else cout << cnt << endl;
//}

signed main() {
	unsyncIO();
	int tt =1 ;
	// cin >> tt;
	rep(i,0,tt) solve();













#ifdef np
	cout <<endl<<endl<< "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}


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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a+b == c+d) {
        cout << "Balanced" << endl;
    } else if (a+b < c+d) {
        cout << "Right" << endl;
    } else if (a+b > c+d) {
        cout << "Left" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
typedef long long ll;
using namespace std;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps = 0.0000001;
const int N=2200;
const int M=1e5+10;
const int mod=1e9+7;
void io(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
ll aa[2010];
int main()
{
   int n;
   ll k;
   cin>>n>>k;
   for(int i=1;i<=n;i++)
       cin>>aa[i];
   ll sum=0;
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           if(aa[i]>aa[j]) sum++;
   ll summ=0;
   for(int i=1;i+1<=n;i++)
       for(int j=i+1;j<=n;j++)
       if(aa[j]<aa[i]) summ++;
    ll ans=summ*k%mod;
    ans=ans+(k*(k-1)/2%mod*sum%mod)%mod;
    cout<<ans%mod<<endl;
}

Measured memory_bytes: 256
console.log((args=>{
  const [L,R,d] = args.trim().split(' ').map(v=>v|0);
  let count = 0;
  for ( let i = L; i <= R; i++ ) {
    if ( i % d === 0 ) count++;
  }
  return `${count}`;
})(require('fs').readFileSync('/dev/stdin', 'utf8')));


Measured memory_bytes: 29676
/* {{{ Shinobu kawaii */
/*
  ______   __        _                  __                 
.' ____ \ [  |      (_)                [  |                
| (___ \_| | |--.   __   _ .--.   .--.  | |.--.   __   _   
 _.____`.  | .-. | [  | [ `.-. |/ .'`\ \| '/'`\ \[  | | |  
| \____) | | | | |  | |  | | | || \__. ||  \__/ | | \_/ |, 
 \______.'[___]|__][___][___||__]'.__.'[__;.__.'  '.__.'_/ 

*/
/* }}} */

#include <bits/stdc++.h>
using namespace std;

// #define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; std::cin >> x; return x;}
template <typename T> void print(T x) {std::cout << x << '\n';}
template <typename T>
void print(std::vector<T>& v, std::string s = " ") {
  REP(i, v.size()) {
    if (i != 0) std::cout << s;
    std::cout << v[i];
  }
  std::cout << '\n';
}

/* }}} */

void warshallfloyd(vvi& d, int n)
{
  REP(k, n) REP(i, n) REP(j, n) {
    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  }
}

signed main()
{
  int n, k;
  while (n = in(), k = in(), n || k) {
    vvi d(n, vi(n, INF));
    REP(i, k) {
      bool a = in();
      if (a) {
        int b = in() - 1, c = in() - 1, cost = in();
        if (d[b][c] <= cost) continue;
        d[b][c] = min(d[b][c], cost);
        d[c][b] = min(d[c][b], cost);
        warshallfloyd(d, n);
      } else {
        int b = in() - 1, c = in() - 1;
        print(d[b][c] == INF ? -1 : d[b][c]);
      }
    }
  }

  return 0;
}

Measured memory_bytes: 3168
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    H, W = read_values()
    F = [input() for _ in range(H)]

    T = [False] * W
    for f in F:
        if f.count("#") == 0:
            continue
        
        for w, s in enumerate(f):
            if s == "#":
                T[w] = True

    for f in F:
        if f.count("#") == 0:
            continue
        print("".join([s for i, s in enumerate(f) if T[i]]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		char[] c = sc.next().toCharArray();
		for(int i = 0; i < 5; i++)
			out.print(c[i]);
		out.print(' ');
		for(int i = 6; i < 13; i++)
			out.print(c[i]);
		out.print(' ');
		for(int i = 14; i < 19; i++)
			out.print(c[i]);
		

		out.close();
	}
	 

static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}
}


Measured memory_bytes: 23252
n = int(input())
k = int(input())

x = list(map(int, input().split(" ")))

ans = 0
for i in range(n):
    if(x[i] > abs(k - x[i])):
        ans += abs(k - x[i]) * 2
    else:
        ans += x[i] * 2

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define ar array
#define nl '\n'
#define AC ios_base::sync_with_stdio(0); cin.tie(NULL);
using namespace std;
const int M = 1e9+7;
const int N = 2*1e5;

int n, k;
vector<int> arr;

int main(){
    AC
    cin>>n>>k;
    arr.resize(n);
    for(int i=0; i<n; i++)
        cin>>arr[i];
    sort(arr.begin(), arr.end());
    int ans = 0;
    for(int i=0; i<k; i++)
        ans+=arr[i];
    cout<<ans<<nl;

}

Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
long long n, m, k, x[100001], a[100001], b[100001], to[100001], cir[100001], ans[100001];
bool vis[100001];
int main(int argc, char const *argv[])
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &x[i]);
        b[i] = x[i] - x[i - 1];
        to[i] = i;
    }
    scanf("%lld%lld", &m, &k);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld", &a[i]);
        swap(to[a[i]], to[a[i] + 1]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            int cnt = 0;
            for (int j = i; !vis[j]; j = to[j])
            {
                cir[++cnt] = j;
                vis[j] = 1;
            }
            for (int j = 1; j <= cnt; j++)
            {
                ans[cir[j]] = b[cir[(j + k - 1) % cnt + 1]];
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        ans[i] += ans[i - 1];
        printf("%lld.0\n", ans[i]);
    }
    return 0;
}

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

int main() {
	string s; cin >> s;
  	assert(s.length() == 6);
  	if(s[0] != s[1] and s[2] == s[3] and s[4] == s[5]) cout << "Yes\n";
  	else cout << "No\n";
  	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define el '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repi(i, a, b) for (int i = a; i >= b; i--)
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define mp make_pair
#ifdef LOCAL
#define debug(fmt, ...) printf(fmt, ##__VA_ARGS__)
#define check(...) assert(__VA_ARGS__)
#else
#define debug(fmt, ...)
#define check(...)
#endif

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

    unordered_set<string> s;
    int n;
    cin >> n;
    rep(i,0,n) {
        string ss;
        cin >> ss;
        s.insert(ss);
    }
    cout << s.size();
}


Measured memory_bytes: 13900
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <iomanip>
#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1844674407370955161
typedef long long int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007



int main()
{
    int N;
    cin>>N;
    ll H[N];
    REP(i,0,N){
        cin >> H[i];
    }
    if(N==1){
        cout << "Yes" << endl;
    }else{

        for (int i = N - 1; i >= 1;i--){
            if(H[i]<H[i-1]){
                H[i-1]--;
            }
            if(H[i]<H[i-1]){
                cout << "No" << endl;
                    return 0;
            }
        }
           

        cout << "Yes" << endl;
    }

    return 0;
}

Measured memory_bytes: 1024
import fractions
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
 
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
 
c = 0
for i in range(n):
    b = ans // a[i]
    c += b
 
print(c % mod)

Measured memory_bytes: 6200
#include <iostream>
#include<cstdio>
#include<cctype>
#include<string.h>
#include<stdio.h>
using namespace std;

int main()
{
    char a[1300];
    cin.getline(a,sizeof(a));
    char c[strlen(a)];
    strcpy(c,a);
    

        
    
    for(int i=0;i<strlen(c);i++){
        
          if(islower(c[i])){
              putchar(toupper(c[i]));
          }else if(isupper(c[i])){
              putchar(tolower(c[i]));
          }else{
              cout<<c[i];
          }
          
       
            
        
    }

    cout<<endl;
}


Measured memory_bytes: 3148
#include <bits/stdc++.h>
using namespace std;
#define cs const
#define int long long
#define low(i) (i & (-i))
#define mid ((l + r) >> 1)
#define ls (now << 1)
#define rs (now << 1 | 1)
#define par pair<int, int>
#define mp make_pair
#define fr first
#define se second
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define drep(i, x, y) for (int i = x; i >= y; --i)
#define fore(i, x) for (int i = fir[x]; i; i = nex[i])
cs int base = 233;
cs int ff = 2e6 + 1;
cs int mod = 998244353;
cs int inf = 1e9 + 1;
int x[ff], y[ff], z[ff], n, m, a, b, c, ans;
bool cmp(const int &a, const int &b) { return a > b; }
int read() 
{
    int x;
    scanf("%lld", &x);
    return x;
}
signed main() 
{
    n = read(), m = read(), a = read(), b = read(), c = read();
    for (int i = 1; i <= a; i++) x[i] = read();
    for (int i = 1; i <= b; i++) y[i] = read();
    for (int i = 1; i <= c; i++) z[i] = read();
    sort(x + 1, x + a + 1, cmp);
    sort(y + 1, y + b + 1, cmp);
    sort(z + 1, z + c + 1, cmp);
    a = n, b = m;
    for (int i = 1; i <= n; i++) ans += x[i];
    for (int i = 1; i <= m; i++) ans += y[i];
    int cnt1 = a, cnt2 = b, cnt3 = 1;
    x[0] = inf, y[0] = inf;
    while (cnt3 <= c) {
        if (x[cnt1] < y[cnt2] && cnt3 <= c && z[cnt3] > x[cnt1]) 
        {
            ans += (z[cnt3] - x[cnt1]), cnt1--, cnt3++;
            continue;
        }
        if (x[cnt1] >= y[cnt2] && cnt3 <= c && z[cnt3] > y[cnt2]) 
        {
            ans += (z[cnt3] - y[cnt2]), cnt2--, cnt3++;
            continue;
        }
        break;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 7168
(n, k) = map(int, input().split(" "))

x = list(map(int, input().split(" ")))

zero = None

min_length = 1000000000

for i in range(0, n - k + 1):
    lx = x[i]
    rx = x[i + k - 1]

    if((lx <= 0 and rx <= 0) or (lx >= 0 and rx >= 0)):
        abslx = abs(lx)
        absrx = abs(rx)
        min_length = min(min_length, max(abslx, absrx))
    else:
        abslx = abs(lx)
        absrx = abs(rx)
        xlength = min(abslx, absrx) * 2 + max(abslx, absrx)
        min_length = min(min_length, xlength)
        
print(min_length)

Measured memory_bytes: 14252
import java.io.ByteArrayInputStream;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static String INPUT = "";

    public static void main(String[] args) {
        InputStream is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());

        Scanner scanner = new Scanner(is);

        final int n = scanner.nextInt();
        final int total = scanner.nextInt();
        List<Pair> result = solve(n, total);
        if (result == null) {
            System.out.println("-1 -1 -1");
        } else {
            System.out.println(String.format("%d %d %d", result.get(0).count, result.get(1).count, result.get(2).count));
        }
    }

    static List<Pair> solve(int n, int total) {
        List<Integer> bills = new ArrayList<>();
        bills.add(10000);
        bills.add(5000);
        bills.add(1000);

        return recursion(n, total, total, n, bills, 0, new ArrayList<>());
    }

    static List<Pair> recursion(int n, int total, int remainingVal, int remainingCount, List<Integer> bills, int billPosition, List<Pair> acc) {
        if (billPosition == bills.size()) {
            // base case
            int billCount = acc.stream().mapToInt(x -> x.count).sum();
            int totalAccVal = acc.stream().mapToInt(x -> x.value * x.count).sum();
            if (totalAccVal == total && n == billCount) {
                return new ArrayList<>(acc);
            } else {
                return null;
            }
        }

        int currentBill = bills.get(billPosition);
        int billLimitForThis = remainingVal / currentBill;

        if (billLimitForThis > remainingCount) { // this can't be the candidate
            return null;
        }

        if (billPosition == bills.size() - 1) {
            // now, this is the last candidate. Check if currentBill * remainingCount == remainingVal
            acc.add(new Pair(currentBill, remainingCount));
            List<Pair> ret = recursion(n, total, remainingVal - currentBill * remainingCount, 0, bills, billPosition + 1, acc);
            acc.remove(acc.size() - 1);
            return ret;
        }

        for (int i = 0; i <= remainingCount && i <= billLimitForThis; i++) {
            acc.add(new Pair(currentBill, i));
            List<Pair> ret = recursion(n, total, remainingVal - currentBill * i, remainingCount - i, bills, billPosition + 1, acc);
            if (ret != null) {
                return ret;
            }
            acc.remove(acc.size() - 1);
        }
        return null;
    }

    static class Pair {
        int value;
        int count;

        Pair(int value, int count) {
            this.value = value;
            this.count = count;
        }
    }

}


Measured memory_bytes: 46152
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){
    int n;
    scanf("%d",&n);
    if((n%10==0)||(n%10==1)||(n%10==6)||(n%10==8)){
        printf("pon\n");
    }else if(n%10==3){
        printf("bon\n");
    }else{
        printf("hon\n");
    }
    return 0;
}

Measured memory_bytes: 1620
#![allow(unused_imports)]

use proconio::{input, fastout};
use proconio::marker::*;

#[fastout]
fn main() {
    input! {
    a: usize,
    b: usize
    }
    let ans = if a * b % 2 != 0 {"Yes"} else {"No"};
    println!("{}", ans);
}


Measured memory_bytes: 2196
#include <iostream>
#include <vector>



int main(){
   const int n = 10;
   int N;
   std::cin >> N;
   int F[N][n], P[N][n+1];
   for(int i=0; i<N; ++i){
      for(int j=0; j<n; ++j){
	 std::cin >> F[i][j];
      }
   }
   
   for(int i=0; i<N; ++i){
      for(int j=0; j<n+1; ++j){
	 std::cin >> P[i][j];
      }
   }

   int ans = -1000000000;
   for(int i=1; i<1024; ++i){
      std::vector<int> c(N,0);
      for(int j=0; j<n; ++j){
	 if(i & (1<<j)){
	    for(int k=0; k<N; ++k){
	       c[k] += F[k][j];
	    }
	 }
      }
      int p = 0;
      for(int j=0; j<N; ++j){
	 p += P[j][c[j]];
      }
      ans = std::max(p, ans);
   }
   std::cout << ans << std::endl;
   return 0;
}


Measured memory_bytes: 256
/* ****AWARE**** */
#include<bits/stdc++.h>
#include <limits.h> 
#define cut ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll          long long
#define pb          push_back
#define endl        '\n'
#define pii         pair< ll, ll>
#define vi          vector< ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(  ll i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp13       make_pair
using namespace std; 
#define MAX  3000000000
#define MODULO 2
using namespace std;   
#define hell 1000000007 
#define hell1 30000000000000000
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
#define mysizeof(i) (char*)(&i+1)-(char *)(&i);
ll T;

void solve()
{ long long int a,b,n,w,m,k,i,j,mx,ans=2,cnt,sum=0;
 cin>>n>>w;
 vector<pair<ll,ll>>v;
 for(i=0;i<n;i++)
 {
  cin>>a>>b;
  v.push_back(make_pair(a,b));
  sum+=b;
 }
  vector<ll>dp(sum+1,1e12);
  dp[0]=0;
  for(i=0;i<n;i++)
  {
    for(j=sum;j>=v[i].second;j--)
    {
      dp[j]=min(dp[j],dp[j-v[i].second]+v[i].first);
    }
  }
  for(i=sum;i>=0;i--)
  {
    if(dp[i]<=w)
    {
      cout<<i<<"\n";
      return ;
    }
  }


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

Measured memory_bytes: 4000
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Char
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM
import qualified Data.ByteString.Char8 as BS

readIntTriplet :: BS.ByteString -> (Int, Int, Int)
readIntTriplet s = let Just (a, s') = BS.readInt s
                       Just (b, s'') = BS.readInt $ BS.dropWhile isSpace s'
                       Just (c, _) = BS.readInt $ BS.dropWhile isSpace s''
                   in (a, b, c)

main = do
  n <- readLn
  let loop 0 !a !b !c = return (a,b,c)
      loop i !a !b !c = do
        (a',b',c') <- readIntTriplet <$> BS.getLine
        -- a,b,c <= 10^4
        loop (i - 1) (max b c + a') (max a c + b') (max a b + c')
  (a,b,c) <- loop n 0 0 0
  print (max a (max b c))

main2 = do
  n <- readLn
  happiness <- V.replicateM n (readIntTriplet <$> BS.getLine)
  let (!a,!b,!c) = V.foldl1' (\(!a,!b,!c) (!a',!b',!c') -> (max b c + a', max a c + b', max a b + c')) happiness
  print (max a (max b c))


Measured memory_bytes: 1020
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		long total=0;
		int N = in.nextInt();
		in.nextLine();
		
		
		for(int i=0;i<N;i++){
			String s= in.nextLine();
			String[] arraySeat = s.split(" ");
			int l = Integer.parseInt(arraySeat[0]);
			int r = Integer.parseInt(arraySeat[1]);
			total+=(r-l+1);
		}
		System.out.print(total);
		
	}
}


Measured memory_bytes: 26324
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define n_l '\n'

#ifndef ONLINE_JUDGE
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
#endif

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef double db;
typedef vector<vi> vvi;
const ll mod=1000000007;
const ll N=200005; //check this
int dx[] = {-1, 0, 1, 0, 1, 1, -1, -1};
int dy[] = {0, -1, 0, 1, 1, -1, 1, -1};

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll powb(ll a,ll b) {ll res=1;a ; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a;a=a*a;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

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

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int x,y;cin>>x>>y;
    if((4*x-y)%2!=0)cout<<"No";
    else{
        int a=(4*x-y)/2;
        if(a>=0 && x-a>=0)cout<<"Yes";
        else cout<<"No";
    }
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);i++)
#define rep(i,n) repl(i,0,n-1)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

int main(){
  cin.sync_with_stdio(false);
  int n,k;
  cin >> n >> k;
  int x;
  int sum=0;
  rep(i,n){
    cin >> x;
    sum += mmin(abs(x-k)*2,x*2);
  }
  cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define pii pair<long long,long long>
#define endl '\n'
#define N 300001
void solve()
{
    int n; cin>>n;
    string s; cin>>s;
    if(s.size()<=n)
    cout<<s;
    else
    cout<<s.substr(0,n)<<"...";
    
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test; test=1; //cin>>test;
    int x=1;
    while(test--)
    {
        //cout<<"Case #"<<x++<<": ";
        solve();
    }
    return 0;
}

Measured memory_bytes: 3648
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	n := nextInt()
	sList := nextInts(n)

	sum := 0

	for _, s := range sList {
		sum += s
	}
	if sum%10 != 0 {
		fmt.Println(sum)
		return
	}
	sort.Ints(sList)
	for _, s := range sList {
		result := sum - s
		if result%10 != 0 {
			fmt.Println(result)
			return
		}
	}
	fmt.Println(0)
}

// 引数処理
func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}

func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}

func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;

int main(){
  cin >> n;
  pair<int, int> p[n];
  ll x, l;
  for ( int i = 0; i < n; i++){
    cin >> x >> l;
    p[i] = make_pair(x+l, x-l);
  }
  sort(p, p+n);

  ll cur = -1000000001, cnt = 0;
  for ( int i = 0; i < n; i++){
    if ( cur > p[i].second){
      cnt++;
    } else {
      cur = p[i].first;
    }
  }

  cout << n-cnt << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i, n) for(ll i = 0; i < (n); i++)
#define fori(i, b, e) for(ll i = (b); i < (e); i++)
#define forr(i, b, e) for(ll i = (b); i >= (e); i--)
#define allele(v) v.begin(), v.end()

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> h(n);
  forn(i, n) cin >> h[i];
  vector<int> dp(n);
  dp[0] = 0, dp[1] = abs(h[1] - h[0]);
  fori(i, 2, n) dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
  cout << dp[n - 1];
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// Split
namespace util {

std::vector< std::string > split(std::string s, char delimiter)
{
  std::vector< std::string > vs;
  std::string sub;
  for (auto c : s) {
    if (c == delimiter) vs.push_back(sub), sub.clear();
    else sub += c;
  }
  vs.push_back(sub);
  return vs;
}

} // namespace util

// Minimum, Maximum
template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }
template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

// Output
template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 0) os << std::endl; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp){os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll N;
  std::cin >> N;

  ll ans = 1;
  ll max_cnt = 0LL;
  for (ll i = 2; i <= N; i+=2) {
    ll x = i;
    ll cnt = 0LL;
    while (x % 2 == 0) {
      x /= 2;
      cnt++;
    }
    if (cnt > max_cnt) {
      ans = i;
      max_cnt = cnt;
    }
  }

  print(ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll h, w;
    cin >> h >> w;
    ll g[4];
    for(int i=0;i<4;i++){
        cin >> g[i];
        g[i]--;
    }
    string s[h];    
    for(int i=0;i<h;i++){
        cin >> s[i];
    }
    vector<vector<ll> > dis(h, vector<ll> (w, INF));
    deque<pair<ll, pair<ll, ll> > > q;
    pair<ll, pair<ll, ll> > niko;
    q.push_back({0LL, {g[0], g[1]}});
    ll dy[24] = {0, 0, -1, 1, -2, -2, -2, -2, -2, 2, 2, 2, 2, 2, 1, 1, 1, 1, -1, -1, -1, -1, 0, 0};
    ll dx[24] = {-1, 1, 0, 0, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, -1, 1, 2, -2, 2};
    while(!q.empty()){
        niko = q.front();
        ll y = niko.second.first;
        ll x = niko.second.second;
        ll d = niko.first;
        q.pop_front();
        if(d > dis[y][x]) continue;
        for(int k=0;k<4;k++){
            ll nowy = y + dy[k];
            ll nowx = x + dx[k];
            if(nowy < 0 || nowy >= h || nowx < 0 || nowx >= w || s[nowy][nowx] == '#') continue;
            if(dis[nowy][nowx] > d){
                dis[nowy][nowx] = d;
                q.push_front({d, {nowy, nowx}});
            } 
        }
        for(int k=4;k<24;k++){
            ll nowy = y + dy[k];
            ll nowx = x + dx[k];
            if(nowy < 0 || nowy >= h || nowx < 0 || nowx >= w || s[nowy][nowx] == '#') continue;
            if(dis[nowy][nowx] > d + 1){
                dis[nowy][nowx] = d + 1;
                q.push_back({d + 1, {nowy, nowx}});
            }
        }
    }
    ll ans = dis[g[2]][g[3]];
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12836
//============================================================================
// Name        : ProjG.cpp
// Author      : Yong Kiat
// Version     :
// Copyright   : By Algotae.
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>

using namespace std;

const int mxN = 1000, M = 1e9+7;
int r, c, dp[mxN][mxN];
string g[mxN];

bool ie(int i, int j) {
	return i >= 0 && j >= 0 && g[i][j] == '.';
}

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

    cin >> r >> c;

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

    dp[0][0] = 1;
    for (int i = 0; i < r; i++) {
    	for (int j = 0; j < c; j++) {
    		if (ie(i - 1, j)) {
    			dp[i][j] += dp[i - 1][j];
    		}
    		if (ie(i, j - 1)) {
    			dp[i][j] += dp[i][j - 1];
    		}

    		dp[i][j] %= M;
    	}
    }

    cout << dp[r - 1][c - 1];
}


Measured memory_bytes: 5248
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jiglypuff
#define ld long double
#define itn int
#define pir pair<int, int> 
#define all(x) (x).begin(), (x).end()
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x1, ld y1, ld x2, ld y2)
{
	return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
	return (a * (a + 1LL)) / 2;
}
char vow[] = { 'a', 'e', 'i', 'o', 'u' };
int dx[] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dy[] = { 0, 0, 1, -1, 1, -1, 1, -1 };


const int N = 3010;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 238;
const ld e = 74e-9;

lli bp(lli a, lli b = -2LL)
{
	lli ret = 1;
	while (b)
	{
		if (b & 1) ret *= a, ret %= mod;
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return ret;
}

string s;
int main()
{
	fastio;
	cin >> s;
	if (s[2] == s[3] && s[4] == s[5]) cout << "Yes";
	else cout << "No";
	return 0;
}


/*
  __
*(><)*
  \/ /
  ||/
--||
  ||
  /\
 /  \
/    \
4 3 2 10 4
8 1 2 3 4 5 6 7 8
8 2 2 1 5 3 8 7 3
0
*/


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#pragma region include

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
//////////////
int N,K,C;
vector<bool> Bjob;
vector<bool> OK;
vector<bool> res;//出勤日
int workDayMAX=0;
/*
Bjob,追加条件
OK 働いてもいいひ
*/
bool cal() {
	//OKをベースに
	
	int cnt = 0;//出勤日数
	for (int i = 0; i < N; ++i) {
		if (OK[i] == false) {
			//働けない日
			continue;
		}
		res[i] = true; ++cnt;//働いた日は全部チェックできる。
		//次に調べるのはi+C+1の場所
		i = i + C;
	}
	
	workDayMAX = cnt;
	if (cnt >= K) {
		return true;
	}
	return false;
}
/*
問題の前提として
oが働いても良い日
xは絶対に働かない日
*/
void solve() {
	/*
	条件は両方満たす必要がある。
	C日の休息は絶対。
	i日後は後半考えられない。
	*/
	
	string str;
	cin >> N >> K >> C >> str;
	
	OK = vector<bool>(N, true);
	for (int i = 0; i < N; ++i) {
		if (str[i] == 'x') {
			OK[i] = false;
		}
	}
	res = vector<bool>(N, false);//働いた日がtrueで帰ってくる。
	vector<bool> res2(N, false);
	if (cal() == false) {
		cout << "";
	}
	res2 = res;
	res = vector<bool>(N, false);//働いた日がtrueで帰ってくる。
	int WMD = workDayMAX;//保存

	reverse(OK.begin(), OK.end());
	if (cal() == false) {//逆貪欲
		cout << "";
	}
	workDayMAX = WMD;

	vector<bool> res3(N, false);
	for (int i = 0; i < N; ++i) {
		if (res[i]) {
			res3[N - i - 1] = true;
		}
	}
	//res2,と逆でやったre3
	if (cal() == false) {//貪欲失敗かな
		//必ず一通りは働く日程表がある。
		cout << "";
	}
	if (workDayMAX > K) {
		//K日を超えて働けるなら何処か休んでもOK
		return;
	}
	vector<bool> base = res;
	int cnt = 0;
	
	for (int i = 0; i < N; ++i) {
		if (res2[i] == true && res3[i] == true) {
			cout << i + 1 << endl;
		}
	}
	return;

	for (int i = 0; i < N; ++i) {
		if (res[i] == false) {
			continue;
		}
		
		OK[i] = false;//働けない日に設定。
		/*
		resを使ってOKを操作して
		働けたら休みにできる。
		*/
		if (cal() == false) {
			if (cnt == 0) {
				++cnt;
			}
			cout << i + 1 << endl;;
		}

		OK[i] = true;//リセット
	}
}

#pragma region main
signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()


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

const int MAX_N = 110000;
#define MIN(a,b) (((a)<(b))?(a):(b))

int memo[MAX_N]; // memo[i] が i についての答え
int rec(int n) {
    if (n == 0) return 0; // 終端条件
    if (memo[n] != -1) return memo[n]; // すでに探索済みならリターン

    int res = n; // INF の気持ち
    int tmp;
    // 1, 6, 6^2, ..., を試す (n を超えない範囲で)
    for (int pow6 = 1; pow6 <= n; pow6 *= 6) {
        tmp = rec(n - pow6) + 1;
        if (res > tmp) {
            res = tmp;
        }
    }

    // 1, 9, 9^2, ..., を試す (n を超えない範囲で)
    for (int pow9 = 1; pow9 <= n; pow9 *= 9) {
        tmp = rec(n - pow9) + 1;
        if (res > tmp) {
            res = tmp;
        }
    }

    // メモしながらリターン
    return memo[n] = res;
}

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

    // テーブルを -1 で初期化
    for (int i = 0; i < MAX_N; ++i) memo[i] = -1;
    cout << rec(N) << endl;
}


Measured memory_bytes: 5376
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

void solve(){
	int n;
	int A[100010];
	cin >> n;
	rep(i, n)scanf("%d", A+i);
	sort(A, A+n);
	ll s[100010] = {};
	s[0] = A[0];
	for(int i=1;i<n;i++)s[i] = s[i-1] + A[i];
	for(int i=n-1;i>=0;i--){
		if(s[i] * 2 < A[i+1]){
			printf("%d\n", n-i-1);
			return;
		}
	}
	printf("%d\n", n);
}

int main(){
	int Tc = 1; // scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector> 
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
#include <map>
#include <cerrno>
#include <stdio.h>
#include <stdlib.h>
#include <cfenv>
#include <stack>
#include <math.h>
#include <iomanip>
#include <limits>
#include <queue>
#define ll long long int
#define pb push_back
#define mp make_pair
#define MOD 2019

using namespace std;

int main(){

    ll L,R;
    cin >> L >> R;

    int l_s = L/MOD;
    int r_s = R/MOD;
    if(l_s<r_s){
        cout << 0 << endl;
        return 0;
    }

    ll l1 = (L+MOD)%MOD;
    ll r1 = (R+MOD)%MOD;

    if(l1>=r1){
        r1+=MOD;
    }

    vector<ll> ans;
    ll tmp;

    for(ll i=l1;i<=r1;i++){
        for(ll j=i+1;j<=r1;j++){
            tmp = i*j;
            tmp = (tmp+MOD)%MOD;
            ans.pb(tmp);
        }
    }
    
    sort(ans.begin(),ans.end());

    cout << ans[0] << endl;

    return 0;
}

//3*673;

Measured memory_bytes: 16872
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

vector<int> v[101010];
ll dp[101010][2];

void dfs(int x,int p){
    dp[x][0]=dp[x][1]=1;
    for(auto to:v[x]){
        if(to==p)continue;
        dfs(to,x);
        (dp[x][0]*=(dp[to][0]+dp[to][1]))%=mod;
        (dp[x][1]*=dp[to][0])%=mod;
    }
}

int main(){
    int n;
    cin>>n;
    rep(i,n-1){
        int x,y;
        cin>>x>>y;
        --x;--y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(0,-1);
    cout<<(dp[0][0]+dp[0][1])%mod;
    return 0;
}

Measured memory_bytes: 14208
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef long double ld;
#define A 1000000007ll
#define D 100000000000000ll
#define B 998244353ll
#define C 8000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

int main() 
{
    FAST;
    string s;
    cin>>s;
    if(s.length()%2==1)
    {
        cout<<"No";
        return 0;
    }
    for(int i=0;i<s.length();i+=2)
        if(s[i]!='h' || s[i+1]!='i')
        {
            cout<<"No";
            return 0;
        }
    cout<<"Yes";
    subt;
    return 0;
}

Measured memory_bytes: 256
import math
# Euclid
def prime(n):
    prime_list = list(range(1, n + 1))
    for n_ in range(2, int(math.sqrt(n)) + 1):
        for p in prime_list:
            if p % n_ == 0 and p != n_:
                prime_list.remove(p)
    return prime_list


N = int(input())
p_list = prime(N)
prime_num = []

for _ in range(len(p_list)):
    prime_num.append(0)

for i in range(2, N+1):
    for j in range(1, len(p_list)):
        while i % p_list[j] == 0:
            prime_num[j] += 1
            i /= p_list[j]
# print(prime_num)
ans = 1
for n in prime_num:
    ans = ans * (n + 1) % (10**9 + 7)
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

void solve(){
    int n, k;
    cin>>n>>k;
    vector<int> h(n+5), dp(n+5);
    for(int i=1;i<=n;i++)cin>>h[i];
    h[0]=0;
    dp[1]=0;
    for(int i=1;i<=n;i++){
        if(i>1)dp[i]=INT_MAX;
        for(int j=i-k;j<i;j++){
            if(j>0)dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
        }
    }
    cout<<dp[n]<<endl;
}

int main()
{
    //freopen("IN.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 3992
j=lambda:map(int,raw_input().split())
n,q=j()
u=1
c=[1]*3+[0]*(n-2)+[1]
for p in[-1]*q:a,b=d=j();u+=u in d and a+b-2*u;c[a],c[b]=c[b],c[a];c[u-1]=c[u+1]=1
print sum(c)-2

Measured memory_bytes: 4228
#include <bits/stdc++.h>
using namespace std;
struct unionfind{
    int par[200100];
    int rank[200100];

    void init(int n){
        for(int i=0;i<n;i++){
            par[i]=i;
            rank[i]=0;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x]<rank[y]) par[x] = y;
        else{
            par[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }

    bool same(int x, int y){
        if(find(x)==find(y)) return true;
        else return false;
    }
};
int main(){
   long long n, m, ans=0, i, a[200100], b[200100];
   map<long long, long long> mp;
   unionfind g;
   cin >> n >> m;
   g.init(n);
   for(i=0;i<m;i++){
       cin >> a[i] >> b[i];
       g.unite(a[i], b[i]);
   }

   for(i=0;i<n;i++){
      mp[g.find(i)]++;
   }
   for(auto x : mp){
       ans=max(ans, x.second);
   }
   cout << ans <<endl;

   return 0;
}

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

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

void solve()
{
  int n;cin>>n;
  vector<int> h(n, 0);
  vector<int> d(n, 0);
  for (int i=0; i<n; i++) {
    cin>>h[i];
  }
  int ans=0;
  for (int i=0; i<100; i++) {
    for (int j=0; j<n; j++) {
      if (h[j]<=d[j]) continue;
      while(h[j]>d[j]) {
        d[j]++;
        j++;
      }
      ans++;
    }
  }
  cout << ans << endl;
}

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


Measured memory_bytes: 256