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

int main() {
  int n;
  cin >> n;
  vector<int> wi(n);
  for (int i = 0; i < n; i++) cin >> wi.at(i);
  
  int ans = 10000;
  for (int i = 0; i < n; i++) {
    int l = 0;
    int r = 0;
    for (int j = 0; j <= i; j++) l += wi.at(j);
    for (int j = i+1; j < n; j++) r += wi.at(j);
    ans = min(ans, abs(l-r));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <string>
#include <numeric>
#include <cmath>
#include <cassert>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <cstdint>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

constexpr auto M = 1000000007;

// x は高々9
int64_t fib(int x) {
    switch (x) {
        case -1:
            return 0;
        case 0:
        case 1:
            return 1;
        case 2:
            return 2;
        case 3:
            return 3;
        case 4:
            return 5;
        case 5:
            return 8;
        case 6:
            return 13;
        case 7:
            return 21;
        case 8:
            return 34;
        default:
            assert(false);
            return -1;
    }
}

int64_t solve(int h, int w, int k) {
    vector<int64_t> current(w + 2, 0);
    vector<int64_t> next(w + 2, 0);

    current[1] = 1;

    for (int hh = 1; hh <= h; ++hh) {
        for (int x = 1; x <= w; ++x) {
            next[x] = (current[x - 1] * fib(x - 2) * fib(w - x) + current[x] * fib(x - 1) * fib(w - x) + current[x + 1] * fib(x - 1) * fib(w - x - 1)) % M;
        }
        current.swap(next);
    }

    return current[k];
} 

int main() {
    int h, w, k;
    cin >> h >> w >> k;

    cout << solve(h, w, k) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

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

using namespace std;

const long long mod = 1000000007;

template<typename T>
constexpr T gcd(T m, T n) noexcept {
	T g = 1;

	while (m != 0) {
		if (m < n) swap(m, n);

		if (m & 1) {
			if (n & 1) m = (m - n) >> 1;
			else n = n >> 1;
		}
		else {
			if (n & 1) {
				m = m >> 1;
			}
			else {
				n = n >> 1;
				m = m >> 1;
				g = g << 1;
			}
		}
	}

	return g * n;
}

template<typename T>
constexpr T lcm(T m, T n) noexcept {
	return (m * n) / gcd(m, n);
}

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

	ll a, b;
	cin >> a >> b;
	cout << lcm(a, b) << "\n";

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define pp pop_back
#define f first
#define s second
#define sz(a) (int)((a).size())
#define NoType ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL)
#define mp make_pair

typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//find_by_order(x) -> returns an iterator to the element at a given position
//order_of_key(x) -> returns the position of a given element

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pi;

const int mod = (int)1e9 + 7;
const int MAXN = 2e5+12;
//indexed_set s;

string a,b;

int main() {

    NoType;

    cin >> a >> b;
    int ans = 0;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) ans++;
    }

    cout << ans;

return 0;
}


Measured memory_bytes: 3788
n, x, y = map(int, input().split())
graf = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n - 1):
    for j in range(i + 1, n):
        graf[i][j] = graf[i][j - 1] + 1

# (y - x - 1)
# for i in range(x):
#     for j in range(y - 1, n):
#         graf[i][j] -= y - x - 1
#
#     for j in range(y - 2, x - 1, -1):
#         graf[i][j] = min(graf[i][j], graf[i][j + 1] + 1)

for i in range(n):
    for j in range(i + 1, n):
        graf[i][j] = min(graf[i][j], abs(i - x + 1) + abs(y - 1 - j) + 1)

# print(graf)
k = [0 for _ in range(n)]
for i in graf:
    for j in i:
        k[j] += 1
# print(k)
for i in k[1::]:
    print(i)

Measured memory_bytes: 80604
#include <stdio.h>
int n,i,A[2000];
int solve(int,int);
int main(){
  int m[2000],q;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++)
    scanf("%d",&m[i]);
  for(i=0;i<q;i++){
    if(solve(0,m[i])==1)
      printf("yes\n");
    else printf("no\n");
  }
  return 0;
}
int solve(int i,int m){
  int res;
  if(m==0)
    return 1;//真                                                               
  if(i>=n)
    return 0;//負                                                               
  res=solve(i+1,m)||solve(i+1,m-A[i]);
  return res;
}




Measured memory_bytes: 2108
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
using namespace std;

int main() {
	int N;
	cin>>N;
	int K;
	cin>>K;
	vector<double> vec(N+1,0);
  	vector<double> ruiseki(N+2,0);
  	vector<double> kitai(N+1,0);
	for(int i=1; i<=N; i++){
		double p; cin>>p;
		vec[i]=p;
      	kitai[i]=(1/vec[i])*((0.5)*(vec[i])*(vec[i]+1));
	}
  	for(int i=1; i<=N; i++) ruiseki[i+1]=ruiseki[i]+kitai[i];
  	double mx=-1;
	for(int i=1; i<=N-K+1; i++){
		double tmp=ruiseki[i+K]-ruiseki[i];
		
      	mx=max(tmp,mx);
		
	}
  cout<<setprecision(15)<<mx<<endl;
}
		
		
		
		
		
		
		
		
	

Measured memory_bytes: 4992
import collections, bisect
s = tuple(input())
t = tuple(input())
ls = len(s)
idx = collections.defaultdict(list)
dct = collections.defaultdict(list)
ln = -1
loop = 0
for i, v in enumerate(s):
    idx[v].append(i)
