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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> C(H, vector<char>(W, '.'));
  vector<int> A(H, 0);
  vector<int> B(W, 0);

  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> C.at(i).at(j);
      if (C.at(i).at(j) == '#') {
        A.at(i) = 1;
        B.at(j) = 1;
      }
    }
  }
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
  		if (A.at(i) == 1 and B.at(j) == 1) {
        	cout << C.at(i).at(j);
        }
    }
    if (A.at(i) == 1) cout << endl;
  }  
}


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

int main(){
    
    int N;cin>>N;
    vector<long long int> A(N),B(N);
    for(int i=0;i<N;i++){
        cin>>A[i]>>B[i];
    }
    long long int ans=0;
    for(int i=N-1;i>=0;i--){
        if((ans+A[i])%B[i]!=0) ans+=(B[i]-(ans+A[i])%B[i]);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int n;
string s[100001];

int main() {
	cin >> n;
	inc(i, n) { cin >> s[i]; }
	
	inc(i, n) { sort(ALL(s[i])); }
	sort(s, s + n);
	s[n] = "@";
	
	LL ans = 0, c = 0;
	inc(i, n) {
		if(s[i] == s[i + 1]) { c++; ans += c; } else { c = 0; }
	}
	
	cout << ans << endl;
	
	return 0;
}


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

A = list(range(1, N+1))
d = []
B = []
c = []
for i in range(K):
    tmp = int(input())
    d.append(tmp)
    a = list(map(int, input().split()))
    
    B.append(a)
    c = list(set(A) & set(a))
    for j in range(len(c)):
        A.remove(c[j])

print(len(A))




Measured memory_bytes: 9200
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
using namespace std;
int main(void){
    int h, w, a, b;
    cin>>h>>w>>a>>b;
    int ans=h*w - (a*w + b*h -a*b);
    cout<<ans<<endl;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define inf 1000000009
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	int lack = b-1;
	int fue = a-1;
	int ans = lack/fue;
	if(lack%fue!=0)ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  queue<int> que[N];
  int tmp;
  for(int i=0;i<N;++i) {
    for(int j=0;j<N-1;++j) {
      cin>>tmp;
      tmp--;
      que[i].push(tmp);
    }
  }
  int match[N];
  for(int i=0;i<N;++i) match[i] = -1;
  int ans = 0;
  bool can;
  bool owari;
  while(true) {
    owari = true;
    for(int i=0;i<N;++i) {
      if(match[i]>-1) continue;
      if(!que[i].empty()) {
        owari = false;
        match[i] = que[i].front();que[i].pop();
      }
    }
    if(owari) break;
    ans++;
    can = false;;
    for(int i=0;i<N;++i) {
      if(match[i]==-1) continue;
      if(i==match[match[i]]) {
        can = true;
        match[match[i]] = -1;
        match[i] = -1;
      }
    }
    if(!can) break;
  }
  if(can) cout<<ans<<endl;
  else cout<<-1<<endl;
}



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

using namespace std;

vector < int >prime_number;

bool isPrime(int n)
{
 for (auto p:prime_number) {
		if (n % p == 0) {
			return false;
		}
	}
	return true;
}

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

	int i = 2;
	while (i < x || !isPrime(i)) {
		if (isPrime(i)) {
			prime_number.push_back(i);
		}
		i++;
	}

	cout << i << endl;

	return 0;
}


Measured memory_bytes: 384
c = [list(map(int, input().split())) for _ in range(3)]

if c[1][0] - c[0][0] == c[1][1] - c[0][1] == c[1][2] - c[0][2] and \
   c[2][0] - c[1][0] == c[2][1] - c[1][1] == c[2][2] - c[1][2] and \
   c[0][1] - c[0][0] == c[1][1] - c[1][0] == c[2][1] - c[2][0] and \
   c[0][2] - c[0][1] == c[1][2] - c[1][1] == c[2][2] - c[2][1]:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<math.h>
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 100000000000000000

int main (){
    int n, W;
    cin >> n >> W ;
    vector<int> v (n);
    vector<int> w (n) ;
    rep(i, n){
        cin >> v[i] >> w[i] ;
    } 
    vector<vector<int>> dp (n + 1, vector<int> (W + 1) ) ;
    rep(i, n ){
        rep(j, W + 1){
            if(j < w[i]){
                dp[i + 1][j] = dp[i][j] ;
            }
            else {
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) ;
        }}
    }
    cout << dp[n][W] << endl ;
}


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

int main(){
int N, M; cin >> N >> M;
vector<int> a(N), b(N), c(M), d(M);
vector<int> ans(N);
for (int i = 0; i < N; i++) {
    cin >> a[i] >> b[i];
    ans[i] = 0;
}
for (int j = 0; j < M; j++) {
    cin >> c[j] >> d[j];
}

for (int i = 0; i < N; i++) {
    int min_dist = 1000000000;
    for (int j = 0; j < M; j++) {
        int tmp = abs(a[i] - c[j]) + abs(b[i] - d[j]);
        if (tmp < min_dist) {
            min_dist = tmp;
            ans[i] = j + 1;
        }
    }
    cout << ans[i] << endl;
}

}

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

