akhauriyash/Code-Regression huggingface dataset:
//重要：「積まなくてもよい」と言い換えても答えは変わらない。積まないを選んだ人が後ろにいけばいいだけなので
//「積む」順番はh + pが小さい順が良い。だからこの順番で並べれば、前の人から「積む」「積まない」を試す感じになる。

#include <iostream>
#include <algorithm>
#include <tuple>
#define int long long
using namespace std;
typedef tuple<int, int, int> T;

int n;
int h[5000], p[5000];
T t[5000];
int dp[5001][5001];

signed main() {
	int i, j;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> h[i] >> p[i];
	for (i = 0; i < n; i++) t[i] = T(h[i] + p[i], h[i], p[i]);
	sort(t, t + n);
	for (i = 0; i < n; i++) { h[i] = get<1>(t[i]); p[i] = get<2>(t[i]); }
	
	for (i = 0; i <= n; i++) for (j = 0; j <= n; j++) dp[i][j] = 1145141919810;
	dp[0][0] = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j <= i; j++) {
			if (h[i] >= dp[i][j]) {
				dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + p[i]);
			}
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
		}
	}
	
	for (j = n; j > 0; j--) { if (dp[n][j] <= 11451419190) break; }
	cout << j << endl;
	return 0;
}

Measured memory_bytes: 195840
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

template<int64_t MOD> struct Mint {
  int64_t v;
  Mint() { v = 0; }
  Mint(int64_t x) { v = x % MOD; if(v < 0)  v += MOD; }

  Mint operator-() { return Mint{-v}; };
  Mint operator+(Mint x) { return Mint(v + x.v); };
  Mint operator-(Mint x) { return Mint(v - x.v); };
  Mint operator*(Mint x) { return Mint(v * x.v); };
  Mint operator/(Mint x) { return Mint(v * pow(x.v, MOD-2).v); };

  Mint& operator+=(Mint x) { return *this = (*this + x); };
  Mint& operator-=(Mint x) { return *this = (*this - x); };
  Mint& operator*=(Mint x) { return *this = (*this * x); };
  Mint& operator/=(Mint x) { return *this = (*this / x); };

  static Mint pow(Mint base, int64_t exp) {
    if(exp == 0)  return Mint(1);
    return pow(base*base, exp/2) * (exp&1 ? base : Mint(1));
  }

  friend ostream& operator<<(ostream& os, Mint x) { return os << x.v; }
};
using mint = Mint<998244353>;

template<typename T> vector<T> tensor(int n, T v){ return vector<T>(n, v); }
template<typename... Ts> auto tensor(int n, Ts... ts) {
  return vector<decltype(tensor(ts...))>(n, tensor(ts...));
}

mint dp[3123][3123];
int main() {
  lint A, B, C, D;
  cin >> A >> B >> C >> D;

  // 初期化
  dp[A][B] = 1;
  for(lint b=B; b<3010; b++) {
    dp[A][b+1] = dp[A][b] * mint(A);
  }
  for(lint a=A; a<3010; a++) {
    dp[a+1][B] = dp[a][B] * mint(B);
  }

  // 更新
  for(lint a=A; a<3010; a++)
  for(lint b=B; b<3010; b++) {
    dp[a+1][b+1]  = dp[a][b+1] * mint(b+1);
    dp[a+1][b+1] += dp[a+1][b] * mint(a+1);
    dp[a+1][b+1] -= dp[a][b] * mint(a*b);
  }

  cout << dp[C][D] << endl;
}

Measured memory_bytes: 79784
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

const int MAXN=2e5+777;
const int inf=2e9;
ll n, t[4*MAXN];

void build(vector<ll> &a, int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = a[tl];
	} else {
		int tm = (tl + tr) / 2;
		build(a, v*2, tl, tm);
		build(a, v*2+1, tm+1, tr);
		t[v] = 0;
	}
}

void update(int v, int tl, int tr, int l, int r, ll add) {
	if (l > r)
		return;
	if (l == tl && r == tr) {
		t[v] += add;
	} else {
		int tm = (tl + tr) / 2;
		update(v*2, tl, tm, l, min(r, tm), add);
		update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
	}
}

ll get(int v, int tl, int tr, int pos) {
	if (tl == tr)
		return t[v];
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		return t[v] + get(v*2, tl, tm, pos);
	else
		return t[v] + get(v*2+1, tm+1, tr, pos);
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll n,d,a; cin>>n>>d>>a;
	set<ii> st;
	map<int,int> idx;
	for (int i=0; i<n; i++) {
		ii p; cin>>p.first>>p.second;
		st.insert(p);
	}
	int iter=0;
	for (auto x : st)
		idx[x.first]=iter++;
	vector<ll> init(n);
	for (int i=0; i<n; i++)
		init[i]=0;
	build(init,1,0,n-1);

	ll ret=0;
	int left=0;
	while(!st.empty()) {
		ii cur=*st.begin();
		ll bomb=get(1,0,n-1,left);
		ll ct=max(0LL,(cur.second-bomb+a-1)/a);
		ret+=ct;
		auto it=st.upper_bound({cur.first+2*d,inf});
		if(it==st.begin())
			continue;
		it--;
		ll right=idx[it->first];
		update(1,0,n-1,left,right,a*ct);
		left++;
		st.erase(st.begin());
	}
	cout<<ret<<endl;
	return 0;
}

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


public class Main{
  
 public static void main(String args[]){
  
   Scanner s = new Scanner(System.in);
   int n  =s.nextInt();
   
   if(n>=30)
     System.out.println("Yes");
   else
     System.out.println("No");
 }
  
}

