akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        int hitPoint = sc.nextInt();
        int skillNum = sc.nextInt();
        int[] powers = new int[skillNum];
        int totalDamage = 0;
        
        for (int i = 0; i < skillNum; i++) {
            powers[i] = sc.nextInt();
            totalDamage += powers[i];
        }     
        
        if (totalDamage >= hitPoint) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
        
    }
}
        

Measured memory_bytes: 52540
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int pasta[] = new int[3];
		int juice[] = new int[2];
		int minPasta, minJuice;
		for (int i = 0; i < 3; i++) {
			pasta[i] = sc.nextInt();
		}
		for (int i = 0; i < 2; i++){
			juice[i] = sc.nextInt();
		}
		
		minPasta = Math.min(Math.min(pasta[0], pasta[1]), pasta[2]);
		minJuice = Math.min(juice[0], juice[1]);
		
		System.out.printf("%d\n", minPasta + minJuice - 50);

	}
}

Measured memory_bytes: 17180
n, k, q = [int(i) for i in input().split()]
correct_answer_counts = [0] * n
for i in range(q):
	correct_answer = int(input())
	correct_answer_counts[correct_answer - 1] += 1
for i in range(n):
	print ('Yes' if (k + correct_answer_counts[i] - q > 0) else 'No')

Measured memory_bytes: 4680
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++) //for文マクロ
#define all(obj) obj.begin(), obj.end()
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef unsigned long long ull;
typedef int long long ll;
constexpr ll bigNum = 1000000007;

signed main()
{
    fast;
    string s;
    cin >> s;
    if (s == "Sunny")
    {
        cout << "Cloudy";
    }
    else if (s == "Cloudy")
    {
        cout << "Rainy";
    }
    else
    {
        cout << "Sunny";
    }
}

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

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pll pair<ll,ll>
#define MP make_pair
#define ff first
#define ss second
#define PB push_back
#define mod 1000000007
#define lp(i,start,end) for(ll i=start;i<=end;i++) 
#define deb1(a) cout<<#a<<" = "<<(a)<<endl;
#define deb2(a,b) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<endl;
#define deb3(a,b,c) cout<<#a<<" = "<<(a)<<", "<<#b<<" = "<<(b)<<", "<<#c<<" = "<<(c)<<endl;


ll modu(ll a, ll b)
{
	ll ans =1;
	while(b>0)
	{
		if(b&1)
		ans = (ans*a)%mod;
		b/=2;
		a = (a*a)%mod;
	}
	return ans;
}

int main()
{
	fastio
	ll t=1;
	//cin >> t;
	while(t--)
	{
		ll n,k;
		cin>>n>>k;
		ll a[n+1];
		ll cost[n+1];
		lp(i,1,n){
			cin>>a[i];
			cost[i]=mod;
		}
		cost[1]=0;
		lp(i,2,n){
			for(ll j=i-1; j>= max((ll)1,i-k) ;j--){
				cost[i]=min(cost[i],cost[j]+abs(a[i]-a[j]));
			}
		}
		cout<<cost[n]<<endl;
	}
	return 0;	
}


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

int main() {
  int h, w, s = 1;
  cin >> h >> w;
  vector<string> v(h);
  rep(i, h) cin >> v[i];
  rep(i, h){
    rep(j, w) if(v[i][j] == '#') ++s;
  }
  if(s == h + w) cout << "Possible" << endl;
  else cout << "Impossible" << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        
    Scanner sc = new Scanner(System.in);
    
    int m;//中間テスト
    int f;//期末テスト
    int r;//再試験
    int p;//学生の合計点数、ｍ　+ｆ、ｒ
    
/*    m = sc.nextInt();
    f = sc.nextInt();
    r = sc.nextInt();
    p = m + f;
 */   
    while (sc.hasNextLine()){
        
    m = sc.nextInt();
    f = sc.nextInt();
    r = sc.nextInt();
    p = m + f;
        
        
        if( m == -1 && f ==-1 && r ==-1){
            break;
        }
        else if(p < 30 || m == -1 ||f == -1){
            System.out.println("F");
            
        }else if((30 <= p && p < 50) && 50 <= r){
             System.out.println("C");
        }
        else if(30 <= p && p < 50){
                 System.out.println("D");
        }
             else if(50 <= p && p < 65){
                 System.out.println("C");
             }else if(65 <= p && p < 80){
                 System.out.println("B");
             }else if(80 <= p){
                 System.out.println("A");
             }
    }
    }
}