using namespace std;

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

    int ret = s.size();
    string back = "!";
    string now = "";
    for (int i = 0; i < s.size(); i++) {
        now += s[i];
        if (now != back) {
            back = now;
            now = "";
        } else {
            ret--;
        }
    }

    cout << ret << endl;
    return 0;
}

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


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

    int res = false;

    for (int i = 0; i <= N ; i += 4) {
        if ((N - i) % 7 == 0) {
            res = true;
        }
    }

    if (res) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3628
#n = int(input())
#
l,r,d = map(int,input().split())
#a = list(map(int,input().split()))
#mod = pow(10,9) + 7
sum =0
for i in range(l,r+1):
    if i % d ==  0:
        sum += 1
print(sum)
'''
a = []
for i in range(n):
    a.append(list(map(int,input().split())))
print(a)
'''

Measured memory_bytes: 9096
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

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

	switch (D)
	{
	case 22:
		cout << "Christmas Eve Eve Eve" << endl;
		break;
	case 23:
		cout << "Christmas Eve Eve" << endl;
		break;
	case 24:
		cout << "Christmas Eve" << endl;
		break;
	case 25:
		cout << "Christmas" << endl;
		break;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifdef EZZAT
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#else
#endif
}

int main() {
	run();
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	int ans = 1 * min(a, k);
	k = max(0, k - a - b);
	cout << ans - min(c, k) << endl;
}


Measured memory_bytes: 3620
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int a=sc.nextInt();
    int b=sc.nextInt();
    if (b<a) {
      System.out.println(a-1);
    }else{
      System.out.println(a);
    }
  }
}


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

using namespace std;

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

#define INF (1<<(4*4-1))
#define MOD 1000000007

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

   string S;
   cin>>S;
   string ans = "keyence";

   for(int i=0;i<S.size();i++){
      for(int j=0;j<=S.size();j++){
         string A = S;
         A.erase(i,j);
         //cout<<S<<" "<<A<<" "<<i<<" "<<j<<endl;
         if(A==ans){
            cout<<"YES"<<endl;
            return 0;
         }
      }
   }
   cout<<"NO"<<endl;
   return 0;
}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e15;
const ll MOD = 1e9+7;
const ll LINF = 1e18;


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll a(n);
  rep(i,n) cin>>a[i];
  
  vll cnts(n);
  rrep(i,n){
    ll tmp=i+i+1;
    ll cnt=0;
    while(tmp<n){
      cnt+=cnts[tmp];
      tmp+=i+1;
    }
    if(cnt%2){
      if(a[i]==0) cnts[i]=1;
    }else{
      if(a[i]) cnts[i]=1;
    }
  }
  
  vll nums;
  rep(i,n){
    if(cnts[i]) nums.push_back(i+1);
  }
  cout<<nums.size()<<endl;
  rep(i,nums.size()){
    if(i) cout<<" ";
    cout<<nums[i];
  }
  if(nums.size()) cout<<endl;
}

Measured memory_bytes: 5108
#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
 
#define llong long long
 
using namespace std;
const int IINF = 2147483647;
const llong LLINF = 9223372036854775807;
 
class UNF {
 private:
  int s;
  vector<int> tree, rank;
  int getP(int i) {
    if (tree[i] == -1){
      return i;
    }
    else
      return tree[i] = getP(tree[i]);
  }
 
 public:
  UNF(int n) {
    s = n;
    tree.resize(s, -1);
    rank.resize(s, 1);
  }
  int size() { return s; }
  void connect(int a, int b) {
    a = getP(a);
    b = getP(b);
    if(a==b)return;
    if (rank[a] >= rank[b]) {
      tree[b] = a;
      rank[a] += rank[b];
    } else {
      tree[a] = b;
      rank[b] += rank[a];
    }
  }
  bool check(int a, int b) { return getP(a) == getP(b); }
};

int main(){
  int n, m;
  cin >> n >> m;
  UNF uf(n+m+10);
  int k;
  for(int i=0; i<n; i++){
    cin >> k;
    int l;
    for(int j=0; j<k; j++){
      cin >> l;
      uf.connect(i, l+n-1);
    }
  }
  for(int i=1; i<n; i++){
    if(!uf.check(0, i)){
      cout << "NO";
      return 0;
    }
  }
  cout << "YES";
  return 0;
}

Measured memory_bytes: 1792
from collections import defaultdict, deque
import sys
import heapq
import bisect
import itertools
import queue
import copy
import time
import math
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())

def inpl(): return list(map(int, sys.stdin.readline().split()))

def inpl_str(): return list(sys.stdin.readline().split())

r = inp()
print(2 * math.pi * r)

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

using namespace std;
using ll = long long;

#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define REP(i,n) FOR(i, 0, n)
#define FORD(i,a,n) for(int i=(a); i>=(n); i--)
#define REPD(i,n) FOR(i, n, 0)

#define ALL(o) (o).begin(), (o).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T, vector<T>, greater<T> >;

const ll MOD = 1000000007;