Measured memory_bytes: 35900
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int arr[3][3];
    for(int i=0;i<3;i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    int n,x;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                if(arr[j][k]==x){
                    arr[j][k]=0;
                }
            }
        }
    }
    if(arr[1][0]+arr[1][1]+arr[1][2]==0 ||arr[0][0]+arr[0][1]+arr[0][2]==0 || arr[2][0]+arr[2][1]+arr[2][2]==0 || arr[0][0]+arr[1][0]+arr[2][0]==0 || arr[0][1]+arr[1][1]+arr[2][1]==0 || arr[0][2]+arr[1][2]+arr[2][2]==0 || arr[0][0]+arr[1][1]+arr[2][2]==0 || arr[0][2]+arr[1][1]+arr[2][0]==0 ){
        cout<< "Yes"<<endl;
    }else{cout<< "No"<<endl;}

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <math.h>
#include <ctype.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <queue>
#include <limits.h>
using namespace std;

typedef long long ll;

const int N = 100, W = 1e5;
int n, can, w[N], v[N];
ll dp[N][W + 1];

ll calc(int at, int can) {
	if (at == n)
		return 0;
	ll &res = dp[at][can];
	if (res != -1)
		return res;
	res = calc(at + 1, can);
	if (w[at] <= can)
		res = max(res, calc(at + 1, can - w[at]) + v[at]);
	return res;
}

int main(int argc, char **argv) {
	scanf("%d%d", &n, &can);
	for (int i = 0; i < n; ++i)
		scanf("%d%d", &w[i], &v[i]);
	memset(dp, -1, sizeof(dp));
	printf("%lld\n", calc(0, can));
	return 0;
}


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

typedef long long ll;

const ll mod = 1e9+7;

ll dp[1005][1005];
char matrix[1005][1005];
int n,m;

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

	cin>>n>>m;
	for(int i=0; i<n; ++i){
		for(int j=0; j<m; ++j){
			cin>>matrix[i][j];
		}
	}
	memset(dp,0,sizeof(dp));
	dp[0][0] = 1;
	for(int i=0; i<n; ++i){
		if( matrix[i][0] == '#' ){ break; }
		else{ dp[i][0] = 1; }
	}
	for(int i=0; i<m; ++i){
		if( matrix[0][i] == '#' ){ break; }
		else{ dp[0][i] = 1; }
	}

	for(int i=1; i<n; ++i){
		for(int j=1; j<m; ++j){
			dp[i][j] = dp[i-1][j] + dp[i][j-1] ;
			if( matrix[i][j] == '#' ){ dp[i][j] = 0; }
			dp[i][j] %= mod;
		}
	}
	cout<<dp[n-1][m-1]<<'\n';
	return 0;
}


Measured memory_bytes: 9088
#include<iostream>
#include<vector>
#include<bitset>
#include<string>
#include<cmath>
#include<algorithm>
#include<stack>
#include<list>
#include<queue>
#include<map>
using namespace std;

int INF=1e9;
int main(){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
      int b,e,k,ans=0;;
      cin>>b>>e>>k;
      for(int i=b;i<e;i++){
        if(a[i]==k){
          ans++;
        }
      }
      cout<<ans<<endl;
    }
    return 0;
}


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