Measured memory_bytes: 26280
#include<bits/stdc++.h>
using namespace std;
#define a first
#define b second
int main(){
  #define int long
  int N,M,yen=0;
  cin>>N>>M;
  vector<pair<int,int>> v(N);
  for(int i=0;i<N;++i)cin>>v[i].a>>v[i].b;
  sort(v.begin(),v.end(),[](pair<int,int> p, pair<int,int> q){return (p.a<q.a);});
  int k=0;
  while(M>0){
    if(v[k].b<=M){
      yen+=v[k].a*v[k].b;
      M-=v[k].b;
    }
    else{
      yen+=v[k].a*M;
      break;
    }
    k++;
  }
  cout<<yen;
  return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using ull = unsigned long long;

/* Counter Lib */
template <class T>
class Counter {
 public:
  Counter() = default;
  template <class U>
  Counter(const U& container) {
    for (auto x : container) {
      counter_[x]++;
    }
  }
  auto val(const T& key) const { return counter_.find(key)->second; }
  auto add(const T& key) { counter_[key]++; }
  auto get() { return counter_; }
  auto get() const { return counter_; }
  auto hist() const {
    map<int, int> hist_counter;
    for (auto kv : counter_) {
      hist_counter[kv.second]++;
    }
    return hist_counter;
  }

 private:
  map<T, int> counter_;
};
/* /Counter Lib */

int main(int argc, char* argv[]) {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  /* */
  int n;
  cin >> n;
  vi a(n);
  for (int i = 0; i < n; ++i) cin >> a[i];

  Counter<int> counter(a);
  int count = 0;
  for (auto kv : counter.hist()) {
    if (kv.first == 1) continue;
    count += (kv.first - 1) * kv.second;
  }
  cout << n - 2 * ((count + 1) / 2)  << endl;
  /* */

  return EXIT_SUCCESS;
}


Measured memory_bytes: 5376
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll INF = 1e18;

int main(void){
    ll n;
    cin >> n;
    VL a(n);
    REP(i,n) a[i] = in();
    VVL dp(n + 1, VL(3, -INF));
    REP(i,3) dp[i][i] = a[i];
    REP(i,n) REP(j,3){
        if (dp[i][j] == -INF) continue;
        FOR(k,1,3){
            int d = i + k + 1;
            int p = j + k - 1;
            if (d >= n) continue;
            if (p >= 3) continue;
            chmax(dp[d][p], dp[i][j] + a[d]);
        }
    }
    ll ans = -INF;
    if (n % 2 == 0){
        chmax(ans, dp[n - 1][1]);
        chmax(ans, dp[n - 2][0]);
    }else{
        REP(j,3) chmax(ans, dp[n - 1 - j][2 - j]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 15736
#include<stdio.h>

int main(void){
  int N;
  int Change, i;
  
  scanf("%d", &N);
  
  for(i = 1000; i <= 10000; i += 1000){
    if(N <= i){
      Change = i - N;
      break;
    }
  }
  
  printf("%d\n", Change);
  
  return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

const int Max = 10005;
const int INF = (1<<29);
struct Node
{
    int v, c;
    bool operator < (const Node& a) const{
        return c > a.c;
    }
};

int n, color[Max], d[Max], p[Max];
int u, k, v, c;
vector<Node> G[Max];
priority_queue<Node> pq;
Node pn;

void dijstra()
{
    memset(color, -1, sizeof(color));
    for(int i=0; i<n; i++)
    {
        d[i] = INF;
    }
    d[0] = 0;
    p[0] = -1;
    pn = {0, d[0]};
    pq.push(pn);

    while(!pq.empty())
    {
        pn = pq.top(); pq.pop();
        int u = pn.v;
        color[u] = 0;
     
        for(int j=0; j<G[u].size(); j++)
        {
            int v = G[u][j].v;
            if(color[v]!=0 && d[u]+G[u][j].c<d[v])
            {
                d[v] = G[u][j].c+d[u];
                pn = {v, d[v]};
                pq.push(pn);
                p[j] = u;//j的父节点为u，有利于重建MST
            }
        }
    }
    //打印输出
    for(int i=0; i<n; i++)
    {
        if(d[i]==INF)
            cout << i << " " << -1 << endl;
        else
            cout << i << " " << d[i] << endl;
    }
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
         cin >> u >> k;
         for(int i=0; i<k; i++)
         {
             cin >> v >> c;
             Node pn = {v, c};
             G[u].push_back(pn);
         }
    }

    dijstra();
    return 0;
}



Measured memory_bytes: 8080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
void upd(int &x,int y)
{
	x+=y;
	x=(x%P+P)%P;
}
const int MAXN=329;
int a[MAXN],sum[MAXN],n;
int ans=0;
int f[2][MAXN*MAXN],g[2][MAXN*MAXN];
int main()
{
	n=read();
	for(int i=1; i<=n; ++i)
		sum[i]=sum[i-1]+(a[i]=read());
	ans=fpow(3,n);
	int cur=0;
	g[cur][0]=f[cur][0]=1;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<=sum[i];++j)
			f[cur^1][j]=g[cur^1][j]=0;
		for(int j=0;j<=sum[i-1];++j)
			if(f[cur][j])
			{
				upd(f[cur^1][j+a[i]],f[cur][j]);
				upd(f[cur^1][j],mul(2,f[cur][j]));
				upd(g[cur^1][j+a[i]],g[cur][j]);
				upd(g[cur^1][j],g[cur][j]);
			}
		cur^=1;
	}
	for(int i=(sum[n]+1)>>1;i<=sum[n];++i)
		upd(ans,-mul(3,f[cur][i]));
	if(!(sum[n]&1))
		upd(ans,mul(3,g[cur][sum[n]>>1]));
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1664
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val w = sc.nextLong()
    val wv = (0 until n).map { sc.next().toInt() to sc.next().toInt() }
    println(edpcE(n, w, wv))
}

fun edpcE(n: Int, w: Long, wv: List<Pair<Int, Int>>): Long {
    val dp = mutableListOf<LongArray>()
    for (i in 0..110) {
        dp.add(LongArray(100100) { Integer.MAX_VALUE.toLong() })
    }
    dp[0][0] = 0
    for (i in 0 until n) {
        for (sumV in dp[0].indices) {
            if (sumV - wv[i].second >= 0) {
                dp[i + 1][sumV] = Math.min(dp[i + 1][sumV], dp[i][sumV - wv[i].second] + wv[i].first)
            }
            dp[i + 1][sumV] = Math.min(dp[i + 1][sumV], dp[i][sumV])
        }
    }
    var res = 0L
    for (i in dp[0].indices) {
        if (dp[n][i] <= w) res = i.toLong()
    }
    return res
}

Measured memory_bytes: 156760
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[] lunch=new int[5];
		int[] lunch2=new int[5];

		int sum=0;
		int min=644;

		for(int i=0;i<5;i++) {
			lunch[i]=sc.nextInt();
		}

		for(int i=0;i<5;i++) {
			if(lunch[i]%10==0) {
				lunch2[i]=lunch[i];
			}else {
				lunch2[i]=((lunch[i]/10)+1)*10;
			}
		}

		for(int i=0;i<5;i++) {
			for(int j=0;j<5;j++) {
				if(i==j) {
					sum+=lunch[j];
				}else {
					sum+=lunch2[j];
				}
			}
			//System.out.println(sum);
			if(min>sum) min=sum;
			sum=0;
		}

		System.out.println(min);

		sc.close();

	}
}