for i in t:
    t_idx = idx[i]
    if t_idx:
        bn = bisect.bisect_left(t_idx, ln + 1)
        if bn >= len(t_idx):
            ln = t_idx[0]
            loop += 1
        else:
            ln = t_idx[bn]
    else:
        print(-1)
        exit()
print(ls * loop + ln + 1)


Measured memory_bytes: 9256
#include <iostream>

using namespace std;

int main()
{
    long n, input, i=1, max, min, sum=0;
    
    cin >> n >> input;
    max = input;
    min = input;
    for (i=1;i<=n;i++)
    {
        sum = sum + input;
        if (input < min)
        {
        min = input;
        }
        if (input > max)
        {
            max = input;
        }
        cin >> input;
    }
     cout << min << " " << max  << " " << sum<< endl;
   return 0;
}




Measured memory_bytes: 3112
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1<<30;

int main() {
  string s; cin >> s;
  int N = s.size();
  ll sum = 0;
  for(int i = 0; i < (1<<(N-1)); i++) {
    ll t = s[0] - '0';
    for(int j = 0; j < N-1; j++) {
      if(i & (1<<j)) {
        sum += t;
        t = s[j+1] - '0';
      } else {
        t *= 10;
        t += s[j+1] - '0';
      }
    }
    sum += t;
  }
  cout << sum << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x) cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define SANKOU(n, a, b) cout << ((n) ? (#a) : (#b)) << endl
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define P pair<int, int>
#define V vector<int>
#define M map<int, int>
#define S set<int>

char a;
int n, k;

void solve()
{
}

signed main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        char b;
        cin >> b;
        if (i == k) {
            b -= 'A' - 'a';
        }
        cout << b;
    }
    cout << endl;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

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

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

vector<ll> uf(100001);
vector<ll> uf_t(100001,1);

void init_uf(){
  rep(i,100001) uf[i]=i;
}

ll root(ll x){
  if(uf[x] == x) return x;
  return uf[x] = root(uf[x]);
}

void unite(ll x,ll y){
  ll rx=root(x);
  ll ry=root(y);  
  if(rx==ry) return;
  uf_t[ry]+=uf_t[rx];
  uf_t[rx]=0;
  uf[rx]=ry;
}

bool same(ll x,ll y){
  ll rx=root(x);
  ll ry=root(y);  

  return rx==ry;
}

int main(void){

  ll n,m;
  cin>>n>>m;

  vector<ll> a(m);
  vector<ll> b(m);  

  vector<ll> ans(m+1,0);

  vector<ll> teri(n,1);

  ans[m]=n*(n-1)/2;

  rep(i,m){
    cin>>a[i];
    cin>>b[i];
  }

  init_uf();

  for(ll i=m-1;i>=0;i--){
    ll tmp_ans=ans[i+1];
    ll n1,n2;
    if(same(a[i],b[i])){
      n1=0;
      n2=0;
    }
    else{
      n1=uf_t[root(a[i])];
      n2=uf_t[root(b[i])];    
      unite(a[i],b[i]);
    }
    
    tmp_ans-=n1*n2;

  ans[i]=tmp_ans;

  }

  rep1(i,m){
    cout << ans[i] << endl;
  }

  return 0;

}


Measured memory_bytes: 6016
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

#define REP(i, init, n) for(int i = (int)(init); i < (int)(n); i++)

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

int main() {
    int n, m;
    cin>>n>>m;
    scc_graph g(n);
    REP(i, 0, m){
        int from, to;
        cin >> from >> to;
        g.add_edge(from, to);
    }
    vvi scc = g.scc();
    cout << scc.size() << endl;
    for(auto v: scc){
        cout << v.size() << " ";
        for(auto e: v){
            cout << e << " ";
        }
        cout << endl;
    }
}

Measured memory_bytes: 40560
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_H 550
#define MAX_W 550
#define MAX_D 4
#define INF 1e9
 
struct State{
    int d,x,y;
    State(int d,int x,int y) :
	d(d),x(x),y(y) {}
   
    bool operator > (const State &s)const{
	return d > s.d;
    }
};
 
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
 
struct TroddenCable{
    int H,W,N,sx,sy,gx,gy;
    int cost[MAX_H][MAX_W][MAX_D];
    int d[MAX_H][MAX_W];
 
    TroddenCable(){
	for(int i = 0 ; i < MAX_H ; i++){
	    for(int j = 0 ; j < MAX_W ; j++){
		d[i][j] = INF;
		for(int k = 0 ; k < MAX_D ; k++){
		    cost[i][j][k] = 0;
		}
	    }
	}
    }
 
    int getDir(char x){
	if(x == 'L') return 0; 
	if(x == 'U') return 1; 
	if(x == 'R') return 2; 
	if(x == 'D') return 3; 
	return -1;
    }
 
    void input(){
	int x,y,T;
	string S;
	cin >> W >> H >> N;
	cin >> sx >> sy >> gx >> gy;
	for(int i = 0 ; i < N ; i++){
	    cin >> x >> y >> T;
	    cin >> S;
	    for(int j = 0 ; j < T ; j++){
		for(int k = 0 ; k < (int)S.size() ; k++){
		    int _dir = getDir(S[k]);
		    int nx = x + dx[_dir], ny = y + dy[_dir];
		    if(0 > nx || nx >= W || 0 > ny || ny >= H){
			continue;
		    }
		    if(x == nx){
			cost[max(y,ny)][x][2]++;
			cost[max(y,ny)][x+1][0]++;
		    }else if(y == ny){
			cost[y][max(x,nx)][3]++;
			cost[y+1][max(x,nx)][1]++;
		    }
		    x = nx; y = ny;
		}
	    }
	}
    }
 
    int solve(){
	priority_queue<State,vector<State>,greater<State> > Q;
	Q.push(State(0,sx,sy));
	d[sy][sx] = 0;
	while(!Q.empty()){
	    State s = Q.top(); Q.pop();
	    int x = s.x,y = s.y;
	    if(d[y][x] < s.d) continue;
	    if(x == gx && y == gy) return d[y][x]; 
	    for(int i = 0 ; i < 4 ; i++){
		int nx = x + dx[i], ny = y + dy[i];
		if(0 > nx || nx > W || 0 > ny || ny > H) continue; 
		if(d[y][x] + cost[y][x][i] < d[ny][nx]){
		    d[ny][nx] = d[y][x] + cost[y][x][i];
		    Q.push(State(d[ny][nx],nx,ny));
		}
	    }
	}
	return -1;
    }
 
    void run(){
	input();
	cout << solve() << endl;
    }
};
 
int main(){
    TroddenCable tc;
    tc.run();
    return 0;
}

Measured memory_bytes: 11944
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) ((x < 0)?-(x):x)
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