int a(char x){
	switch (x) {
		case 'I': return 1;
		case 'V': return 5;
		case 'X': return 10;
		case 'L': return 50;
		case 'C': return 100;
		case 'D': return 500;
		case 'M': return 1000;
	}
	return 0;
}
int main(void){
	string str;
	int ans=0;
	int p=0;
	while(cin>>str){
		ans=0;
		p=0;
		for(int i=str.length()-1;i>=0;i--){
			int now=a(str[i]);
			if(p>now)ans-=now;
			else ans+=now;
			p=now;
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3172
import sys
import math


# get from std-I/O.
def loading_inputs():

    data = {"N":0, "S":list()}
    N = raw_input()
    N = int(N)

    P = list()
    for i in xrange(N):
        p_i = raw_input()
        p_i = int(p_i)
        P.append(p_i)

    data["N"] = N
    data["P"] = P

    return data


def calc_payment(max_p, p_remain):

    total = 0

    max_pay = math.ceil(max_p/2)
    remain_pays = sum(p_remain)
    total = int(max_pay + remain_pays)
    return total



def main():

    ans  = 0
    inputs = loading_inputs()
    P = sorted(inputs["P"])
    N = inputs["N"]

    max_p    = P[N-1]
    remain_p = P[:N-1]
    ans = calc_payment(max_p, remain_p)
    print ans



if __name__ == "__main__":
    main()

Measured memory_bytes: 2696
#include <iostream>
#include <string>
int main()
{
	int res;
	std::string a, b;
	std::cin >> a >> b;
	res = 0;
	for (int i = 0; i < a.length(); i++)
		if (a[i] != b[i])
			res++;
	std::cout << res;
	return 0;
}

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


public class Main {

	boolean[] sieve;
	final int MAX=10000000;
	Scanner sc;
	
	void makeSieve(){
		sieve=new boolean[MAX];
		Arrays.fill(sieve, true);
		sieve[0]=false;
		for(int i=2;i<=MAX;++i){
			if(sieve[i-1]){
				for(int j=i*2;j<=MAX;j+=i){
					sieve[j-1]=false;
				}
			}
		}
	}
	
	int solve(int n){
		int i;
		for(i=n;!(sieve[i-1]&&sieve[i-3]&&sieve[i-7]&&sieve[i-9]);--i);
		return i;
	}
	
	int ni(){
		return sc.nextInt();
	}
	
	void io(){
		makeSieve();
		sc=new Scanner(System.in);
		int n;
		while((n=ni())!=0) System.out.println(solve(n));
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().io();
	}

}

Measured memory_bytes: 34596
//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 100005

typedef long long ll;

const ll mod = 1e9 + 7;
const double PI = acos(-1);

using namespace std;

int N, M, K;

ll d[MAXN];
ll f[MAXN];

bool cmp(ll a, ll b){
	return a > b;
}

int main(void)
{
#ifdef Sunshine
	freopen("data.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll N, M;
	cin >> N >> M;
	for(int i = 1; i <= N; i++)
		cin >> d[i];
		
	sort(d + 1, d + 1 + N);
	for(int i = 1; i <= N; i++){
		f[i] = f[i - 1] + d[i];
	}
	
	ll cnt, res, l, r, ans;
	l = 0;
	r = 2e5;
	
	while(l <= r){
		int mid = (l + r) >> 1;
		cnt = res = 0;
		for(int i = 1; i <= N; i++){
			int pos = lower_bound(d + 1, d + 1 + N, mid - d[i]) - d;
			res += f[N] - f[pos - 1] + d[i] * (N - pos + 1);
			cnt += N - pos + 1;
			
		}
		if(cnt >= M){
			l = mid + 1;
			ans = mid;
		}
		else
			r = mid - 1;
	}
	
	cout << res - (cnt - M) * ans << '\n';
	




	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
//debug
#ifdef grief
#define debug(...) do{\
	fprintf(stderr , "%s - %d : (%s) = " , __PRETTY_FUNCTION__ , __LINE__ , #__VA_ARGS__ );\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> 				void _DO(I&&x){	cerr<<x<<endl;	}
template<typename I,typename...T>	void _DO(I&&x,T&&...tail){	cerr<<x<<" , ";	_DO(tail...);	}
template<typename _a,typename _b> 	ostream& operator << (ostream &_s,const pair<_a,_b> &_p)
{	return _s<<'('<<_p.first<<','<<_p.second<<')';	}
#define IOS
#else
#define debug(...)
#define IOS do{ios_base::sync_with_stdio(0); cin.tie(0);}while(0);
#endif
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
//macro
#define SZ(x) ((ll)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define stp setprecision(30)<<fixed
const ll INF=0x3f3f3f3f3f3f3f3f;
const int NF=0x3f3f3f3f;
const ll MAX=1e5+5,Mlg=__lg(MAX)+2;
const ll MOD=1e9+7;
//}}}
int n;
bool iss[MAX];
vector<int> adj[MAX];
int qd[MAX];
vector<int> an1,an2;
void dfs1(int u,int v,int p){
	int now=p;
	for(int i:adj[u]){
		if(iss[i]){
			an1.eb(++p);
		}
	}
	an1.eb(now);
	for(int i:adj[u]){
		if(!iss[i]&&i!=v){
			dfs1(i,u,p+1);
		}
	}
}
void dfs2(int u,int v,int p){
	int now=p;
	for(int i:adj[u]){
		if(iss[i]){
			an2.eb(++p);
		}
	}
	an2.eb(now);
	for(int i:adj[u]){
		if(!iss[i]&&i!=v){
			dfs2(i,u,p+1);
		}
	}
}
void T(){
	for(int i=0;i<n;i++){
		if(an1[i]!=an2[i]){
			if(an1[i]>an2[i])	an1.swap(an2);
			return;
		}
	}
	return;
}
int main(){
	IOS
	cin>>n;
	if(n<=3){
		for(int i=1;i<=n;i++){
			cout<<i;
			if(i==n)	cout<< '\n';
			else		cout<< ' ';
		}
		return 0;
	}
	for(int i=1;i<n;i++){
		int u,v;	cin>>u>>v;
		adj[u].eb(v);
		adj[v].eb(u);
	}
	int cnt=n;
	for(int i=1;i<=n;i++){
		if(SZ(adj[i])==1){
			iss[i]=1;
			cnt--;
		}
	}
	if(cnt==1){
		cout<<1;
		for(int i=3;i<=n-1;i++)	cout<<' '<<i;
		cout<< ' '<<2<< ' '<<n<< '\n';
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j:adj[i])
			if(!iss[j])
				qd[i]++;
		if(qd[i]>2){
			cout<<"-1\n";
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		debug(i,iss[i]);
	}
	vector<int> v;
	for(int i=1;i<=n;i++){
		if(!iss[i]&&qd[i]==1)	v.eb(i);
	}
	assert(SZ(v)==2);
	for(int j=0;j<2;j++){
		for(int i:adj[v[j]]){
			if(iss[i]){
				v[j]=i;
				break;
			}
		}
		assert(iss[v[j]]);
		iss[v[j]]=0;
	}
	debug(v[0]);
	for(int i=1;i<=n;i++){
		debug(i,iss[i]);
	}
	dfs1(v[0],v[0],1);
	dfs2(v[1],v[1],1);
	T();
	for(int i=0;i<n;i++){
		if(i)	cout<< ' ';
		cout<<an1[i];
	}
	cout<< '\n';
	return 0;
}

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

int main() {
    int N, T; cin >> N >> T;
    vector<int> t(N);
    rep(i, N){
        cin >> t[i];
    }

    int ans = t[N-1] + T;
    for (int i = 1; i < N; i++){
        int d = t[i] - t[i-1];
        if(d > T){
            ans -= d-T;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4020
#include <cstdio>
#include <set>
#include <algorithm>

typedef long long i64;

const int N = 100000 + 10;
const i64 INF = 1LL << 60;

int n, t, e, x[N];
i64 f[N];

int main() {
  scanf("%d%d%d", &n, &e, &t);
  for (int i = 1; i <= n; ++i) scanf("%d", &x[i]);
  std::multiset<i64> a, b;
  for (int i = 1, j = 1; i <= n; ++i) {
    b.insert(f[i - 1]);
    for (; 2 * (x[i] - x[j]) > t; ++j) {
      b.erase(b.find(f[j - 1]));
      a.insert(f[j - 1] - 2 * x[j]);
    }
    f[i] = INF;
    if (!a.empty()) f[i] = 2 * x[i] + *a.begin();
    if (!b.empty()) f[i] = std::min(f[i], *b.begin() + t);
  }
  printf("%lld\n", f[n] + e);
  return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Sep 13 21:06:22 JST 2020
 **/

signed main() {
    Int x;
    std::cin >> x;
    std::cout << !x << std::endl;
}


Measured memory_bytes: 3596
n,m = $stdin.gets.split.map(&:to_i)
bridges =[]
ary = []
benri = []
result = []
c = n*(n-1)/2
m.times do |i|
  bridges[i] = $stdin.gets.split.map(&:to_i)
end

(1..n).each do |i|
  ary[i] = {depth: 1, value: i}
  benri[i] = 1
end

def get_root(i,t)
  while i != t[i][:value]
    i = t[i][:value]
  end
  i
end

(0..m-1).reverse_each do |i|
  root_a, root_b = bridges[i].map{|a| get_root(a,ary)}

  if root_a != root_b
    result.push(benri[root_a] * benri[root_b])
    
    if ary[root_a][:depth] < ary[root_b][:depth]
      ary[root_a][:value] = ary[root_b][:value]
      benri[root_b] += benri[root_a]
    elsif ary[root_a][:depth] > ary[root_b][:depth]
      ary[root_b][:value] = ary[root_a][:value]
      benri[root_a] += benri[root_b]
    else
      ary[root_a][:value] = ary[root_b][:value]
      benri[root_b] += benri[root_a]
      ary[root_b][:depth] += 1
    end
  else
    result.push(0)  
  end 
end

sum = 0
(0..m-1).reverse_each do |i|
  sum += result [i]
  puts sum
end

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

int main()
{
  string s;
  cin >> s;
  
  char c = 'C', f = 'F';
  string ans;
  for(int i = 0; i < s.size(); i++)
  {
    if((c == s.at(i)) || (f == s.at(i)))
      ans.push_back(s.at(i));
  }
  
  if(ans.find("CF") != string::npos)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
import sys
import math
import bisect
from sys import stdin,stdout
from math import gcd,floor,sqrt,log
from collections import defaultdict as dd
from bisect import bisect_left as bl,bisect_right as br

sys.setrecursionlimit(100000000)

ii     =lambda: int(input())
si     =lambda: input()
jn     =lambda x,l: x.join(map(str,l))
sl     =lambda: list(map(str,input().strip()))
mi     =lambda: map(int,input().split())
mif    =lambda: map(float,input().split())
lii    =lambda: list(map(int,input().split()))

ceil   =lambda x: int(x) if(x==int(x)) else int(x)+1
ceildiv=lambda x,d: x//d if(x%d==0) else x//d+1

flush  =lambda: stdout.flush()
stdstr =lambda: stdin.readline()
stdint =lambda: int(stdin.readline())
stdpr  =lambda x: stdout.write(str(x))

mod=1000000007


#main code
def findProductSum(A, n): 
    array_sum = 0
    for i in range(0, n, 1): 
        array_sum = array_sum + A[i] 
    array_sum_square = array_sum * array_sum 
    individual_square_sum = 0
    for i in range(0, n, 1): 
        individual_square_sum += A[i] * A[i] 
    return (array_sum_square - 
            individual_square_sum)//2
n=ii()
arr=lii()
print(findProductSum(arr,n)%mod)

Measured memory_bytes: 32412
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
int main(){
    ll N, M;
    cin >> N >> M;
    ll day = 0;
    for(int i = 0; i < M; i++){
        ll a;
        cin >> a;
        day += a;
    }
    if(N - day >= 0){
        cout << N - day << endl;
    }
    else{
        cout << -1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
using namespace std;

bool judge(int n){
    if(n<=1){return false;}
    for(int i=2;i*i<=n;i++){
        if(n%i==0){return false;}
    }
    return true;
}


int main(){
    int n,a;
    cin>>n;
    int count=0;
    for(int i=0;i<n;i++){
        cin>>a;
        if(judge(a)){count++;}
    }
    

    cout<<count<<endl;
    
    return 0;
}



Measured memory_bytes: 3096
main :: IO ()
main = putStrLn . init . unlines . map (\(x, y) -> (showMultiplication x y)) $ table
  where
    table = concat [[(x, y) | y <- [1..9]] | x <- [1..9]]
    showMultiplication x y = (show x) ++ "x" ++ (show y) ++ "=" ++ (show (x * y))



Measured memory_bytes: 3548
#include <iostream>
//#include <iomanip>
#include <string>
#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
//string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll n ; cin >> n ;
	vll cnt(26,0) ;
	for(int i=0;i<n;i++){
		char c ; cin >> c ;
		cnt.at(c-'a')++ ;
	}
	ll ans = 1 ;
	for(int i=0;i<26;i++){
		ans *= cnt.at(i)+1 ;
		ans %= mod ;
	}
	cout << ans-1 << endl ;
}


Measured memory_bytes: 256
# include <stdio.h>

int main(){
    int N = 0;
    scanf("%d", &N);
    int a[N];
    for(int i=0; i<N; ++i){
        scanf("%d", &a[i]);
    }
    // selection sort
    int swap = 0;
    for(int i=0; i<N-1; ++i){
        int min = i;
        for(int j=i+1; j<N; ++j){
            if(a[j] < a[min]){
                min = j;
            }
        }
        if(i != min){
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
            swap++;
        }
    }
    for(int i=0; i<N-1; ++i){
        printf("%d ", a[i]);
    }
    printf("%d\n", a[N-1]);
    printf("%d\n", swap);
}



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

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int ans = 0;
	for (int i = 0;i <= 100;i++) {
		bool A = a < i&&i <= b, B = c < i&&i <= d;
		if (A&&B)ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Scanner input = new Scanner(System.in);
      	int N = input.nextInt();
      	int M = input.nextInt();
      	Map<Integer, int[]> sorted = new TreeMap<Integer, int[]>();
      
      
      	for (int i = 0; i < M; i++) {
          	int P = input.nextInt();
          	int Y = input.nextInt();
          	int[] arr = new int[2];
          	arr[0] = P;
          	arr[1] = i;
          	sorted.put(Y, arr);
        }
      	
      	String[] ans = new String[M];
      	int[] city = new int[N];
      	for (int[] arr : sorted.values()) {
        	ans[arr[1]] = String.format("%06d%06d", arr[0], ++city[arr[0]-1]);
        }
      	for (int i = 0; i < M; i++) {
			System.out.println(ans[i]);
        }
    } 	
}


Measured memory_bytes: 159468
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N=100;
int dis[100][100];
bool dot[100][100];
vector<int> v1;
queue<int> q1;
int main(){
	int n,m;
	int i,j,k,t;
	int a,b,c,d;
	int s=0;
	char ca[100];
	memset(dis,-1,sizeof(dis));
	cin>>n>>m;
	for(i=0;i<n;i++){
		cin>>ca;
		for(j=0;j<m;j++){
			if(ca[j]=='.')dot[i][j]=true,s++;
		}
	}
	q1.push(0);
	for(t=0;!q1.empty();t++){
		d=q1.size();
		for(i=0;i<d;i++){
			a=q1.front(),q1.pop();
			b=a%N,a/=N;
			if(!dot[a][b] || dis[a][b]!=-1)continue;
			dis[a][b]=t;
			for(j=-1;j<=1;j++){
				for(k=-1;k<=1;k++){
					if((j+k+4)%2==0)continue;
					if(a+j<0 || n<=a+j || b+k<0 || m<=b+k)continue;
					if(dis[a+j][b+k]!=-1 || !dot[a+j][b+k])continue;
					q1.push((a+j)*N+b+k);
				}
			}
		}
	}
	if(dis[n-1][m-1]!=-1){
		s-=dis[n-1][m-1]+1;
	}else s=-1;
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;


    void calc()
    {
        cin = new Scanner();
        int[] ABT = cin.ArrayInt(3,0);
        int ans=(ABT[2]/ABT[0])*ABT[1];
        Console.WriteLine(ans);
        
    }


}



class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }


    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}


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

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T>
vector<vector<T> > make_v(size_t a,size_t b){
  return vector<vector<T> >(a,make_v<T>(b));
}
template<typename T>
vector<vector<vector<T> > > make_v(size_t a,size_t b,size_t c){
  return vector<vector<vector<T> > > (a,make_v<T>(b,c));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//INSERT ABOVE HERE
signed main(){
  Int n,m,s;
  while(cin>>n>>m>>s,n){
    const Int MOD=100000;
    int v=n*n;
    m-=v;
    s-=v*(v+1)/2;
    
    auto dp=make_v<int>(s+1,m+1);
    fill_v(dp,0);
    dp[0][0]=1;
    
    for(int i=0;i<v;i++){
      int c=v-i;
      auto nx=make_v<int>(s+1,m+1);
      fill_v(nx,0);
      for(int j=0;j<=s;j++){
	for(int k=0;k<=m;k++){
	  nx[j][k]+=dp[j][k];
	  nx[j][k]%=MOD;
	  if(j+c<=s&&k+1<=m){
	    dp[j+c][k+1]+=dp[j][k];
	    dp[j+c][k+1]%=MOD;
	  }
	}
      }
      swap(dp,nx);
    }
    
    int ans=0;
    for(int i=0;i<=m;i++){
      ans+=dp[s][i];
      ans%=MOD;
    }
    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 30132
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll dp[405][405];
ll solve(int i,int j,ll arr[]){
    if(j<=i)
        return 0;

    if(dp[i][j]!=-1)
        return dp[i][j];


    ll ans = 1e14;
    ll S =0;
    for(int k=i;k<=j;k++)
        S+=arr[k];

    for(int k=i;k<j;k++){

        // i to k, k+1 to j
        ans = min(ans,solve(i,k,arr)+solve(k+1,j,arr)+S);
    }

    return dp[i][j] = ans;
}
int main()
{
    int n;
    cin>>n;
    memset(dp,-1,sizeof dp);
    ll arr[n];

    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<solve(0,n-1,arr);
    return 0;
}

Measured memory_bytes: 4876
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c,d;
    cin>>a>>b>>c>>d;
    long long x=a*c;
    long long y=b*d;
    long long x1=a*d;
    long long y1=b*c;
    cout<<max(max(max(x,y),x1),y1)<<endl;
}


Measured memory_bytes: 3632
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

a, b, c, x, y = read_line(int, int, int, int, int)

if a + b < 2 * c:
    print(x * a + y * b)
else:
    z = min(x, y)
    count = z * (c * 2)
    if x == z:
        count += (y - z) * min(b, c * 2)
    else:
        count += (x - z) * min(a, c * 2)
    print(count)
            
        



Measured memory_bytes: 38492
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define PI 3.1415926535

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll divc, divd, divcd;
    divc = b / c - (a - 1) / c;
    divd = b / d - (a - 1) / d;
    divcd = b / (c * d / __gcd(c , d)) - (a - 1) / (c * d / __gcd(c , d));
    ll ans = b - a + 1;
    ans -= divc + divd - divcd;
    cout << ans << endl;
}


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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 1000013;

int N;
int arr[MAXN];
int twos[MAXN];
int ans;

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    string str; cin >> str;
    bool even = true;
    FOR(i, 0, N)
    {
        arr[i] = (str[i] - '1');
        if (arr[i] == 1)
        {
            even = false;
        }
    }
    twos[0] = 0;
    FOR(i, 1, N + 1)
    {
        twos[i] = twos[i - 1] + __builtin_ctz(i);
        // cerr << "tows " << i << " = " << twos[i] << endl;
    }
    if (even)
    {
        FOR(i, 0, N)
        {
            arr[i] >>= 1;
        }
    }
    //2022
    //220
    //02
    //2
    FOR(i, 0, N)
    {
        if (twos[N - 1] - twos[i] - twos[N - 1 - i] == 0 && arr[i] == 1)
        {
            ans ^= 1;
        }
    }
    //find it mod 2.
    if (even)
    {
        ans <<= 1;
    }
    cout << ans << '\n';
    return 0;
    //we need N choose everything mod 2.
    //if everything is even, solve and then divide by 2.
}


Measured memory_bytes: 9116
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][][] info = new int[4][3][10]; 
        for(int i=0;i<n;i++){
            int b= sc.nextInt();
            int f = sc.nextInt();
            int r= sc.nextInt();
            int v= sc.nextInt();
            info[b-1][f-1][r-1]+=v;
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<3;j++){
                for(int m=0;m<10;m++){
                    System.out.printf(" %d",info[i][j][m]);
                }
                System.out.println();
            }
            if(i!=3){
                System.out.printf("####################\n");
            }
        }
        sc.close();
    }
}


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

const int N = 60;
const int inf = INT_MAX;

#define ll long long
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define _FOR(i,a,b) for(int i = a;i >= b;i--)

template<typename T> void read(T &x)
{
  x = 0;int f = 1;
  char c = getchar();
  for(;!isdigit(c);c = getchar()) if(c == '-') f = -1;
  for(;isdigit(c);c = getchar()) x = x * 10 + c - '0';
  x *= f;
}

ll n,a[N];
int main()
{
  //freopen(".in","r",stdin);
  //freopen(".out","w",stdout);
  read(n);
  FOR(i,1,n)
    read(a[i]);
  sort(a + 1,a + 1 + n);
  double haha = 1.0 * a[1];
  FOR(i,2,n)
    haha = (haha + 1.0 * a[i]) / 2.0;
  printf("%f",haha);
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const int Inf = 1000000000;
const ll INF= 1e18;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> B(N);
    for(int i = 0;i < N;i++) {
        cin >> A.at(i);
    }
    for(int i = 0;i < N;i++) {
        cin >> B.at(i);
    }
    vector<ll> cnt(N);
    for(int i = 0;i < N;i++) {
        cnt.at(i) = A.at(i) - B.at(i);
    }
    int ret = 0;
    sort(cnt.begin(),cnt.end());
    ll cnt2 = 0;
    for(int i = 0;i < N;i++) {
        if(cnt.at(i) < 0) {
            cnt2 += abs(cnt.at(i));
        }
        else {
            break;
        }
        ret++;
    }
    bool res = true;
    reverse(cnt.begin(),cnt.end());
    for(int i = 0;i < N;i++) {
        if(cnt.at(i) <= 0) {
            res = false;
            break;
        }
        else if(cnt2 <= 0) {
            break;
        }
        else {
            ret++;
            cnt2 -= cnt.at(i);
            if(cnt2 <= 0) {
                break;
            }
        }
    }
    if(res == false) {
        cout << -1 << endl;
    }
    else {
        cout << ret << endl;
    }
}

Measured memory_bytes: 2560
#include <stdio.h>

int main(void)
{
	int i, n;
	long long int a[100005], b, ans = 0;

	scanf("%d", &n);
	for (i=1; i <= n+1; i++)
		scanf("%lld", &a[i]);

	for (i = 1; i <= n; i++) {
		scanf("%lld", &b);
		if (b > a[i]) {
			ans += a[i];
			b -= a[i];
			if (b > a[i + 1]) {
				ans += a[i + 1];
				a[i + 1] = 0;
			}
			else {
				ans += b;
				a[i + 1] -= b;
			}
		}
		else ans += b;
	}

	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 896
#include<iostream>
using namespace std;
 
static const int MAX = 1000000;

int main() {
    static bool is_prime[MAX] = { false };
    static int npr[MAX];
    for (int i = 2; i<MAX; i++) {
        if (!is_prime[i]) {
            for (int j = 2; j*i<MAX; j++) {
                is_prime[i*j] = true;
            }
        }
        npr[i] = npr[i - 1] + !is_prime[i];
    }
    int n;
    while (cin >> n) {
        cout << npr[n] << endl;
    }
    return 0;
}

Measured memory_bytes: 7912
#include <bits/stdc++.h> 
#include <cstring>
using namespace std;
//typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
//define
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int main(){
    int n;
    cin >> n;
    cout << n*n*n << endl;  

 return 0;
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

// Get lines from standard input.
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
var number_of_hills_to_output = 3;

// Sort numerically greatest first.
lines.sort(function(a, b) {
  return b - a;
});

// Print the output
for (var counter = 0; counter < number_of_hills_to_output; counter++){
console.log(lines[counter]);
}

Measured memory_bytes: 15544
x = int(input())
ans = 0
if x <= 3:
    i = x
else:
    for i in range(x,2*x):
        s = 0
        for j in range(2,int(pow(i,0.5))+1):
            if i%j == 0:
                s = 1
                break
        if s == 0:
            break
print(i)

Measured memory_bytes: 2940
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        String str = sc.next();
        
        String str1 = str.substring(0,num2 - 1);
        String str2 = str.substring(num2 - 1, num2);
        String str3 = str.substring(num2);

        System.out.println(str1 + str2.toLowerCase() + str3);
    }
}

Measured memory_bytes: 21712
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define range(i,a,n) for(ll i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x,y,a,b,c;
	cin>>x>>y>>a>>b>>c;
	vector<pll> v(a+b+c);
	rep(i,a)cin>>v[i].fs,v[i].sc=0;
	rep(i,b)cin>>v[i+a].fs,v[i+a].sc=1;
	rep(i,c)cin>>v[i+a+b].fs,v[i+a+b].sc=2;
	sort(all(v),[](auto a,auto b){
		return(a.fs>b.fs);
	});
	ll ans=0,tmp=0;
	rep(i,a+b+c){
		if(v[i].sc==0&&x>0&&x+y>tmp){
			ans+=v[i].fs;
			x--;
		}
		if(v[i].sc==1&&y>0&&x+y>tmp){
			ans+=v[i].fs;
			y--;
		}
		if(v[i].sc==2&&x+y>tmp){
			ans+=v[i].fs;
			tmp++;
		}
	}
	puta(ans);
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define UB upper_bound
#define LB lower_bound
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define be(a) (a).begin(),(a).end()
#define deb(x) cout<< #x <<" "<<endl;
#define deb2(x, y) cout<< #x <<" "<< x <<endl<< #y <<" "<<y<<endl
#define fo(i, n) for(long long i=0; i<n; i++)
#define Fo(i, n, k) for(long long i=k; i<n; i++)
#define mod 1000000007
#define int long long

typedef long long ll;

void fileIO()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
 
typedef vector<pair<int, int>> vll;
typedef unordered_map<int, int> ump;



bool sortbysecdesc(const pair<int, int> &a, 
                    const pair<int, int> &b) 
{ 
    return a.second>b.second;
}



int32_t main()
{
    IOS;
    fileIO();
    int T;
    T = 1;
    //cin>>T;

    while(T--)
    {
        int h, w;
        cin>>h>>w;
        vector<string>grid;

        for(int i = 0; i<h; i++)
        {
            string input;
            cin>>input;
            grid.push_back(input);
        }

        vector<vector<int>> dp;
        for(int i = 0; i<h; i++)
        {
            vector<int> temp;
            for(int j = 0; j<w; j++)
            {
                temp.push_back(0);
            }

            dp.push_back(temp);
        }

        
        dp[0][0] = 0;
        for(int i = 1; i<h; i++)
        {
            if(grid[i][0] != '#')dp[i][0] = 1;
            else break;
        }

        for(int i = 1; i<w; i++)
        {
            if(grid[0][i] != '#')dp[0][i] = 1;
            else break;
        }

        for(int i = 1; i<h; i++)
        {
            for(int j = 1; j<w; j++)
            {
                if(grid[i][j] != '#')
                {
                    dp[i][j] = ((dp[i][j-1]%mod) + (dp[i-1][j]%mod))%mod;
                }
            }
        }


        cout<<dp[h-1][w-1];




    }
    
    return 0;
}



Measured memory_bytes: 12124
import sys
import math
import collections
import bisect
import itertools

import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    n = ni()
    a = na()
    b = a.copy()

    a_cnt = 0
    a_sum = 0
    b_cnt = 0
    b_sum = 0

    for i in range(n):
        tmp = a_sum + a[i]
        if i % 2:
            if tmp <= 0:
                a_cnt += 1 + abs(tmp)
                a_sum = 1
            else:
                a_sum += a[i]
        else:
            if tmp >= 0:
                a_cnt += 1 + abs(tmp)
                a_sum = -1
            else:
                a_sum += a[i]

    for i in range(n):
        tmp = b_sum + b[i]
        if not i % 2:
            if tmp <= 0:
                b_cnt += 1 + abs(tmp)
                b_sum = 1
            else:
                b_sum += b[i]
        else:
            if tmp >= 0:
                b_cnt += 1 + abs(tmp)
                b_sum = -1
            else:
                b_sum += b[i]

    print(min(a_cnt, b_cnt))


if __name__ == '__main__':
    main()


Measured memory_bytes: 38156
#include<iostream>
#include<algorithm>
#include<cmath>

using sll = signed long long;

int main(){

	sll N, K;
	std::cin >> N >> K;

	const sll r{ N%K };

	std::cout << 
		std::min( r, std::abs( r - K ) ) 
		<< "\n";

	return 0;
}

Measured memory_bytes: 3136
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0;bool f=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?x:-x;
}
int n,k,s;
int main()
{
    n=read(),k=read(),s=read();
    for(int i=0;i<k;i++) printf("%d ",s);
    if(s!=1e9)
        for(int i=k;i<n;i++) printf("1000000000 ");
    else
        for(int i=k;i<n;i++) printf("1 ");
    puts("");
    return 0;
}


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

using namespace std;
#define ull unsigned long long
#define ll long long
#define ii pair<ll, ll>
#define x first
#define y second

ll n, k, a ,b;
vector<ii> v;

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a >> b;
        v.push_back(ii(a, b));
    }
    ull ans = 1e19;
    sort(v.begin(), v.end());
    for (int i = 0; i + k - 1 < n; i++){
        for (int j = i + k - 1; j < n; j++){
            vector<ll> q;
            for (int t = i; t <= j; t++) q.push_back(v[t].y);
            sort(q.begin(), q.end());
            for (int t = 0; t <= j - i - k + 1; t++)
            ans = min(ans, (ull)(q[t + k - 1] - q[t])*abs(v[i].x-v[j].x));
        }
    }
    cout << ans;
}


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

// macros
#define int long long 
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define PB push_back
#define MP make_pair
#define bitcount __builtin_popcount
#define watch(x) cerr<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)

// type definitions
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > vvi;
typedef pair<int, int> pii;
typedef long double ld;

// template functions
template < typename A, typename B >
ostream &operator << ( ostream& os, const pair< A, B > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "[";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "{";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}
template < typename A, typename B >
ostream &operator << ( ostream & os, const map< A, B > &v ) {
    os << "[";
    typename map< A, B >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " -> " << it -> second ;
    }
    return os << "]";
}
template<typename T>
T gcd(T a, T b) { if(a==0 or b==0) return a+b; return gcd(b, a%b) ; }
template<typename T>
T lcm(T a, T b) { if(a==0 or b==0) return 0; return a/gcd(a, b)*b; }

// random number generation
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// constants
const long double eps = LDBL_EPSILON;
const int inf = 1e15;
const int modn = 1e9+7;
const int maxn = 2e5+3;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your code here
    string s;
    cin>>s;
    if(s[2]==s[3] and s[4]==s[5]) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }
    return 0;
}