Measured memory_bytes: 23124
#include <bits/stdc++.h> 
using namespace std; 
#define int long long
# define pii pair<int,int>
const int maxn=1e6+5;
signed main() { 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int x,y;
    cin>>x>>y;
    for(int i=0;i<=x;i++)
    {
    	if(i*2+(x-i)*4==y)
    	{
    		cout<<"Yes";
    		return 0;
    	}
    }
    cout<<"No";
}

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

typedef long long ll;
typedef pair<ll,ll> ii;
typedef long double ld;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
const int INF=2012345678;
const ll LLINF=4012345678012345678LL;
const ll MOD=1000000007; //998244353; //
const ld PI=3.1415926535898;
const ld EPS=1e-9;
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(b==0)return a;return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll expo(ll b,ll p,ll m){ll res=1; while(p){if(p&1)res=(res*b)%m; b=(b*b)%m; p>>=1;} return res;}
inline ll modinv(ll a,ll m){return expo(a,m-2,m);}

int n;
ll k;
vector<vector<ll> > mat;

inline vector<vector<ll> > matmult(vector<vector<ll> > a,vector<vector<ll> > b){
	vector<vector<ll> > ans;ans.resize(n);for(int i=0;i<n;i++)ans[i].assign(n,0);
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				ans[i][j]+=(a[i][k]%MOD)*(b[k][j]%MOD);
				ans[i][j]%=MOD;
			}
		}
	}
	return ans;
}

vector<vector<ll> > matexp(ll p){
	if(p==1)return mat;
	vector<vector<ll> > ans;
	vector<vector<ll> > temp=matexp(p/2);
	ans=matmult(temp,temp);
	if(p%2==1)ans=matmult(ans,mat);
	//printf("%lld\n",p);
	//for(int i=0;i<n;i++){for(int j=0;j<n;j++)printf("%lld ",ans[i][j]);printf("\n");}
	return ans;
}

int main(){
	scanf("%d%lld",&n,&k);
	ll temp;
	for(int i=0;i<n;i++){
		vector<ll> v;
		for(int j=0;j<n;j++){
			scanf("%lld",&temp);
			v.pb(temp);
		}
		mat.pb(v);
	}
	vector<vector<ll> > ans=matexp(k);
	ll a=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			a+=ans[i][j];
			a%=MOD;
		}
	}
	printf("%lld",a);
}



Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
	string str;
	cin>>str;
	int len=str.size();
	int pos1,pos2;
	for (pos1=0;pos1<len;++pos1) {
		if (str[pos1]=='C') {
			break;
		}
	}
	for (pos2=len-1;pos2>=0;--pos2) {
		if (str[pos2]=='F') {
			break;
		}
	}
	if (pos1<pos2) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
l = [0] * (N + 1)
ac = 0
wa = 0
for _ in range(M):
    p, S = input().split()
    if S == 'WA':
        if l[int(p)] >= 0:
            l[int(p)] += 1
    else:
        if l[int(p)] >= 0:
            wa += l[int(p)]
            ac += 1
            l[int(p)] = -1

print(ac, wa)


Measured memory_bytes: 3828
// https://atcoder.jp/contests/tenka1-2017/tasks/tenka1_2017_c
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <bitset>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define REP(i, n) for(size_t i = 0; i < (n); ++i)