typedef long long cat;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<uint64_t> pos_sum(2000*N/64+2, 0);
	pos_sum[0] = 1;
	cat sum = 0;
	for(int i = 0; i < N; i++) {
		int a;
		cin >> a;
		for(int j = sum/64; j >= 0; j--) {
			if(a%64 != 0) pos_sum[j+a/64+1] |= pos_sum[j] >> (64-a%64);
			pos_sum[j+a/64] |= pos_sum[j] << (a%64);
		}
		sum += a;
	}
	for(int s = sum-sum/2; s <= sum; s++) if((pos_sum[s/64]>>(s%64))&1) {
		cout << s << "\n";
		return 0;
	}
	return 0;
}

// look at my code
// my code is amazing


Measured memory_bytes: 768
A=int(input())
B=int(input())
C=int(input())
X=int(input())
cnt=0
for a in range(min(A,X//500)+1):
    for b in range(min(B,X//100)+1):
        for c in range(min(C,X//50)+1):
            if 500*a+100*b+50*c==X:
                cnt+=1
print(cnt)

Measured memory_bytes: 3064
def main
  h, w, n = gets.split.map(&:to_i)

  # 高橋君は動けるときは必ず動かないといけない

  # 障害物がない場合、ans == w となる ※青木は一切動かず壁まで到達

  # x < y の障害物は無視 ※決してたどり着けないので

  # x で昇順ソート
  #
  # x - y を diff と定義
  # min_diff = 1
  # 
  # 最初に 1 <= diff となる障害物がゴール
  # ただし、その前に diff == 0 となる障害物が見つかった場合、
  # min_diff を1加算 する
  #
  # 以下同じで、min_diff <= diff となる障害物がゴールだが、
  # diff == min_diff-1 となる障害物が見つかった場合は
  # 更に min_diff += 1 する

  o_ary = []
  n.times do
    # 原点(0, 0)に変換
    x, y = gets.split.map do |c|
      c.to_i - 1
    end

    # x < y は無視
    next if x < y

    o_ary << [x, y]
  end

  o_ary.sort!
  # pp o_ary

  diff = 1
  o_ary.each do |(x, y)|
    if (x - y) == (diff - 1)
      # 青木くんの行動を制限するブロック
      diff += 1
      
    elsif diff <= x - y
      # 目標ブロックに到達
      return puts x
    end
  end
  puts h
end

if __FILE__ == $0
  main
end


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

int main() {
  long long X; cin >> X ;
  long long i = 100;
  long long ans = 0;
  while (true) {
    ans++;
    i = i * 1.01;
    if (i >= X) {
      break;
    }
  }

  cout << ans << endl;

  return 0;
}


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

int main()
{
    int a, b, ar[1000], i, s=0;
    cin>>a>>b;
    for(i=0; i<a; i++)
    {
        cin>>ar[i];
    }
    sort(ar, ar+a);
    for(i=0; i<b; i++)
    {
        s=s+ar[i];
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
int main(void)
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a>=b && a>=c)
    {
        printf("%d",b+c);
    }
    else if(b>=a && b>=c)
    {
        printf("%d",a+c);
    }
    else
    {
        printf("%d",a+b);
    }
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
 public static void main(String[] args) {
   Scanner kbd =new Scanner(System.in);
   int n=kbd.nextInt();
   int a=n%10;
   if(a==2||a==4||a==5||a==7||a==9){
     System.out.println("hon");
   }else if(a==3){
     System.out.println("bon");
   }else{
   System.out.println("pon");
   }
 }
}



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

typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string str[101];
    int r,c;
    cin>>r>>c;
    for(int i=0;i<r;i++)
    {
        cin>>str[i];
    }
    for(int i=0;i<c+2;i++)
    {
        cout<<"#";
    }
    cout<<endl;
    for(int i=0;i<r;i++)
    {
        cout<<"#";
        cout<<str[i];
        cout<<"#"<<endl;
    }
    for(int i=0;i<c+2;i++)
    {
        cout<<"#";
    }
    cout<<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;
using ll = long long;

int main() {
    int s;
    cin >> s;
    
    map<int, int> mp;
    mp[s] = 1;

    for(int i = 2;i < 1000005; i++) {
        if(s % 2 == 0) s /= 2;
        else s = 3 * s + 1;
        if(mp.count(s)) {
            cout << i << endl;
            return 0;
        }
        else {
            mp[s] = i;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define mod 1000000007
#define M 1000000
using namespace std;

int isprime(ll n){
    if(n==1) return 0;
    if(n==2 || n==3) return 1;
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}

void answer(){
    ll n,ans=0,m,p=1,an=1;
    cin>>n;
    while(n>0){
        ans++;
        n=n/2;
    }
    ans--;
    while(ans--){
        an=1+2*p;
        p = an;
    }
    cout<<an;
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    //cin>>q; while(q--)
        answer();
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    int n = N % 10;
    if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9) {
        cout << "hon" << endl;
    }
    else if (n == 3) {
        cout << "bon" << endl;
    }
    else {
        cout << "pon" << endl;
    }
}

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

int main(void) {
	long long l, r;
	cin >> l >> r;
	r = min(r, l+4038);
	int ans = 2018;
	for (long long i = l; i <= r; i++) {
		for (long long j = i+1; j <= r; j++) {
			int x = i * j % 2019;
			ans = min(ans, x);
		}
	}
 	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import nlargest
from heapq import nsmallest
#-------------------------------------------------------------------

N, M = map(int, input().split())		# 5 7 2
#A = list( map(int, input().split()) )
H = list( -int(i) for i in input().split() )

#p("A ",A)
p("H ",H)

heapify(H)

p("H ",H)

for _ in range(M):
	h = heappop(H)//(-2)
	heappush(H,-h)
	
	#p("h,H ",h,H)


print(-sum(H))




Measured memory_bytes: 14260
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> h(N);
    for(int i = 0; i < N; i++) cin >> h[i];

    vector<vector<int>> G(N);

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);
    }

    int ans = 0;
    for(int i = 0; i < N; i++) {
        bool check = true;
        for(int j = 0; j < (int)G[i].size(); j++) {
            if(h[i] <= h[G[i][j]]) {
                check = false;
                break;
            }
        }

        if(check) {
            ans++;
        }
    }

    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 8772
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    const int MMAX = 12;
    #else // ONLINE_JUDGE
    const int MMAX = 1005;
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> a(m), b(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    vector<bitset<MMAX>> masks(n);
    vector<bool> bad(n, false);
    for (int i = 0; i < n; ++i) {
        vector<bool> forced(n, false);
        forced[i] = true;
        masks[i].set(i);
        for (int j = m - 1; j >= 0; --j) {
            if (forced[a[j]] && forced[b[j]]) {
                bad[i] = true;
                break;
            } else if (forced[a[j]]) {
                forced[b[j]] = true;
                masks[i].set(b[j]);
            } else if (forced[b[j]]) {
                forced[a[j]] = true;
                masks[i].set(a[j]);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (bad[i]) {
            continue;
        }
        for (int j = i + 1; j < n; ++j) {
            if (!bad[j] && (masks[i] & masks[j]).count() == 0) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
int main() {
  ll N, K;
  cin >> N >> K;
  vector<ll> P(N), C(N);
  bool ollzero = true;
  REP(i, N) cin >> P[i], P[i]--;
  REP(i, N) { cin >> C[i]; }
  ll ans = -1e17;
  REP(i, N) {
    vector<bool> Kita(N, false);
    ll tmpK = K, num = 0;
    ll now = i, loopcnt = 0;
    bool cat = false;
    while (tmpK > 0) {
      
      now = P[now];
      if (Kita[now] == true && !cat) {
        cat = true;
        ll a = (tmpK - 1) / loopcnt;
        ll tmp = num * a;
        if (tmp < 0) break;
        num += tmp;
        tmpK -= a * loopcnt;
        ans = max(ans, num);
      }
      num += C[now];
      Kita[now] = true;
      ans = max(ans, num);
      loopcnt++;
      tmpK--;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using P = pair<int ,int>;
const int INF = 1001001001;
const int MOD = 1000000007;
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 (b<a) {a=b; return 1;} return 0;}

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...)
#define print(...)
#endif

int main() {
    int n, m; cin >> n >> m;
    vector<int> dp(1<<n, INF);
    dp[0] = 0;

    rep(i, m) {
        int cost, box; cin >> cost >> box;
        int x = 0;
        rep(j, box) {
            int y; cin >> y; y--;
            x += 1<<y;
        }
        rep(j, 1<<n) {
            int z = x|j;
            dp[z] = min(dp[j]+cost, dp[z]);
        }
        debug(dp);
    }
    int ans = dp[(1<<n)-1];
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
 
int main(){
    int N;cin>>N;
    int a[N],b[N];
    for(int i=0;i<N;i++) cin>>a[i];
    for(int i=0;i<N;i++) b[i]=a[i];
    
    sort(a,a+N);
    for(int i=0;i<N;i++){
        if(b[i]==a[N-1]) cout << a[N-2] <<endl;
        else cout << a[N-1] <<endl;
    }
      
}

Measured memory_bytes: 5140
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

template<class T> struct RMQ {
    int n;
    vector<T> A; vector<int> I;
    RMQ(int n_=0): n(n_), A(n), I(2*n) {
	for (int i=0; i<n; i++) I[i+n] = i;
	for (int i=n; --i;) I[i] = I[2*i];
    }
    RMQ(const vector<T> &a): n(a.size()), A(a), I(2*n) {
	for (int i=0; i<n; i++) I[i+n] = i;
	for (int i=n; --i;) I[i] = (A[I[i*2+1]] < A[I[i*2]]? I[i*2+1]: I[i*2]);
    }
    void modify(int i, const T &v) {
	A[i] = v;
	for (i+=n; i>>=1;) I[i] = (A[I[i*2+1]] < A[I[i*2]]? I[i*2+1]: I[i*2]);
    }
    int min_i(int x, int y) {
	x += n; y += n;
	int p = -1;
	for (; x<y; x>>=1, y>>=1) {
	    if (y & 1) { --y; if (p < 0 || A[I[y]] < A[p]) p = I[y]; }
	    if (x & 1) { if (p < 0 || A[I[x]] < A[p]) p = I[x]; x++; }
	}
	return p;
    }
    T min_v(int x, int y) { return A[min_i(x, y)]; }
};

int N, T, E;
int A[100111];
LL dp[100111];

int main() {

    scanf("%d%d%d", &N, &E, &T);
    REP (i, N) scanf("%d", A+i+1);
    A[N+1] = E;

    RMQ<LL> X1(N + 10), X2(N + 10);
    X1.modify(0, -2LL * A[1]);


    int mid = 0;
    LL cst = 0;
    for (int i=1; i<=N; i++) {

	while (2LL * (A[i] - A[mid]) > T) mid++;
	cst = 1LL << 60;

	if (0 < mid-1) amin(cst, X1.min_v(0, mid-1) + 3LL * A[i]);
	if (mid-1 < i) amin(cst, X2.min_v(max(0, mid-1), i) + T + A[i]);
	amin(cst, X2.min_v(i-1, i) + T + A[i]);

	X1.modify(i, cst - 2LL * A[i+1] - A[i]);
	X2.modify(i, cst - A[i]);

//	eprintf("%d %lld %d\n", i, cst, mid);
    }

    LL ans = cst + E - A[N];
    printf("%lld\n", ans);

    return 0;
}



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

int main() {
  int q; cin >> q;
  map<string, int> mp;
  for (int i = 0; i < q; i++) {
    int cmd; cin >> cmd;
    if (cmd == 0) {
      string key; int x; cin >> key >> x;
      mp[key] = x;
    }
    if (cmd == 1) {
      string key; cin >> key;
      auto itr = mp.find(key);
      if (itr != mp.end()) {
        cout << mp[key] << endl;
      } else {
        cout << 0 << endl;
      }
    }
    if (cmd == 2) {
      string key; cin >> key;
      mp.erase(key);
    }
  }
}



Measured memory_bytes: 27772
# coding: utf-8
# Your code here!


w,h,x,y = [int(i) for i in input().split()]


if 2*x == w and 2*y == h:
    ans = 1
else:
    ans = 0
    

#print("{:.2f}".format(w*h/2.0), ans)
print(w*h/2, ans)
#print((10**10-1)/2.0)

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

int main() {
  int n;
  cin >> n;
  
  vector<int64_t> lucas(3);
  rep(i, n) {
    if (i == 0) {
      lucas.at(0) = 2;
      lucas.at(1) = 1;
      lucas.at(2) = 1;
    } else {
      lucas.at(2) = lucas.at(0) + lucas.at(1);
      lucas.at(0) = lucas.at(1);
      lucas.at(1) = lucas.at(2);
    }
  }
  cout << lucas.at(2) << endl;
}


Measured memory_bytes: 256
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.ArrayList;
import java.util.List;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//文字列読込み
		Scanner sc = new Scanner(System.in);

		//結果格納
		int scInt;
		int befInt = 0; //前の値=0
		boolean result = true;

		while (sc.hasNext()) {
			//1行読込み
			scInt = sc.nextInt();
			if (befInt < scInt ) {
				result = true;	
			} else {
				result = false;
				break;
			}
			befInt = scInt;
		}
		
		if (result == true) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 26400
#include<bits/stdc++.h>
using namespace std;
int m,n;
string s[130];
map<vector<int>,int> dp;
int rec(vector<int> S){
  if(S.size()<=1)return 0;
  if(dp[S]>0)return dp[S];
  
  dp[S]=m;
  for(int i=0;i<m;i++){
    
    vector<int> ok,ng;
    
    for(int j=0;j<S.size();j++){
      if(s[S[j]][i]=='1')ok.push_back(S[j]);
      else ng.push_back(S[j]);
    }
    
    if(ok.size()==0||ng.size()==0)continue;
    dp[S]=min(dp[S],max(rec(ok),rec(ng))+1);
  }
  
  return dp[S];
}

int main(){
  while(cin>>m>>n,n){
    dp.clear();
    for(int i=0;i<n;i++)cin>>s[i];
    
    vector<int> S(n);
    for(int i=0;i<n;i++)S[i]=i;
    
    cout<<rec(S)<<endl;
  }
  return 0;
}



Measured memory_bytes: 5284
#include <bits/stdc++.h>
#include <cmath>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP1(i,n) for(int i = 1; i < n+1 ;i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
typedef long long ll;
int main(){
  int K, N;
  cin >> K >> N;
  int i;
  int a[N];
  for(i = 0 ;i < N; i ++) {
    cin >> a[i];
  }
  int b[N];
  int j;
  for (j = 0; j < N; j ++) {
    if (j != N-1) {
      b[j] = a[j + 1] - a[j];
    } else {
      b[j] = K - a[j] + a[0];
    }
  }
  int maxl = b[0];
  for (i = 0; i < N; i++) {
    if (b[i] > maxl){
      maxl = b[i];
    }
  }
  cout << K-maxl << endl;
}

Measured memory_bytes: 1792
//Never stop chasing!-MdSourav.
#include <bits/stdc++.h>

#define yes            cout<<"YES"<<endl
#define no             cout<<"NO"<<endl
#define sz(x)          x.size()
#define ll                    long long int
#define ls             long int
#define start          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test           int t;cin>>t;while(t--)
#define f(i, a, n)     for(int i=a; i<n;i++)
#define gcd(a,b)7           __gcd(a,b)
#define lcd(a,b)       (a*b)/gcd(a,b)
#define pb             push_back
#define mp(x,y)        make_pair(x,y)
#define rsrt(v)        sort(v.begin(),v.end(),greater<int>())
#define srt(v)         sort(v.begin(),v.end())
#define basrt(a,n)     sort(a,a+n,greater<int>())
#define asrt(a,n)      sort(a,a+n)
#define fact(n)        ll x=1;for(ll i=1;i<=n;i++){x=(x*i);}
#define F              first
#define S              second
#define deb(x)         cout << #x << ": " << x << endl;
#define enter(v,n)     for(ll i=0;i<n;i++){ll x;cin>>x;v.pb(x);}
#define INF 	       1000000007
#define unique(v)      v.erase(unique(v.begin(),v.end()),v.end())
using namespace std;

double pi=3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664 ;
typedef vector<ll> vll ;
typedef vector<int> vii ;

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v)
{
    os << '{';
    for (const auto &x : v) os << " " << x;
        return os << '}';
}

void solve()
{

   string s;
   cin>>s;
   string g;
   cin>>g;
   for(int i=0;i<s.size();i++)
   {
   	    if(s[i]!=g[i])
		{
			cout << "No";
			return;
		}

   }
   cout << "Yes";

}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    ll test_case=1;
    //cin>>test_case ;
    while(test_case--)
	{
		 solve();
	}

	return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} // input vector

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

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

i64 N, T; cin >> N >> T;
VI A(N); invec(A);

i64 mini = INF, maxi = 0, cnt = 0;
rep(i, 0, N){
    chmin(mini, A[i]);
    if (chmax(maxi, A[i] - mini)) cnt = 1;
    else if (maxi == A[i] - mini) ++cnt;
}

cout << cnt << "\n";

return 0;
}
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 1024
#include<bits/stdc++.h>
 // #include <ext/pb_ds/tree_policy.hpp>
 // #include <ext/pb_ds/assoc_container.hpp>
 // #include<chrono>
 using namespace std;
 using namespace std::chrono;      
 // using namespace __gnu_pbds; 
 #define fastio     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
 #define fi         first
 #define se         second
#define int         long long 
 #define pb         push_back
 #define emp        emplace_back
 #define vv(x)      vector<x>
 #define mp(x,y)    map<x,y>
 #define dq(x)      deque<x>
 #define pql(x)     priority_queue<x>
 #define pqs(x)     priority_queue<x,vv(x),greater<x> >
 #define mod        1000000007
 #define forf(i,a,b) for(int i=a;i<b;i++)
 #define it(x)      x::iterator
 #define ll         long long 
 #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
 #define time__(d)  for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
 #define vii        vector<int>
 #define big        2e18
 #define sm         -1e9
 #define mkr        make_pair
 #define vpi        vector<pair<int,int> >
 #define pii        pair<int,int>
 #define rng        500005
 #define sz(x)      (int)x.size()
 #define rv(x)      reverse(x.begin(),x.end())
 #define out(x)     cout<<x.fi<<" "<<x.se<<endl;

//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update> 
  
void pr_init()
{
   
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
   
    #endif
}

void solve()
{
 
int n,k;
cin >> n >> k;


n-=(n/k)*k;

cout<<min(n,abs(n-k));


}

int32_t main()
{
  pr_init();
  fastio;
  solve();

 }


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

int main(){
	int N, A, B, C, D;
	cin >> N >> A >> B >> C >> D;
	A--; B--; C--; D--;
	string S;
	cin >> S;
	char now = '.';
	bool p = true;
	for (int i = A; i < C; i++) {
		if (S[i] == '#' && now == '#') p = false;
		now = S[i];
	}
	now = '.';
	for (int i = B; i < D; i++) {
		if (S[i] == '#' && now == '#') p = false;
		now = S[i];
	}

	if (C > D) {
		p = false;
		for (int i = B; i <= D; i++) {
			if (S[i-1]=='.' && S[i]=='.' && S[i+1]=='.') p = true;
		}
	}

	if (p) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3692
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int a[300];
int main(){
	int n;cin>>n;
	int l;cin>>l;
	int sum=0;
	int Min=INT_MAX;
	rep(i,n){
		a[i]=l+i;
		if(abs(Min)>abs(a[i])){
			Min=a[i];
		}
		sum+=a[i];
	}
	cout<<sum-Min<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  double r;
  cin>>r;
  cout<<r*2*3.1415926535<<endl;

  return 0;
}


Measured memory_bytes: 3804
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#define int long long
using namespace std;
int test[213456], uiop[213456];
signed main() {
	int n, a; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> a;
        test[h] = a; uiop[h] = a;
	}
    sort(uiop,uiop + n);
	for (int h = 0; h < n; h++) {
      	if(test[h] <= uiop[n / 2 - 1]){
            cout << uiop[n / 2] << endl;
        }
        else{
        	cout << uiop[n / 2 - 1] <<endl;
     	}
    }
}

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

int main(){
  long long b,ans=0,n,array[200000];
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>array[i];
    array[i]=array[i]-i-1;
  }
  sort(array,array+n);
  if(n%2){
    b=array[n/2];
    for(int i=0;i<n;i++){
      ans+=abs(array[i]-b);
    }
    cout<<ans<<endl;
    return 0;
  }else{
    b=(array[n/2]+array[(n/2)-1])/2;
    for(int i=0;i<n;i++){
      ans+=abs(array[i]-b);
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=2e5,MAX_M=2e5;
int N,M;
map<int,int> mp;
int main(){
	cin>>N;
	REP(i,N){
		int d;
		cin>>d;
		mp[d]++;
	}
	cin>>M;
	REP(i,M){
		int t;
		cin>>t;
		mp[t]--;
	}
	bool ans=true;
	for(auto v:mp){
		if(v.second<0){
			ans=false;
		}
	}
	cout<<(ans ? "YES" : "NO")<<endl;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const LL INF = 2147483647000000LL;
const int N = 1000000;

int lewa[N], prawa[N], M, a[N], b[N], c[N], i, kol[N], n, m, ww;
LL w[N], W[N], l;

bool cmp(int q1, int q2) {
	return a[q1] < a[q2];
}

void insert (int a, int b, LL c, int d=1) {
            if (lewa[d]>b || prawa[d]<a) return;
            if (lewa[d]==a && prawa[d]==b) {
            w[d]=min(w[d],c);
            W[d]=w[d];
            if (d<=M) W[d]=min(W[d],min(W[2*d],W[2*d+1]));
            return;
            }
            insert (a,min(b,prawa[2*d]),c,2*d);
            insert (max(a,lewa[2*d+1]),b,c,2*d+1);
            W[d]=min(w[d],min(W[2*d],W[2*d+1]));
}
 
LL query (int a, int b, int d=1) {
            if (lewa[d]>b || prawa[d]<a) return INF;
            if (lewa[d]==a && prawa[d]==b) return W[d];
            return min(w[d], min(query (a,min(b,prawa[2*d]),2*d), query (max(a,lewa[2*d+1]),b,2*d+1)));
}

void init (int a) {
            int i;
            M=1;
            while (M<a) M*=2;
            for (i=M;i<2*M;i++) {w[i]=W[i]=INF; lewa[i]=prawa[i]=i-M+1;}
            for (i=M-1;i>=1;i--) {w[i]=W[i]=INF; lewa[i]=lewa[2*i]; prawa[i]=prawa[2*i+1];}
            M--;
}



int main() {
scanf("%d %d", &n, &m);
for (i=0;i<m;i++) {
	scanf("%d %d %d", &a[i], &b[i], &c[i]);
	kol[i] = i;
}
sort(kol, kol + m, cmp);
init(n);
insert(1, 1, 0);
for (i=0;i<m;i++) {
	ww = kol[i];
	l = query(a[ww], a[ww]);
	if (l == INF) {
		printf("-1\n");
		return 0;
	}
	insert(a[ww], b[ww], l + c[ww]);
}
l = query(n, n);
if (l == INF) l = -1;
printf("%lld\n", l);
return 0;
}

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

int main(){
	int n, m, c, x;
	cin >> n >> m >> c;
	int a[m], b[m];
	int cnt = 0;

	for(int i=0; i<m; i++){
		cin >> b[i];
	}
	for(int i=0; i<n; i++){
		x = 0;
		for(int j=0; j<m; j++){
			cin >> a[j];
			x += a[j]*b[j];
		}
		x += c;
		if(x>0){
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	long long z=0,i,n,k;
	cin>>n;
	k=n;
	if(n==0){
		cout<<"No"; 
		return 0;
	}
	for(i=1;i>0;i++){
		if(n==0){
			break;
		}
		z+=n%10;
		n/=10;
	}
	if(k%z==0){
		cout<<"Yes";
	}
	else cout<<"No";
}

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

int main(int argc, char const *argv[])
{
	int n,m;
	cin>>n>>m;
	int memo[n+5]={},l,r;
	for (int i = 0; i < m; ++i)
	{
		cin>>l>>r;--l;
		++memo[l];
		--memo[r];
	}
	int ans=0;
	if (memo[0]==m)
	{
		++ans;
	}
	for (int i = 1; i <= n; ++i)
	{
		memo[i]+=memo[i-1];
		if (memo[i]==m)
		{
			++ans;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;
int o, e;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        if (a % 2)
            o++;
        else
            e++;
    }
    e += o / 2;
    o %= 2;
    if (e && o)
        cout << "NO";
    else
        cout << "YES";
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin>>s>>t;
    cout<<t+s<<"\n";
    return 0;
}

Measured memory_bytes: 256
/*
* problem:
* method:
* date:
*/
#include<iostream>
#define LL long long
using namespace std;
int main(){
	LL a,b,res;
	char s[4];
	cin>>a>>s;
	b=(s[0]-'0')*100+(s[2]-'0')*10+(s[3]-'0');
	res=a*b/100;
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>

int main(void){
    char S1[4],S2[4];
    int i;
    scanf("%s",S1);
    scanf("%s",S2);
    for(i=0;i<3;i++){
        if(S1[i]!=S2[2-i]){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

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

int m,n,d[300];
vector<int> g[300],rg[300];
bool vis[300],rvis[300];

void dfs(int p){
  if(vis[p])return;
  vis[p] = true;
  for(int i=0;i<g[p].size();i++)
    if(!vis[g[p][i]])dfs(g[p][i]);
}

void rdfs(int p){
  if(rvis[p])return;
  rvis[p] = true;
  for(int i=0;i<rg[p].size();i++)
    if(!rvis[rg[p][i]])rdfs(rg[p][i]);
}

int main(){
  while(cin >> m,m){
    cin >> n;
    for(int i=1;i<=n;i++)cin >> d[i]; d[0] = d[n+1] = 0;
    for(int i=0;i<=n+1;i++){g[i].clear(); rg[i].clear();}

    for(int i=0;i<=n;i++){
      for(int j=1;j<=m;j++){
	int nxt = min(n+1,i+j);
	nxt = max(0,min(n+1,nxt + d[nxt]));

	g[i].push_back(nxt); rg[nxt].push_back(i);
      }
    }

    for(int i=0;i<=n+1;i++)vis[i] = rvis[i] = false;
    dfs(0); rdfs(n+1);

    bool res = true;
    for(int i=0;i<=n+1;i++){
      if(vis[i] && !rvis[i])res = false;
    }
    cout << (res?"OK":"NG") << endl;
  }
}
      

Measured memory_bytes: 1296
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var ans = 0.0;

        for (int i = 0; i < N; i++)
        {
            var xv = ReadLine().Split(' ');
            var (x, v) = (double.Parse(xv[0]), xv[1]);

            if (v == "JPY")
                ans += x;
            else
                ans += x * 380000.0;
        }

        WriteLine(ans);
    }
}


Measured memory_bytes: 27552
#include <bits/stdc++.h>
using namespace std;
long long modl=1e9+7;
long long sum,ans;
long long a[200005],n;
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=0;i<n;i++)
	{
		sum-=a[i];
		ans+=sum%modl*a[i];
		ans%=modl;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 5144
#include<stdio.h>
int main(){


int a,b,c,d,i,j;

scanf("%d %d %d %d",&a,&b,&c,&d);

i=a*b;
j=c*d;
if(i>j){
    printf("%d\n",i);
}
else{
    printf("%d\n",j);
}


return 0;
}


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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())
#define all(a) (a).begin(), (a).end()

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;


int main(void){

	int n; cin >> n;

	vector<int> a(n);
	REP(i,n) cin >> a[i];

	map<int, int> mp;
	REP(i,n){
		if(a[i] >= 3200) mp[8]++;
		else mp[a[i]/400]++;
	}

	int ans = 0;
	int c = 0;
	for(auto a:mp){
		int idx = a.first;
		int cnt = a.second;
		if(idx < 8) ans++;
		else c += cnt;
	}

	printf("%d %d\n", max(ans, 1), ans+c);

	return 0;

}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int w,h,c,a,s,b;
	scanf("%d %d %d",&w,&h,&c);
	if(w>h){
		b=w;
		s=h;
	}
	else{
		b=h;
		s=w;
	}
	while(b%s>0){
		a=b%s;
		b=s;
		s=a;
	}
	printf("%d\n",w/s*h/s*c);
	return 0;
	}


Measured memory_bytes: 2148
#include<stdio.h>

int main(){
  long long int min,max,x,y,n,sum;
  max=-100000000;
  min=100000000;
  sum=0;
  scanf("%lld",&n);

   for(x=0;x<n;x++){
     scanf("%lld",&y);
     sum = sum+y;
     if(min>y){
       min=y;
     }
     if(max<y){
       max=y;
     }
   }
     printf("%lld %lld %lld\n",min,max,sum);
     return 0;
}



Measured memory_bytes: 2104
N, H, *blades = map(int, open(0).read().split())
cut = max(blades[::2])
throws = sorted(b for b in blades[1::2] if b >= cut)

ans = 0
while throws:
    H -= throws.pop()
    ans += 1
    if H <= 0:
        print(ans)
        exit()

ans += (H + cut - 1) // cut
print(ans)

Measured memory_bytes: 32084
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;

int main() {
    int X;
    scanf("%d", &X);
    int tmp = X / 100;
    X %= 100;
    if (tmp * 5 < X) puts("0");
    else puts("1");
    return 0;
}


Measured memory_bytes: 256