int main() {
	int r;
	cin >> r;
	cout << r*r;

}



Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cmath>
#include <iomanip>
#include <iostream>

using namespace std;

int main() {
  double r;
  cin >> r;
  cout << fixed;
  cout << setprecision(6) << r * r * M_PI << " " << setprecision(6)
       << 2 * M_PI * r << endl;
}

Measured memory_bytes: 3244
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef long long ll;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<long long>> vvll;
typedef long double ld;
typedef std::vector<long double> vld;
typedef std::vector<std::vector<long double>> vvld;
using namespace std;
void yesno(bool state);

void Main(){
    string S,T;
    cin >> S >> T;
    ll ans = 1001;
    for (ll i = 0; i < S.size() - T.size() + 1; i++)
    {
        ll memo = 0;
        for (ll j = 0; j < T.size(); j++){
            if(T[j] != S[i+j])
                memo++;
            // cout << S[i + j];
        }
        if(memo < ans)
            ans = memo;
        // cout << endl;
    }
    cout << ans << endl;
}

int main(int argc, char const *argv[])
{
    Main();
    return 0;
}

void yesno(bool state){
    if(state)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3640
use std::cmp::max;
use std::cmp::min;

fn main() {
    input! {
        h: i32,
        w: i32,
        n: usize,
        start: (i32, i32),
        s: chars,
        t: chars,
    }

    let mut h_max = h;
    let mut h_min = 1;
    if s[n - 1] == 'U' {
        h_min += 1
    }
    if s[n - 1] == 'D' {
        h_max -= 1
    }
    for i in (0..n - 1).rev() {
        if t[i] == 'U' {
            h_max = min(h, h_max + 1)
        }
        if t[i] == 'D' {
            h_min = max(1, h_min - 1);
        }
        if s[i] == 'U' {
            h_min += 1;
        }
        if s[i] == 'D' {
            h_max -= 1;
        }
        if h_min > h_max {
            println!("NO");
            return;
        }
    }
    if h_min > start.0 || h_max < start.0 {
        println!("NO");
        return;
    }

    let mut w_max = w;
    let mut w_min = 1;
    if s[n - 1] == 'R' {
        w_max -= 1
    }
    if s[n - 1] == 'L' {
        w_min += 1
    }
    for i in (0..n - 1).rev() {
        if t[i] == 'R' {
            w_min = max(1, w_min - 1);
        }
        if t[i] == 'L' {
            w_max = min(w, w_max + 1);
        }
        if s[i] == 'R' {
            w_max -= 1;
        }
        if s[i] == 'L' {
            w_min += 1;
        }
        if w_min > w_max {
            println!("NO");
            return;
        }
    }
    if w_min > start.1 || w_max < start.1 {
        println!("NO");
        return;
    }
    println!("YES");
}

#[macro_export(local_inner_maccros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export(lcal_inner_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

#[macro_export(lcal_inner_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

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


Measured memory_bytes: 4284
#include <bits/stdc++.h>
using namespace std;
typedef float fl;
typedef long long ll;
int n, a[100001];

int partition(int a[], int p, int r){
    int x = a[r];
    int i = p - 1; // xより小さい数の先頭を指す
    for (int j = p; j < r; j++){
        if(a[j] <= x){
            int tmp = a[j];
            a[j] = a[++i];
            a[i] = tmp;
        }
    }
    int tmp = a[r];
    a[r] = a[++i];
    a[i] = tmp;
    return i;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    int id = partition(a,0,n-1);
    for(int i = 0; i < n; i++){
        if(i) cout << " ";
        if(i == id){
            cout << "[" << a[i] << "]";
            }else{
                cout << a[i];
            }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3388
import javax.swing.*;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int maxWeight = sc.nextInt();
        int[] weights = new int[count];
        long[] values = new long[count];
        for (int i = 0; i < count; i++) {
            weights[i] = sc.nextInt();
            values[i] = sc.nextLong();
        }
        long[][] res = new long[count][maxWeight + 1];
        for (int i = 0; i < count; i++) {
            for(int j= 0; j <= maxWeight; j++) {
                res[i][j] = -1;
            }
        }
        for(int j= 0; j <= maxWeight; j++) {
            if (weights[0] <= j) {
                res[0][j] = values[0];
            } else {
                res[0][j] = 0;
            }
        }

        System.out.println(calculate(res, weights, values, count - 1, maxWeight));
    }


    public static long calculate(long[][] res, int[] weights, long[] values, int index, int weight) {
        if (index == 0) {
            return res[index][weight];
        }
        if (res[index][weight] != -1 ) {
            return res[index][weight];
        }
        int curWeight = weights[index];

        long without =  calculate(res, weights, values, index - 1, weight );
        long with = 0;
        if (weight - curWeight >= 0 ) {
            with = calculate(res, weights, values, index - 1, weight - curWeight) + values[index];
        }
        res[index][weight] = Math.max(without, with);
        return res[index][weight];
    }
}

Measured memory_bytes: 127828
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		
		if(N <= K)
		{
			System.out.println( N * X);
		}else
		{
			int mo = K * X;
			int mi = (N - K) * Y;
			System.out.println(mo + mi);
		}
	}

}