int main()
{
    ll N;
    scanf("%lld", &N);
    for (ll h = 1; h <= 3500; ++h)
    {
        for (ll n = 1; n <= 3500; ++n)
        {
            ll f = N * h * n;
            ll d = 4LL * n * h - N * h - N * n;
            if (d <= 0) continue;
            ll r = f % d;
            if (r != 0) continue;
            ll w = f / d;
            ll q0 = (n * w + h * w + n * h) / 4LL;
            ll r0 = (n * w + h * w + n * h) % 4LL;
            ll q1 = (n * h * w) / N;
            ll r1 = (n * h * w) % N;
            if (r0 == 0 && r1 == 0 && q0 == q1)
            {
                printf("%lld %lld %lld\n", h, n, w);
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3804
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
void add(int &x,int y){
	x=(x+y)%mod;
}
int n,k,f[305][305][305],cnt[505],suf[505];
char s[505];
signed main(){
	scanf("%s%d",(s+1),&k);
	n=strlen(s+1);k=min(n,k);
	int res=0,tot=0;
	//cout<<n<<" "<<k<<endl;
	for(int i=1;i<=n;++i)
		if(s[i]=='0') cnt[++tot]=res,res=0;
		else ++res;
	if(res) cnt[++tot]=res;
	for(int i=tot;i>=1;--i)
		suf[i]=suf[i+1]+cnt[i];
	f[0][0][0]=1;
	for(int i=1;i<=tot;++i)
		for(int one=0;one<=n;++one)
			for(int st=0;st<=k;++st)
				if(f[i-1][one][st]){
					for(int v=0;v<=cnt[i];++v){
						int tmp=one-(cnt[i]-v);
						if(tmp>=0 && tmp<=suf[i+1]){
							//if(tmp>300) return puts("-1"),int(0);
							add(f[i][tmp][st],f[i-1][one][st]);
						} 
					}
					for(int v=cnt[i]+1;one-(cnt[i]-v)<=suf[i+1];++v){
						int tmp=one-(cnt[i]-v);
						if(tmp>=0 && tmp<=suf[i+1]){
							//if(tmp>300 || st+v-cnt[i]>300) return puts("-1"),int(0);
							add(f[i][tmp][st+v-cnt[i]],f[i-1][one][st]);	
						} 
					}
				}
	int ans=0;
	for(int st=0;st<=k;++st)
		add(ans,f[tot][0][st]);
	cout<<ans;
	return 0;	
}

Measured memory_bytes: 30468
n, k = gets.split.map(&:to_i)

ans = 0
(1..n).each do |index|
  loop_count, mod = n.divmod(index)
  possible_count = [index - k, 0].max
  ans += loop_count * possible_count
  ans += k == 0 ? mod : [mod - k + 1, 0].max
end

puts ans


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll h,w;
    cin >> h >> w;
    ll ch, dh, cw, dw;
    cin >> ch >> cw >> dh >> dw;
    --ch, --cw, --dh, --dw;
    vector<string> s(h);
    rep(i,h) cin >> s.at(i);

    ll INF = (1ll << 60);

    vector<vector<ll>> dp(h,vector<ll>(w,INF));
    priority_queue<pair<ll,pair<ll,ll>>> pq;

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

    pair<ll,ll> top = make_pair(ch, cw); //開始点
    dp.at(ch).at(cw) = 0;
    pq.emplace(0, top);
    while(!pq.empty()){
        auto x = pq.top();
        pq.pop();
        ll nx = x.second.first;
        ll ny = x.second.second;
        ll dist = -x.first;
        if(dp.at(nx).at(ny) < dist) continue;

        rep(i,4){
            ll x = nx + dx[i];
            ll y = ny + dy[i];
            if(x < 0 || x >= h || y < 0 || y >= w) continue;
            if(s.at(x).at(y) == '#') continue;
            if(dp.at(x).at(y) > dist){
                dp.at(x).at(y) = dist;
                pq.emplace(-dist, make_pair(x, y));
            }
        }

        ll nd = dist + 1;
        for(i = -2;i < 3;++i){
            for(j = -2;j < 3;++j){
                ll x = nx + i;
                ll y = ny + j;
                if(x < 0 || x >= h || y < 0 || y >= w) continue;
                if(s.at(x).at(y) == '#') continue;
                if(dp.at(x).at(y) > nd){
                    dp.at(x).at(y) = nd;
                    pq.emplace(-nd, make_pair(x, y));
                }
            }
        }
    }
    if(dp.at(dh).at(dw) == INF) cout << -1 << endl;
    else cout << dp.at(dh).at(dw) << endl;

    return 0;
}

Measured memory_bytes: 13500
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <signal.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); bool s=false; if(c=='-'){s=true;c=getchar();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); int s=0; if(c=='-'){s=1;c=getchar();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar(); while(c==' '||c=='\n') c=getchar(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar(); } *s='\0'; return len; }
void rsorta_d32(void *base, const int count, const int size, const int index){
	typedef int32_t rsort_t;
	rsort_t (*a)[size] = (rsort_t(*)[size])base;
	rsort_t (*b)[size] = (rsort_t(*)[size])malloc(count*size*sizeof(rsort_t));
	int c[0x100];
	for(int k=0; k<4; k++){
		memset(c, 0, sizeof(c)); for(int i=0; i<count; i++){ c[(a[i][index]>>(k<<3))&0xFF]++; } for(int i=1; i<0x100; i++) c[i]+=c[i-1]; for(int i=count-1; i>=0; i--){ int to=--c[(a[i][index]>>(k<<3))&0xFF]; for(int j=0; j<size; j++){ b[to][j]=a[i][j]; } }{rsort_t(*t)[size]=a; a=b; b=t;}
	}
	free(b);
}

int n;
int a[200000];

inline int f(int k){
	long ans=0;
	for(int i=0; i<n; i++){
		ans+=(a[i]-1)/k;
	}
	return ans>INT_MAX?INT_MAX:ans;
}

int main(void){
	n=nextint();
	int k=nextint();
	for(int i=0; i<n; i++){
		a[i]=nextint();
	}
	int l=1, r=1000000000;
	while(l<=r){
		int m=(l+r)/2;
		if(f(m)<=k) r=m-1; else l=m+1;
	}
	printf("%d\n", l);
}


Measured memory_bytes: 2308
from collections import Counter

H, W = map(int, input().split())

c = Counter()
for h in range(H):
    c.update(input())

demand2 = W % 2 * (H // 2) + H % 2 * (W // 2)
demand4 = (H // 2) * (W // 2)

supply2 = supply4 = 0
for x in c.values():
    supply4 += x // 4
    supply2 += x % 4 // 2

yes = False
if supply4 >= demand4:
    supply2 += (supply4 - demand4) * 2
    if supply2 >= demand2:
        yes = True

print('Yes' if yes else 'No')

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

int main() {
    int n;
    int a[30], b[30], c[30];
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i) cin >> b[i];
    for(int i = 0; i < n - 1; ++i) cin >> c[i];
    
    int ans = 0;
    for(int i = 0; i < n; ++i) {
        ans += b[a[i]-1];
        if(a[i] - a[i-1] == 1) ans += c[a[i-1]-1];
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>

int main(){
	int a[10],b,Ichi=0,Ni=0,San=0,n,i;

	for(i=0;i<10;i++){
		std::cin>>a[i];
	}

	for(i=0;i<10;i++){
		if(a[i]>Ichi){
			b=Ichi;
			Ichi=a[i];
			a[i]=b;
		}
		if(a[i]>Ni){
			b=Ni;
			Ni=a[i];
			a[i]=b;
		}
		if(a[i]>San){
			b=San;
			San=a[i];
			a[i]=b;
		}
	}

	std::cout<<Ichi<<std::endl<<Ni<<std::endl<<San<<std::endl;


	return 0;
}

Measured memory_bytes: 1160
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

a,b,c,d = inpl()
x = c-a
y = d-b
res = ''
res += 'U' * y + 'R' * x
res += 'D' * y + 'L' * x
res += 'L' + 'U' * (y+1) + 'R' * (x+1) + 'D'
res += 'R' + 'D' * (y+1) + 'L' * (x+1) + 'U'
print(res)


Measured memory_bytes: 77140
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
m = max(K,m)
s = bin(m)[2:]
length = len(s)
ls = [[0,length-i-1] for i in range(length)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(length):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(length):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  dic[n]=s
s = bin(K+1)[2:]
ils = [len(s)-i-1 for i in range(len(s)) if s[i]=='1']
xls = []
for i in range(len(ils)):
  m = ''
  for j in range(ils[i]):
    if dic[j]>0:
      m+='1'
    else:
      m+='0'
  m += '0'
  while len(m)<len(s):
    m += s[len(s)-len(m)-1]
  m = m[::-1]
  xls += [int(m,2)]

ans = 0
for x in xls:
  h = 0
  for u in a:
    h += x^u
  if h>ans:
    ans = h
print(ans)


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

int main(void)
{
	int A, B, C;
	cin >> A >> B >> C;
	int ans = 0;

	/* 偶奇を一致させる */
	int oddcount = 0;
	oddcount += A % 2;
	oddcount += B % 2;
	oddcount += C % 2;
	if(oddcount == 1) {
		/* 二つが偶数の場合 */
		if(A % 2 == 0)
			A++;
		if(B % 2 == 0)
			B++;
		if(C % 2 == 0)
			C++;
		ans++;
	} else if(oddcount == 2) {
		/* 二つが奇数の場合 */
		if(A % 2 == 1)
			A++;
		if(B % 2 == 1)
			B++;
		if(C % 2 == 1)
			C++;
		ans++;
	}

	/* 大きいほうに合わせる */
	int max = A;
	if(max < B)
		max = B;
	if(max < C)
		max = C;
	ans += ((max - A) / 2) + ((max - B) / 2) + ((max - C) / 2);
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
iN = int(input())
aA = [int(_) for _ in input().split()]


if iN == 1:
    print(aA[0])
elif iN % 2 == 0:
    print(" " .join([str(_) for _ in list(reversed(aA[1::2])) + aA[0::2] ]))
else:
    print(" " .join([str(_) for _ in list(reversed(aA[0::2])) + aA[1::2] ]))


Measured memory_bytes: 28408
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		for(int i = 1; i <= 9; i++){
			dfs(0, i);
		}

		int count = 0;
		while(!pq.isEmpty()){
//			System.out.print(pq.poll() + " ");
			if(pq.poll() <= n){
				count++;
			}
			else {
				break;
			}
		}

		System.out.println(count);


	}

	static int digits[] = new int[10];
	static PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

	static void dfs(int depth, int n){
		String tmp = "";

		if(depth == n){
			int appear[] = new int[10];
			for(int i = 0; i < n; i++){
				tmp += (char)(digits[i] + '0');
				appear[digits[i]]++;
			}
			if(appear[3]*appear[5]*appear[7] != 0){
				pq.add(Integer.parseInt(tmp));
			}

			return;
		}

		int pattern[] = {3,5,7};

		for(int i = 0; i < pattern.length; i++){
			digits[depth] = pattern[i];
			dfs(depth + 1, n);
		}
	}
}


Measured memory_bytes: 45508
#include<iostream>

using namespace std;

int main (){
    int n,i,ans=0,tmp=0; cin >> n;
    int h[n];
    for(i = 0; i < n; i++){
        cin >> h[i];
    }

    i = 0;
    while(i < n){
        if(h[i-1] >= h[i]){
            tmp++;
        } else {
            tmp = 0;
        }
        if(ans < tmp) ans = tmp;
        i++;
    }

    cout << ans << endl;
    return 0;
}

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

using namespace std;

int solve(string s, string t){
	for(int i = 0; i < s.length(); i++) if(s.substr(i, t.length()) == t) return 1;
	return 0;
}

int main(){
	string s, t; cin >> s >> t;
	cout << (solve(s + s.substr(0, s.length() - 1), t) ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
vector<int>v[100005];
int use[100005];
void dfs(int k){
	use[k]=1;
	for (int i : v[k])
		if (!use[i])
			dfs(i);
}
signed main()
{
	int n,m;
	cin>>n>>m;
	while (m--){
		int a,b;
		cin>>a>>b;
		a--,b--;
		v[a].pb(b);
		v[b].pb(a);
	}
	int ans=-1;
	for (int i=0;i<n;i++)
		if (!use[i])
			dfs(i),ans++;
	cout<<ans;
	re 0;
}


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

ll dp[1005][2][1005];

int main(void){
    string s;
    int k;
    cin >> s >> k;
    
    int n = s.size();
    dp[0][0][0] = 1;
    
    for(int i = 0;i < n;i++){
        int a = s[i]-'0';
        for(int j = 0;j < k;j++){
            dp[i+1][1][j] += dp[i][1][j];
            for(int l = 1;l < 10;l++){
                dp[i+1][1][j+1] += dp[i][1][j];
            }
            
            for(int l = 1;l < a;l++){
                dp[i+1][1][j+1] += dp[i][0][j];
            }
            
            if(a == 0)dp[i+1][0][j] += dp[i][0][j];
            else dp[i+1][0][j+1] += dp[i][0][j];
            if(a > 0)dp[i+1][1][j] += dp[i][0][j];
        }
    }
    
    ll ans = 0;
    rep(i,n)ans += (dp[i+1][1][k] + dp[i+1][0][k]);
    cout << ans << endl;
}

Measured memory_bytes: 4384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstring>
using namespace std;

const int B=999999937;
const int P=1000000007;

vector<long long> gen_hash(const string &s){
	vector<long long> hash(s.size());
	long long c=0;
	for(int i=0;i<s.size();i++){
		c=(c*B+s[i])%P;
		hash[i]=c;
	}
	return hash;
}
long long pow_binary_mod(long long x,long long y,long long mod){
	long long z=1;
	for(;y;y>>=1){
		if((y&1)!=0)z=z*x%mod;
		x=x*x%mod;
	}
	return z;
}

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

	string s;
	cin>>s;
	int ls=s.size();
	vector<long long> v=gen_hash(s);

	//int T;
	//for(cin>>T;T--;){
		string q;
		cin>>q;
		int lq=q.size();
		long long hash=gen_hash(q)[lq-1];
		long long Brev=pow_binary_mod(B,lq,P);
		vector<int> r;
		int i=lq-1;
		for(;i<ls;i++){
			if(v[i]==((i>=lq?v[i-lq]:0)*Brev+hash)%P){
				r.push_back(i-lq+1);
			}
		}
		if(!r.empty()){
			for(int i=0;i<r.size();i++)printf("%d\n",r[i]);
			//puts("1");
		}else{
			//puts("0");
		}
	//}
}

Measured memory_bytes: 16444
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String w = str;
		str = br.readLine();
		Boolean isEnd = str.equals("END_OF_TEXT");
		int count = 0;
		while (!isEnd) {
			String[] words = str.split(" ", 0);
			for (String word : words) {
				if (word.equalsIgnoreCase(w) == true) {
					count = count + 1;
				}
			}
			str = br.readLine();
			isEnd = str.equals("END_OF_TEXT");
		}
		System.out.println(count);
	}
}

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

const ll MOD = 1000000007;

int main(){
    ll n, k;
    cin >>n >>k;
    vector<ll> a(n+1);
    vector<ll> aa;
    set<ll> st;
    set<ll> st2;
    vector<ll> loop;
    ll loop_cnt = 0LL;
    ll before_loop = 0LL;
   // st.insert(1);
    a[0] = 1;
    rep(i, n){
        cin >> a[i+1];
        //a[i+1];    
    }
    aa.push_back(1);
    rep(i, 2*n){
        aa.push_back(a[aa[i]]);
    }

    rep(i, 2*n){
        if(!st.count(aa[i])){
            st.insert(aa[i]);
            before_loop++;
        }else if(!st2.count(aa[i])){
            st2.insert(aa[i]);
            loop.push_back(aa[i]);
            //loop_cnt++;
        }
    }
    ll ans;
    loop_cnt = st2.size();
    //cout << "before_loop " << before_loop << endl;
    //cout << "loop_cnt " << loop_cnt << endl;
    if(k <=before_loop){
        ans = aa[k];
    }else{
        ll kk = ((k - before_loop) % loop_cnt);
        ans = loop[kk];
    }
    cout << ans << endl;
}

Measured memory_bytes: 26636
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    while (true) {
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 0) {
            return 0;
        }

        vector<pair<int, int>> v;
        for (int i = 0; i < n; ++i) {
            int d, p;
            cin >> d >> p;
            v.emplace_back(d, p);
        }

        sort(begin(v), end(v),
             [](const pair<int, int>& a, const pair<int, int>& b) {
                 if (a.second == b.second) {
                     return a.first < b.first;
                 }
                 return a.second > b.second;
             });
        auto remain = m;
        auto expectedSum = 0;
        for (auto&& i : v) {
            if (i.first <= remain) {
                remain -= i.first;
            }
            else {
                expectedSum += (i.first - remain) * i.second;
                remain = 0;
            }
        }
        cout << expectedSum << endl;
    }
}


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


using namespace std;


int main()
{
    long long N;
    vector<long long> a;

    cin >> N;
    for (auto i = 0; i < N; i++) {
        long long t;
        cin >> t;
        a.push_back(t);
    }

    vector<long long> sa(N);
    copy(a.begin(), a.end(), sa.begin());
    sort(sa.begin(), sa.end());

    for (auto i = 0; i < N; i++) {
        if (a[i] >= sa[N / 2]) {
            cout << sa[N / 2 - 1] << endl;
        } else {
            cout << sa[N / 2] << endl;
        }
    }
}


Measured memory_bytes: 5488
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100010

int n,m=0;
char s[N],t[N];

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	int l=1,r=n,ans=0;
	while(l<r)
	{
		int cnt1=0,cnt2=0;
		while(s[l]=='x') l++,cnt1++;
		while(s[r]=='x') r--,cnt2++;
		if(s[l]!=s[r]) 
		{
			puts("-1");
			return 0;	
		}
		else ++l,--r;
		ans+=abs(cnt1-cnt2);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
class Items:
    def __init__(self, v, w, t, d, s):
        self.value = v
        self.weight = w
        self.type = t
        self.date = d
        self.name  = s


    def __lt__(self, other):
        if self.value < other.value:
            return True
        elif self.value == other.value:
            if self.weight < other.weight:
                return True
            elif self.weight == other.weight:
                if self.type < other.type:
                    return True
                elif self.type == other.type:
                    if self.date < other.date:
                        return True
                    elif self.date == other.date:
                        if self.name < other.name:
                            return True
                        else:
                            return False
                    else:
                        return False

                else:
                    return False
            else:
                return False
        else:
            return False

    def __str__(self):
        return "{} {} {} {} {}".format(self.value, self.weight, self.type, self.date, self.name)



num = int(input())

L = []

for _ in range(num):
    v, w, t, d, s = input().split()
    L.append(Items(int(v), int(w), t, int(d), s))

L.sort()


for i in L:
    print(i)





Measured memory_bytes: 39280
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
int f(int x, int y, int nx, int ny, vvi &v) {
	int ret=v[nx][ny] - v[x][ny] - v[nx][y] + v[x][y];
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;
	vvi b(2 * k + 1, vi(2 * k + 1, 0)), w(2 * k + 1, vi(2 * k + 1, 0));
	REP(i, n) {
		int x, y;
		char c;
		cin >> x >> y >> c;
		x %= 2 * k;
		y %= 2 * k;
		if (c == 'B')b[y + 1][x + 1]++;
		else w[y + 1][x + 1]++;
	}
	REP(i, 2 * k) {
		REP(j, 2 * k + 1) {
			b[i + 1][j] += b[i][j];
			w[i + 1][j] += w[i][j];
		}
	}
	REP(i, 2 * k + 1) {
		REP(j, 2 * k) {
			b[i][j + 1] += b[i][j];
			w[i][j + 1] += w[i][j];
		}
	}
	int ans = 0;
	REP(i, k) {
		REP(j, k) {
			int cntb, cntw;
			cntw = f(0, 0, i, j, w) + f(i, j, i + k, j + k, w) + f(0, j + k, i, 2 * k, w) + f(i + k, 0, 2 * k, j, w) + f(i + k, j + k, 2 * k, 2 * k, w);
			cntb = f(0, j, i, j + k, b) + f(i, 0, i + k, j, b) + f(i, j + k, i + k, 2 * k, b) + f(i + k, j, 2 * k, j + k, b);
			ans = max(ans, cntb + cntw);
			cntb = f(0, 0, i, j, b) + f(i, j, i + k, j + k, b) + f(0, j + k, i, 2 * k, b) + f(i + k, 0, 2 * k, j, b) + f(i + k, j + k, 2 * k, 2 * k, b);
			cntw = f(0, j, i, j + k, w) + f(i, 0, i + k, j, w) + f(i, j + k, i + k, 2 * k, w) + f(i + k, j, 2 * k, j + k, w);
			ans = max(ans, cntb + cntw);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 31872
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c<'0' || c>'9'));
	if(c=='-') c=getchar(),f=-1;
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	ll f=1;
	while((c=getchar())!='-' && (c<'0' || c>'9'));
	if(c=='-') c=getchar(),f=-1;
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=2e3+10;
int sum1[maxn][maxn],sum2[maxn][maxn];
char s[10];
int sum11(int x1,int y1,int x2,int y2){
	if(x1>x2 || y1>y2) return 0;
	return sum1[x2][y2]-sum1[x1-1][y2]-sum1[x2][y1-1]+sum1[x1-1][y1-1];
}
int sum22(int x1,int y1,int x2,int y2){
	if(x1>x2 || y1>y2) return 0;
	return sum2[x2][y2]-sum2[x1-1][y2]-sum2[x2][y1-1]+sum2[x1-1][y1-1];
}
int main(){
	int n=read(),m=read();
	REP(i,1,n){
		int x=read()%(2*m)+1,y=read()%(2*m)+1;
		scanf("%s",s);
		int u=(s[0]=='B');
		if(u) sum1[x][y]++;
		else sum2[x][y]++;
	}
	REP(i,1,2*m) REP(j,1,2*m){
		sum1[i][j]+=sum1[i-1][j]+sum1[i][j-1]-sum1[i-1][j-1];
		sum2[i][j]+=sum2[i-1][j]+sum2[i][j-1]-sum2[i-1][j-1];
	}
	int ans=0;
	REP(i,0,m) REP(j,0,m){
		int x=i+m,y=j+m;
		int tmp1=sum11(1,1,i,j)+sum11(i+1,j+1,x,y)+sum11(x+1,1,2*m,j)+sum11(x+1,y+1,2*m,2*m)+sum11(1,y+1,i,2*m);
		int tmp2=sum22(1,1,i,j)+sum22(i+1,j+1,x,y)+sum22(x+1,1,2*m,j)+sum22(x+1,y+1,2*m,2*m)+sum22(1,y+1,i,2*m);
		ans=max(ans,max(tmp1-tmp2+sum22(1,1,2*m,2*m),sum11(1,1,2*m,2*m)-tmp1+tmp2));
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 31744
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back

main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
		
	int n,m;
	cin>>n>>m;
	int arr[n+2];
	for(int i=0;i<n+2;i++)
		arr[i]=0;

	for(int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;

		arr[x]++;
		arr[y+1]--;
	}

	for(int i=2;i<=n;i++)
		arr[i]+=arr[i-1];

	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(arr[i]==m)
			ans++;
	}
	cout<<ans;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;

int H, W, N;
#define MAX_H 1000
#define MAX_W 1000
#define MAX_N 9

char maze[MAX_H + 1][MAX_W + 1];
int sy, sx, gy, gx;

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

	cin >> H >> W >> N;
	int pos[10][2];
	rep(y, 0, H) rep(x, 0, W) {
		cin >> maze[y][x];
		switch (maze[y][x]) {
			case 'S' :
				pos[0][0] = x;
				pos[0][1] = y;
				break;
			case '1' :
				pos[1][0] = x;
				pos[1][1] = y;
				break;
			case '2' :
				pos[2][0] = x;
				pos[2][1] = y;
				break;
			case '3' :
				pos[3][0] = x;
				pos[3][1] = y;
				break;
			case '4' :
				pos[4][0] = x;
				pos[4][1] = y;
				break;
			case '5' :
				pos[5][0] = x;
				pos[5][1] = y;
				break;
			case '6' :
				pos[6][0] = x;
				pos[6][1] = y;
				break;
			case '7' :
				pos[7][0] = x;
				pos[7][1] = y;
				break;
			case '8' :
				pos[8][0] = x;
				pos[8][1] = y;
				break;
			case '9' :
				pos[9][0] = x;
				pos[9][1] = y;
				break;
		}
	}

	int hp = 1;

	int dx[4] = {0, -1, 1, 0};
	int dy[4] = {-1, 0, 0, 1};
	int ans = 0;
	rep(j, 0, N) {
		queue<P> q;
		sx = pos[j][0];
		sy = pos[j][1];
		gx = pos[j + 1][0];
		gy = pos[j + 1][1];
		int d[H][W];
		rep(y, 0, H) rep(x, 0, W) d[y][x] = INF;
		d[sy][sx] = 0;
		q.push(make_pair(sx, sy));
		while(q.size()) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			if(maze[y][x] == (hp - '0')) {
				hp++;
				break;
			}
			rep(i, 0, 4) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(0 <= nx && nx < W && 0 <= ny && ny < H && maze[ny][nx] != 'X' && d[ny][nx] == INF) {
					d[ny][nx] = d[y][x] + 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
		ans += d[gy][gx];
	}
	cout << ans << endl;


}



Measured memory_bytes: 8000
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[100];;
    for(int i = 0;i<n;i++) cin >> a[i];
    sort(a,a+n,greater<int>());
    int al = 0;
    int bo = 0;
    for(int i=0;i<n;i++){
        if(i%2 == 0) al+=a[i];
        else bo += a[i];
    }
cout << al-bo << endl;
}


Measured memory_bytes: 256
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")


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

#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


using lli = long long int;
using ld = long double;
using ull = unsigned long long int;


#define FOR(i,x,n) for(lli i=x;i<n;i++)
#define RFOR(i,x,n) for(lli i=x;i>=n;i--)
#define pb push_back
#define Resize(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unique_sort(c) (sort(c.begin(),c.end()), Resize(c))
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) (lli)x.size()
#define fs first
#define ss second
#define mp make_pair
#define lb '\n'
#define gc getchar()
#define pc putchar
#define il inline void
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;
 
 
const lli mod=1e9+7;

template <typename T, typename U, typename V> using TP = tuple<T,U,V>;
template <typename T> using VI = vector<T>;
template <typename T> using LI = list<T>;
template <typename T, typename U> using PI = pair<T,U>;
template <typename T, typename U> using VPI = vector<pair<T,U>>;
template <typename T> using PQ = priority_queue<T>;

template <typename T> inline void read(T& r){ static char c; r=0; int f=1; for(c=gc; c<'0'||c>'9'; c=gc) if(c=='-')f=-1; for(; c>='0'&&c<='9'; r=(r<<1)+(r<<3)+(c^48),c=gc); r*=f; } 
template <typename T, typename... Args> inline void read(T& r, Args&... args) { read(r); read(args...); }

template <typename T> inline void rdstr(T& x){static char c;  for(c=gc; (c!=10 && c!=' ') ; c=gc)x.pb(c);}
template <typename T1, typename T2> inline void chkmin(T1 &a, const T2 & b) {if (a > b) a = b;}
template <typename T1, typename T2> inline void chkmax(T1 &a, const T2 & b) {if (a < b) a = b;}


void solve()
{
	lli n; read(n);
	lli a[n], b[n];
	FOR(i,0,n){read(a[i],b[i]); if(n%2==0){a[i]*=2; b[i]*=2;}}
	sort(a,a+n); sort(b,b+n);
	
	lli mx,mn;
	if(n&1){mx = b[n/2]; mn = a[n/2];}
	else {mx = (b[n/2]+b[(n-1)/2])/2; mn = (a[n/2]+a[(n-1)/2])/2;}

	cout<< mx-mn+1 <<lb;
}



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


Measured memory_bytes: 6720
using namespace std;
#include<bits/stdc++.h>
#define BEGIN ios_base::sync_with_stdio(0);cin.tie(0);
#define END return EXIT_SUCCESS;
#define FOR(I,A,B) for((I)=(A);(I)<(B);(I)++)
#define REP(I,N) FOR((I),0,(N))
#define UP(I,A,B) for((I)=(A);(I)<=(B);(I)++)
#define DW(I,A,B) for((I)=(A);(I)>=(B);(I)--)
#define IN(P) cin>>(P)
#define IN2(P1,P2) cin>>(P1)>>(P2)
#define IN3(P1,P2,P3) cin>>(P1)>>(P2)>>(P3)
#define INS(I,N,V) REP((I),(N)) cin>>(V[I])
#define INS2(I,N,V1,V2) REP((I),(N)) cin>>(V1[I])>>(V2[I]);
#define INS3(I,N,V1,V2,V3) REP((I),(N)) cin>>(V1[I])>>(V2[I])>>(V3[I]);
#define OUT(P) cout<<(P)<<endl
#define OUT2(P1,P2) cout<<(P1)<<" "<<(P2)<<endl
#define OUT3(P1,P2,P3) cout<<(P1)<<" "<<(P2)<<" "<<(P3)<<endl
#define OUTS(I,N,V) REP((I),(N)) cout<<(V[i])<<endl
#define ALL(C) (C).begin(),(C).end()
#define RALL(C) (C).rbegin(),(C).rend()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

string S,T;
long L,i;
inline void solve(){
  IN(S);
  L=S.size();
  if(S[0]!='A'){
    OUT("WA");
    return;
  }
  T=S.substr(2,L-3);
  if(count(ALL(T),'C')!=1){
    OUT("WA");
    return;
  }
  REP(i,L){
    if(i==0)continue;
    if(i>=2&&i<=L-2&&S[i]=='C')continue;
    if(isupper(S[i])){
      OUT("WA");
      return;
    }
  }
  OUT("AC");
}

int main(int argc,char**argv){
  BEGIN
  solve();
  END
}


Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X = int(readline())

    for i in range(X + 1):
        if i * (i + 1) // 2 >= X:
            ans = i
            break

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9020
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(a, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b){
  if (a < b){
    a = b;
    return true;
  }
  return false;
}

int main(){
  cout << fixed << setprecision(15);
  int n; cin >> n;
  vi l(n); rep(i, n) cin >> l[i];

  ll ans = 0;
  sort(all(l));
  for (int i = 0; i < n; i++){
    for (int j = i + 1; j < n; j++){
      int x = lower_bound(all(l), l[i] + l[j]) - l.begin();
      ans += x - j - 1;
    }
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int h = sc.nextInt();
		int w = sc.nextInt();
		int[][] map = new int[h][w];
		int[][] cost = new int[h][w];
		
		for(int i=0;i<h;i++){
			char[] a = sc.next().toCharArray();
			for(int j=0;j<w;j++) map[i][j] = (int)a[j]-48;
			Arrays.fill(cost[i], Integer.MAX_VALUE);
		}
		
		ArrayDeque<Integer> x = new ArrayDeque<Integer>();
		ArrayDeque<Integer> y = new ArrayDeque<Integer>();
		x.offer(0);
		y.offer(0);
		cost[0][0] = 0;
		
		int p, q;
		while(x.size()!=0){
			p = x.poll();
			q = y.poll();
			if(p!=w-1 && cost[q][p]+map[q][p+1]<cost[q][p+1]){
				x.offer(p+1);
				y.offer(q);
				cost[q][p+1] = cost[q][p]+map[q][p+1];
			}
			if(q!=h-1 && cost[q][p]+map[q+1][p]<cost[q+1][p]){
				x.offer(p);
				y.offer(q+1);
				cost[q+1][p] = cost[q][p]+map[q+1][p];
			}
		}
		System.out.println(cost[h-1][w-1]);
	}	
}

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

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  int K;
  cin >> K;

  char target = S.at(K - 1);
  for (int i = 0; i < N; i++) {
    if (S.at(i) == target)
      cout << S.at(i);
    else
      cout << '*';
  }

  cout << endl;
}

Measured memory_bytes: 256