Measured memory_bytes: 256
str = gets.chomp

result = "Yes"
i = 1
str.each_char do |s|
  result = "No" unless (i%2==1 && (s=="R" || s=="U" || s=="D")) || (i%2==0 &&(s=="L"||s=="U"||s=="D"))
  i+=1
end

puts result

Measured memory_bytes: 3836
import math

n=tuple(map(int,input().split()))

A=n[0]
B=n[1]
H=n[2]
M=n[3]

A_rad=H*math.pi/6+M*math.pi/360
B_rad=M*math.pi/30


A_pos=[A*math.cos(A_rad),A*math.sin(A_rad)]
B_pos=[B*math.cos(B_rad),B*math.sin(B_rad)]

print(math.sqrt((A_pos[0]-B_pos[0])**2+(A_pos[1]-B_pos[1])**2))


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

int main(){
	int l[10], v1, v2;
	string str;
	int p;
	int sum, part;
	double time1, dist2;
	
	while(getline(cin, str)){
		for(int i = 0; i < 10; i++) l[i] = 0;
		v1 = 0; v2 = 0;
		
		p = 0;
		for(int i = 0; i < 10; i++){
			while(str[p] != ','){
				l[i] = l[i] * 10 + (str[p] - 48);
				p++;
			}
			p++;
		}
		while(str[p] != ','){
			v1 = v1 * 10 + (str[p] - 48);
			p++;
		}
		p++;
		while(p < str.size()){
			v2 = v2 * 10 + (str[p] - 48);
			p++;
		}
		
		sum = 0;
		for(int i = 0; i < 10; i++) sum += l[i];
		
		part = 0;
		for(int i = 0; i < 10; i++){
			part += l[i];
			
			time1 = (double)part / v1;
			dist2 = time1 * v2;
			
			if(part + dist2 >= sum){
				cout << i + 1 << endl;
				break;
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 1172
#include<stdio.h>
int main(void)
{
        int n,a[10000],i,s=0;
        scanf("%d",&n);
        for(i=0;i<n;i++){
                scanf("%d",&a[i]);
                while(a[i]%2==0){
                        s++;
                        a[i]=a[i]/2;
                }

        }
        printf("%d\n",s);
        return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if(a + b == c) cout << "Yes" << endl;
  else if(a + c == b) cout << "Yes" << endl;
  else if(b + c == a) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>

using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};


int main(){
    int a[5];
    for(int i=0;i<5;i++){
        cin >> a[i];
    }
    int k;
    cin >> k;
    bool f=true;
    if(a[4]-a[0]<=k) f=false;
    if(!f) cout << "Yay!" << endl;
    else  cout << ":(" << endl;
    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=[int(i) for i in input().split()]
from collections import defaultdict
d=defaultdict(int)
for i in a:
    d[i]+=1
a=sorted(list(d.items()),key=lambda x:x[0])
p=0
ans=0
#print(a)
while a:
    c=a.pop()
    if c[1]<2:
        continue
    if c[1]>=4:
        ans=max(c[0]**2,ans)
        p=max(p,c[0])
    if c[1]>=2:
        if p==0:
            p=max(c[0],p)
        else:
            ans=max(p*c[0],ans)
            
print(ans)

Measured memory_bytes: 73880
var toInt = x=>parseInt(x,10);
var toIntArr = arr=>arr.map(x=>toInt(x));
var abs = x=>x>0?x:-x;
function min(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]<val)val = rest[i];return val}
function max(){var rest = arguments,val=rest[0];for(var i=1;i<rest.length;i++)if(rest[i]>val)val = rest[i];return val}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
 
function Main(input){
	var input = input.split(' ');
	var n = toInt(input[0]);
	var k = toInt(input[1]);
	var ans = (n%k===0)? 0:1;

	console.log(ans);

}

Measured memory_bytes: 14924