Measured memory_bytes: 23764
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n = val()
l = []

for i in range(n):
    l.append(li())


ans = [-float('inf') for i in range(2 ** n)]

ans[0] = 0

for i in range(1, 2 ** n):


    curr = 0
    for j in range(n):
        for k in range(n):
            if (i >> j) & 1 == (i >> k) & 1 == 1:curr += l[j][k]
    
    curr //= 2

    ind = i & (i - 1)

    while ind:
        curr = max(curr, ans[ind] + ans[ind ^ i])
        ind = (ind - 1) & i
    
    ans[i] = curr

print(max(ans))


Measured memory_bytes: 80708
//
// Created by yamunaku on 2020/03/28.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    //CFS;
    ll x, y, a, b, c;
    cin >> x >> y >> a >> b >> c;
    vl p(a), q(b), r(c);
    vl pr(a + 1), qr(b + 1);
    rep(i, a) cin >> p[i];
    sort(all(p), greater<ll>());
    rep(i, a){
        pr[i + 1] = pr[i] + p[i];
    }
    priority_queue<ll> qq, rq;
    rep(i, b) cin >> q[i], qq.push(q[i]);
    rep(i, c) cin >> r[i], rq.push(r[i]);
    ll ans = 0;
    int idx = 0;
    ll tmp = 0;
    int count = 0;
    rep(i, y){
        if(rq.empty()){
            tmp += qq.top();
            qq.pop();
        }else if(qq.top() > rq.top()){
            tmp += qq.top();
            qq.pop();
        }else{
            tmp += rq.top();
            rq.pop();
            count++;
        }
    }
    perl(i, max(x - c, 0ll), x + 1){
        ans = max(ans, pr[i] + tmp);
        if(rq.empty()){
            tmp += qq.top();
            qq.pop();
        }else{
            if(count == 0){
                tmp += rq.top();
                rq.pop();
                count++;
            }else if(qq.top() > rq.top()){
                tmp += qq.top();
                qq.pop();
            }else{
                tmp += rq.top();
                rq.pop();
                count++;
            }
            count--;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int n;

    cin >> n;
    if (n <= 9) {
        cout << n << endl;
    }
    else if (n <= 99) {
        cout << 9 << endl;
    }
    else if (n <= 999) {
        cout << 9 + (n - 99) << endl;
    }
    else if (n <= 9999) {
        cout << 909 << endl;
    }
    else if (n <= 99999) {
        cout << 909 + (n - 9999) << endl;
    }
    else {
        cout << 90909 << endl;
    }
    return 0;
}


Measured memory_bytes: 3608
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<map>
#include<queue>
#define int long long
using namespace std;
const int INF = 1e10;
const int ZERO = 0;

signed main() {
	int N;
	cin >> N;
	vector<double> vec(N);
	for(int i = 0;i < N;i++) {
		cin >> vec.at(i);
	} 
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	int A = 2;
	double ret = 0;
	for(int i = 0;i < N - 1;i++) {
		ret += vec.at(i) / A;
      	if(i != N - 2) {
      		A *= 2;
        }
	}
	ret += vec.at(N - 1) / A;
	cout << ret << endl;
}

Measured memory_bytes: 256
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>
#include <fstream>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
int gcd(int a, int b)
{
	if (a%b == 0)return b;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int h1, m1, h2, m2, k; cin >> h1 >> m1 >> h2 >> m2 >> k;
	int t1 = h1 * 60 + m1;
	int t2 = h2 * 60 + m2;
	cout << t2 - k - t1 << endl;
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
#define dump(a) cout << #a << " " << a << endl
#define MAX_SIZE 50000
using namespace std;

int N,M;
vector<int> coins;
int memo_cnt[MAX_SIZE+1];

int dfs(const int NN) {
	if (NN == 0) { return 0; }
	if (memo_cnt[NN] != -1) { return memo_cnt[NN]; }

	int min_cnt=INT_MAX;
	for(int i=0; i<M; i++) {
		int next_NN = NN-coins[i];
		if (next_NN >= 0) {
			int depth = dfs(next_NN) + 1;
			min_cnt = min(min_cnt, depth);
		}
	}
	memo_cnt[NN] = min_cnt;

	return min_cnt;
}

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

	memset(memo_cnt,-1,sizeof(memo_cnt));
	for(int i=0; i<M; i++) {
		cin >> value;
		coins.push_back(value);
	}
	sort(coins.begin(),coins.end());
	reverse(coins.begin(), coins.end());
	/*
	for(int i=0; i<M; i++)
		dump(coins[i]);
	*/

	cout << dfs(N) << endl;

	return EXIT_SUCCESS;
}

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

struct edge{
  int to,c;
};

int V,E,ST;
vector<edge> G[20];
int dp[(1<<15)][16];
int solve(int st,int id){
  if( dp[st][id] != -1 ) return dp[st][id];
  if( st == (1<<V)-1 && id == ST ) return dp[st][id] = 0;
  int ret = (1<<29);
  for(int i=0;i<(int)G[id].size();i++){
    edge e = G[id][i];
    if( (st & (1<<e.to) ) ) continue;
    ret = min( ret, solve(st|(1<<e.to),e.to) + e.c );
  }
  return dp[st][id] = ret;
}

int main(){
  cin >> V >> E;
  for(int i=0;i<E;i++){
    int s,t,d;
    cin >> s >> t >> d;
    G[s].push_back((edge){t,d});
  }
  int res = (1<<29);
  for(int i=0;i<V;i++){
    memset(dp,-1,sizeof(dp));
    res = min ( res, solve(0,i) );
    ST++;
  }
  cout << (res==(1<<29)?-1:res) << endl;


}

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

int main(){
	int n, x, l, sum = 0, ans = 1;
	cin >> n >> x;
	for (int i = 0; i < n; ++i) {
		cin >> l;
		sum += l;
		if (sum <= x) ans++;
		else break;
	}
	cout << ans << endl;
	return 0;
}

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

template<typename T>
void fin (T a){
    cout<<a<<endl;
    exit(0);
}

template<typename S>
void print(S a){
    cout<<a<<endl;
}

template<typename U>
void pprint(U a){
    cout<<a;
}

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

    int x;
    cin>>x;
    print(abs(x-1));



    return 0;
}




Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int INF=1e9;
int s,n,m,t,p;
int x[2000];
vector<int> A;
int dp[2005][2005];
 
int main(){
  scanf("%d %d %d",&s,&n,&m);
  for(int i=0;i<s;i++)scanf("%d",&x[i]);
  for(int i=0;i<n;i++){
    scanf("%d %d",&t,&p);
    A.push_back(t-x[p-1]);
  }
  A.push_back(-INF);
  sort(A.begin(),A.end());
  A[0]=0;

  int size=A.size()-1,base=A[1];
  for(int i=1;i<=size;i++)A[i]-=base;
  fill(dp[1],dp[2005],1e9);
  for(int i=1;i<=size;i++){ 
    for(int j=1;j<=m;j++){
      int sum=0;
      for(int k=i-1;k>=0;k--){
        dp[i][j]=min(dp[i][j],dp[k][j-1]+sum);
        sum+=(A[i]-A[k]);
        if(sum>dp[i][j])break;
      }
    }
  }
  cout<<dp[size][m]<<endl;
  return 0;
}

Measured memory_bytes: 16960
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;

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

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

int main(void) {
    ll H, W;
    cin >> H >> W;

    if (H == 1 || W == 1){ 
        cout << 1 << endl;
        return 0;
    }

    if (H % 2 == 1 && W % 2 == 1) {
        cout << (H * W / 2) + 1 << endl;
    } else {
        cout << H * W / 2 << endl;
    }

    return 0;
}


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

int main() {
  //input
  int N;
  string S;
  cin >> N >> S;
  //calc
  int answer = 0;
  if ( N >= 3 ) {
    rep(i,N-2) {
      if ( S.at(i) == 'A' && S.at(i+1) == 'B' && S.at(i+2) == 'C' ) {
        answer++;
      }
    }
  }
  //output
  cout << answer << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);

		while (true) {
			char[] str = sc.nextLine().toCharArray();
			if (str[0] == '.') {
				break;
			}
			ArrayList<Character> a = new ArrayList<Character>();
			for (int i = 0; i < str.length; i++) {
				char b = str[i];
				if (b == '(' || b == ')' || b == '[' || b == ']') {
					a.add(b);
				}
			}

			Character[] c = a.toArray(new Character[0]);
			Stack<Character> stack = new Stack<Character>();
			boolean flg = true;
			for (int i = 0; i < c.length; i++) {
				if (c[i] == '(' || c[i] == '[') {
					stack.push(c[i]);
				} else {
					if (stack.isEmpty()) {
						flg = false;
						break;
					}
					char tmp = stack.pop();
					if (tmp == '(' && c[i] == ')') continue;
					if (tmp == '[' && c[i] == ']') continue;
					flg = false;
					break;
				}
			}
			/*
			for (int i = 0; i < c.length; i++) {
				System.out.print(c[i] + " ");
			}
			System.out.println();
			 */
			
			System.out.println(flg && stack.isEmpty() ? "yes" : "no");
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

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

using namespace std;
using ll = long long;
using ld = long double;

//#define int long long
//signed main(){
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int taka=(c+b-1)/b;
    int aoki=(a+d-1)/d;
    if(aoki>=taka) cout << "Yes" << "\n";
    else cout << "No" << "\n";

    return 0;
}

Measured memory_bytes: 3652
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())




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

	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n;i+=2) {
		int c = 0;
		int x = i;
		for (int j = 1; j <= x;j++) {
			if (x%j == 0)c++;
		}
		if (c == 8)ans++;
	}
	cout << ans << endl;

	return 0;
}

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

struct edge {
  int from, to, cost, time;
  edge(int from, int to, int c, int t) :
    from(from), to(to), cost(c), time(t) {}
};

vector<long long> dijkstra(const vector<vector<edge>>& G, const vector<int>& C, const vector<int>& D, int s, int S){
  const int n = G.size();
  const long long INF = 1e18;
  constexpr int m = 3000;
  S = min(S,m);
  vector d(n,vector(m+1,INF));
  priority_queue<tuple<long long,int,int>> Q;
  Q.emplace(0,S,s);
  while(Q.size()){
    auto [t, c, v] = Q.top();
    t *= -1;
    Q.pop();
    if(d[v][c] < t) continue;
    {
      int c_ = min(m,c + C[v]);
      long long t_ = t + D[v];
      if(d[v][c_] > t_){
        d[v][c_] = t_;
        Q.emplace(-t_,c_,v);
      }
    }
    for(auto e : G[v]){
      if(e.cost > c) continue;
      long long t_ = t + e.time;
      int v_ = e.to;
      int c_ = c - e.cost;
      if(d[v_][c_] > t_){
        d[v_][c_] = t_;
        Q.emplace(-t_,c_,v_);
      }
    }
  }
  vector<long long> ret(n,INF);
  for(int i = 0; i < n; ++i)
    for(auto e : d[i])
      ret[i] = min(ret[i],e);

  return ret;
}

int main(){
  int N, M, S;
  cin >> N >> M >> S;
  vector<vector<edge>> G(N);
  for(int i = 0; i < M; ++i){
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    --u,--v;
    G[u].emplace_back(u,v,a,b);
    G[v].emplace_back(v,u,a,b);
  }
  vector<int> C(N), D(N);
  for(int i = 0; i < N; ++i){
    cin >> C[i] >> D[i];
  }
  auto ans = dijkstra(G,C,D,0,S);
  for(int i = 1; i < N; ++i)
    cout << ans[i] << "\n";
}


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

int main () {
    long long l, r;
    std::cin >> l >> r;
    int L = l % 2019;
    int R = r % 2019;
    if (R < L)
    {
        std::swap(L, R);
    }
    std::vector<int> ans;
    for (int i = L; i <= R; i++)
    {
        if (r - l >= 2019)
        {
            ans.push_back(0);
            break;
        }
        
        for(int j = i + 1; j <= R; j++) {
            ans.push_back((i * j) % 2019);
        }
    }
    
    ans.push_back(2018);

    std::cout << *std::min_element(ans.begin(), ans.end()) << "\n";
}

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


def make_357(now):
    if int(now) > N:
        return 0
    count = 0
    for c in '753':
        if now.count(c) > 0:
            count+=1
    count = count // 3
    for c in '753':
        count += make_357(now+c)
    
    return count

print(make_357('0'))

Measured memory_bytes: 3060
import re
W = input()
T = input()
T = T.lower()
L = []
while T != 'END_OF_TEXT':
    L.append(re.split(r'\s',T.lower()))
    T = input()
n = 0
for i in range(len(L)):
    for j in range(len(L[i])):
        if L[i][j] == W:
            n += 1
    # if re.findall(W,i):
    #     n += len(re.findall(W,i))
print(n)


Measured memory_bytes: 6508
#include <iostream>
#include <utility>

using namespace std;

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

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    if(a > b) swap(a, b);
    int cnt = 0;
    rep(i, b){
        if(b % (b-i) == 0 and a % (b-i) == 0){
            cnt++;
            if(cnt == k){
                cout << b - i << endl;
                break;
            }
        }
    }
}



Measured memory_bytes: 256
border = 101


def manhattan_distance(Cx, Cy, H, X, Y):
    return max(H - abs(X - Cx) - abs(Y - Cy), 0)


def judge_center(Cx, Cy, cords):
    for x, y, h in cords:
        if h > 0:
            H = abs(x - Cx) + abs(y - Cy) + h
            break
    for x, y, h in cords:
        tmp = manhattan_distance(Cx, Cy, H, x, y)
        if h != tmp:
            return -1
    return H


def main():
    N = int(input())
    cords = [list(map(int, input().split(' '))) for _ in range(N)]

    for tmp_Cx in range(border):
        for tmp_Cy in range(border):
            h = judge_center(tmp_Cx, tmp_Cy, cords)
            if h != -1:
                print('{} {} {}'.format(tmp_Cx, tmp_Cy, h))
                return 0


if __name__ == '__main__':
    main()


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

int main(){
  string s;
  cin >> s;
  if ( s[0] == 'Y' && s[1] == 'A' && s[2] == 'K' && s[3] == 'I' )
    cout << "Yes" << endl;
  else
    cout << "No"  << endl;
}

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

using namespace std;

int main() {
  
  string game;
  while(1) {
    bool flag = 0;
    
    for(int I=0; I<3; I++) {
      
      cin >> game;
      if(game == "0") { flag = 1; break; }
    
      int cntA = 0, cntB = 0;
      
      game = game.substr(1);
      
      int const N = game.size();
      for(int i=0; i<N; i++) {
	cntA += game[i] == 'A';
	cntB += game[i] == 'B';
      }
      
      if(cntA > cntB) {
	if(cntA >= 11) {
	  cntA = cntB + 2;
	}
	else {
	  cntA = 11;
	}
      }
      else {
	if(cntB >= 11) {
	  cntB = cntA + 2;
	}
	else {
	  cntB = 11;
	}
      }
    
      cout << cntA << ' ' << cntB << endl;
      
    }
    
    if(flag) break;
  }
  
  return 0;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bitset<1000010>pk;
vector<ll>udd;
void eos(ll x)
{
    ll g,h,f;
    pk.set();
    pk[0]=pk[1]=0;
    for(h=4;h<=x;h+=2)pk[h]=0;
    udd.push_back(2);
    for(g=3;g<=x;g+=2)if(pk[g]){
        for(h=g*g,f=2*g;h<=x;h+=f)pk[h]=0;
        udd.push_back(g);
    }
}
int main()
{
    eos(1e6+7);
    int g,h,nt,re=0;
    ll q,x;
    scanf("%lld",&q);
    for(g=0;udd[g]*udd[g]<=q;g++){
        x=udd[g];
        nt=0;
        while(q%x==0){
            q/=x;
            nt++;
        }
        for(h=1;h<=nt;nt-=h,h++)
            re++;
    }
    if(q!=1)re++;
    printf("%d\n",re);
    return 0;
}


Measured memory_bytes: 4280
import sys

input = sys.stdin.readline


def main():
    x1, y1, x2, y2 = map(int, input().split())
    x, y = x1 - x2, y1 - y2
    print(x2 + y, y2 - x, x1 + y, y1 - x)
    # print(" ".join([x1 - x, y1, x2, y2]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1e9;

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

    vector<int> b(n),c(n);
    for(int i=0; i<n; i++){
        cin >> b[i] >> c[i];
    }
    vector<int> dp(m+1, inf);
    dp[0] = 0;
    for(int i=0; i<n; i++){
        for(int j=m; j>=0; j--){
            dp[j] = min(dp[j], dp[max(j-b[i], 0)]+c[i]);
        }
        for(int j=m; j>0; j--){
            dp[j-1] = min(dp[j-1], dp[j]);
        }
    }

    int ans = 0;
    for(int i=0; i<m; i++){
        ans = max(ans, a[i]-dp[i+1]);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3252
main = do
  [h, w] <- map read . words <$> getLine :: IO [Int]
  n <- readLn :: IO Int
  a <- map read . words <$> getLine :: IO [Int]
  let ans = zipWith reverseOdd [1..] . pack w . make $ a
  putStr $ unlines . map (unwords . map show) $ ans

make :: [Int] -> [Int]
make s = concat $ zipWith (\x y -> replicate x y) s [1..]

pack :: Int -> [Int] -> [[Int]]
pack w s
  | length s <= w = [s]
  | otherwise     = (take w s):(pack w $drop w s)

reverseOdd :: Int -> [Int] -> [Int]
reverseOdd n s
  | mod n 2 == 0 = s
  | otherwise    = reverse s


Measured memory_bytes: 1916
#include<iostream>
using namespace std;
int main() {
	long a, b[6], c[6],a2[3],b2[3],c2[3];
	for (int i = 0; i < 18; i++) {
		cin >> a;
	}
	/*for (int i = 0; i < 6; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < 6; i++) {
		cin >> c[i];
	}*/
	/*a2[0]= a[0] * 3600 + a[1] * 60 + a[2];
	b2[0] = b[0] * 3600 + b[1] * 60 + b[2];
	c2[0] = c[0] * 3600 + c[1] * 60 + c[2];
	a2[1] = a[3] * 3600 + a[4] * 60 + a[5];
	b2[1] = b[3] * 3600 + b[4] * 60 + b[5];
	c2[1] = c[3] * 3600 + c[4] * 60 + c[5];
	a2[2] = a2[1] - a2[0];
	b2[2] = b2[1] - b2[0];
	c2[2] = c2[1] - c2[0];
	a[0] = a2[2] / 3600; a2[2] = a2[2] % 3600;
	a[1] = a2[2] / 60; a2[2] = a2[2] % 60;
	a[2] = a2[2];
	b[0] = b2[2] / 3600; b2[2] = b2[2] % 3600;
	b[1] = b2[2] / 60; b2[2] = b2[2] % 60;
	b[2] = b2[2];
	c[0] = c2[2] / 3600; c2[2] = c2[2] % 3600;
	c[1] = c2[2] / 60; c2[2] = c2[2] % 60;
	c[2] = c2[2];*/
	cout << 0 << " " << 0 << " " << 1 << endl;
	cout << 0 << " " << 0 << " " << 59 << endl;
	cout << 15 << " " << 59 << " " << 59 << endl;
}

Measured memory_bytes: 3084
# https://atcoder.jp/contests/abc116/tasks/abc116_d

N, K = gets.split.map(&:to_i)
max_in_type = {}
values = []

N.times do
  temp = gets.split.map(&:to_i)
  max_in_type[temp[0]] = temp[1] if !(max_in_type[temp[0]]&.>(temp[1]))
  values << (temp[1] << 17) + temp[0]
end

ph = []
sum = 0
use_type_count = 0
type_flags = {}

t_mask = (1 << 17) - 1

values.sort[(N-K)...N].reverse.each do |t_v|
  t = t_v & t_mask
  v = t_v >> 17
  sum += v
  if !type_flags[t]
    type_flags[t] = true
    use_type_count += 1
  else
    ph << v
  end
end
ph.sort!
ans = sum + use_type_count**2

rph = max_in_type.select { |t, v| !type_flags[t] }.values.sort.reverse

t = 0
phsize = ph.size
rphsize = rph.size
(phsize > rphsize ? rphsize : phsize).times do |i|
  sum = sum - ph[i] + rph[i]
  t = sum + (use_type_count += 1)**2
  ans = t if t > ans
end

p ans

Measured memory_bytes: 17904
#include <iostream>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;

int main(){

  string str;

  while(1){
    getline(cin, str);
    if(str[0] == '.') break;
    int flag = 1;
    stack<int> s;
    for(int i = 0; i < str.size(); i++){
      if(str[i] == '('){
        s.push(1);
      }else if(str[i] == '['){
        s.push(2);
      }else if(str[i] == ']'){
        if(!s.empty() && s.top() == 2){
          s.pop();
        }else{
          flag = 0;
          break;
        }
      }else if(str[i] == ')'){
        if(!s.empty() && s.top() == 1){
          s.pop();
        }else{
          flag = 0;
          break;
        }
      }
    }
    if(flag && s.empty()){
      cout << "yes" << endl;
    }else{
      cout << "no" << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3076
#include<iostream>
#include<cstdio> 
using namespace std;
typedef long long ll;
const int N=2005;

int n,x,mymin,mymini;
ll ans,dp[N][N],a[N];

int main(){
	scanf("%d%d",&n,&x);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++) dp[i][0]=a[i];
	for (int i=1;i<=n;i++)
		for (int j=1;j<n;j++){
			int k=i-j;
			if (k<=0) k+=n;
			dp[i][j]=min(dp[i][j-1],a[k]);
		}
	ll ans=1e18;
	for (int i=0;i<n;i++){
		ll sum=0;
		for (int j=1;j<=n;j++) sum+=dp[j][i];
		ans=min(ans,sum+i*x);
	}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 31616
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

int main() {
  vector<vector<int>> a(3, vector<int>(3));
  rep(i, 3) rep(j, 3) { cin >> a[i][j]; }

  vector<vector<bool>> choosen(3, vector<bool>(3, false));
  int N;
  cin >> N;
  rep(i, N) {
    int b;
    cin >> b;
    rep(i, 3) rep(j, 3) { choosen[i][j] = (choosen[i][j] || (a[i][j] == b)); }
  }

  bool result = ((choosen[0][0] && choosen[1][1] && choosen[2][2]) ||
                 (choosen[0][2] && choosen[1][1] && choosen[2][0]));
  rep(i, 3) {
    result = (result || (choosen[i][0] && choosen[i][1] && choosen[i][2]));
  }
  rep(j, 3) {
    result = (result || (choosen[0][j] && choosen[1][j] && choosen[2][j]));
  }

  cout << (result ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
int n;
bool vis[1000005];
int prime[1000005];
int t[1000005],e[1000005];
int cnt;
int main(){
	cin>>n;
	for(int i=2;i<=n;++i)
	{
		if(!vis[i])
		{
			prime[++cnt]=i;
			t[i]=2;
			e[i]=1;
		}
		for(int j=1;j<=cnt;++j)
		{
			if(i*prime[j]>n) break;
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				t[i*prime[j]]=t[i]/(e[i]+1)*(e[i]+2);
				e[i*prime[j]]=e[i]+1;
				break;
			}
			else
			{
				t[i*prime[j]]=t[i]*2;
				e[i*prime[j]]=1;
			}
		}
	}
	ll ans=0;
	t[1]=1;
	for(int i=1;i<n;i++)
		ans+=t[n-i];
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 12756
#pragma GCC optimize("Ofast")

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

int main() {
    ll X, Y, A, B, C;
    cin >> X >> Y >> A >> B >> C;
    priority_queue<ll> que;
    vector<ll> p(A), q(B), r(C);
    rep(i, A) cin >> p[i];
    rep(i, B) cin >> q[i];
    rep(i, C) {
        cin >> r[i];
        que.push(r[i]);
    }
    sort(p.rbegin(), p.rend());
    sort(q.rbegin(), q.rend());

    rep(i, X) que.push(p[i]);
    rep(i, Y) que.push(q[i]);

    ll ans = 0;

    rep(i, X+Y) {
        ans += que.top(); que.pop();
    }

    cout << ans << endl;
}


Measured memory_bytes: 8688
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	ps := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&ps[i])
	}

	m := make([]int, n)
	for i := 0; i < n; i++ {
		m[ps[i]-1] = i
	}

	mx := 1
	cnt := 1
	for i := 1; i < n; i++ {
		if m[i-1] < m[i] {
			cnt++
		} else {
			cnt = 1
		}
		mx = max(mx, cnt)
	}
	fmt.Println(n - mx)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}


Measured memory_bytes: 6656