akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
double num1[1000];
double num2[1000];
int n = 0;
double fun(int p) {
	double sum = 0;
	for(int i=0;i<n;i++) {
		sum += pow(abs(num1[i]-num2[i]),p);
	}
	sum = pow(sum,1.0/(p*1.0));
	return sum;
}

int main() {
//	freopen("in","r",stdin);
	cin>>n;
	for(int i=0;i<n;i++) 
		cin>>num1[i];

	for(int j=0;j<n;j++) 
		cin>>num2[j];

	cout<<fixed<<setprecision(6)<<fun(1)<<endl;
	cout<<fixed<<setprecision(6)<<fun(2)<<endl;
	cout<<fixed<<setprecision(6)<<fun(3)<<endl;

	double max0 = -1;
	for(int i=0;i<n;i++) {
		max0 = max(max0,abs(num1[i]-num2[i]));
	}

	cout<<fixed<<setprecision(6)<<max0<<endl;
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int>a(n);
  for(int i = 0; i<n; i++)
    cin >> a.at(i);
  
  bool ans = true;
  
  for(int i = 0; i<n; i++){
    if(a.at(i)%2 == 1)
      continue;
    else if(a.at(i)%3 == 0 || a.at(i)%5 == 0)
      continue;
    else
      ans = false;
  }
  if(ans)
    cout << "APPROVED" << endl;
  else
    cout << "DENIED" << endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

int main(){
  double n,t,a;
  cin >> n >> t >> a;
  double h[1000], tmp;
  for(int i = 0; i < n; i++){
    cin >> tmp;
    h[i] = t - (tmp * 0.006);
  }
  int ret = 0;
  double min = fabs(h[0] - a);
  for(int i = 1; i < n; i++){
    if(min > fabs(h[i] -a)){
      min = fabs(h[i] -a);
      ret = i;
    }
  }
  cout << ret+1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define Inf 1000000000
#define nmax_def 110000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;

int main() {
	ll N;
	cin >> N;
	vl C(N);
	rep(i, N) {
		cin >> C[i];
	}
	sort(C.begin(), C.end(), less<ll>());
	ll ans = 0;
	rep(i, N) {
		ll anstmp = C[i];
		anstmp *= (N - i + 1);
		anstmp %= mod;
		ans += anstmp;
		ans %= mod;
	}
	rep(i, 2 * N - 2) {
		ans *= 2;
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE Strict #-}
{-# LANGUAGE StrictData #-}
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import Data.Array.Unboxed
import Data.Array.ST
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Data.List
import Data.Char

main :: IO ()
main = do
    (s,w) <- (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    putStrLn $ if w >= s then "unsafe" else "safe"

Measured memory_bytes: 4168
//
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>

#define rep(i,n) for(int i=0;i<n;i++)
#define scanInt(i) scanf("%d", &i)

using namespace std;

class xy_t{
public:
  double x;
  double y;

  void disp(){
	  cout << "x " << x << " y " << y << endl;
  }
};

int main(){
	xy_t P[110];
	int N = 0;
	double mx, my;
	  while(scanf("%lf,%lf", &mx, &my) != EOF){
	    P[N].x = mx;
	    P[N].y = my;
		// P[N].disp();
		N++;
	  }


	  double sum = 0.0;
	  for(int i=0; i+2<N; i++){
	    xy_t a=P[0], b=P[i+1], c=P[i+2];
	    sum += 0.5*abs((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
	  }
	  printf("%.8lf\n", std::abs(sum));

	return 0;
}

Measured memory_bytes: 3160
#include <cstdio>
#include <cstring>
#include <cctype>

int main(void) {
    char str[81];
    while(gets(str)) {
        while(!strstr(str, "this") && !strstr(str, "that") && !strstr(str, "the")) {
            for(int r = 0; r < strlen(str); r++) {
                if(isalpha(str[r])) {
                    str[r] = 'a' + (str[r] - 'a' + 1) % 26;
                }
            }
        }
        printf("%s\n", str);
    }
    return(0);
}

Measured memory_bytes: 936
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <tuple>

#define INF 100100100100
#define rep(i,n) for(int i=0; i<(n); i++)
typedef long long ll;
using namespace std;

 
int main(){
    int m1,d1,m2,d2;
    cin >> m1 >> d1 >> m2 >> d2;
    
    if(m1 == m2){
        cout << 0 << endl;
        return 0;
    }
    cout << 1 << endl;
    return 0;
}


Measured memory_bytes: 256
/*
ID: computerbox --> Huseyn Hajiyev
LANG: C++
TASK: target_mode_on
*/
#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define _CRT_SECURE_NO_WARNINGS
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
#define FAST_READ ios_base::sync_with_stdio(0);/*cin.tie(0); cout.tie(0);*/
#define in freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define MAXN 200010

using namespace std;

#define debug(args...)(Debugger()) , args
class Debugger
{
  public:
  Debugger(const std::string& _separator=", ") :
  first(true),separator(_separator){}
  template<typename ObjectType>
  Debugger& operator,(const ObjectType& v)
  {
        if(!first)cerr<<separator;
        cerr<<v;
        first=false;
        return *this;
  }
  ~Debugger() {cerr<<endl;}      
  private:
    bool first;
    string separator;
};
 
template <typename T1, typename T2>
inline ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
   return os<<"("<<p.first<<", "<<p.second<<")";
}
template<typename T>
inline ostream &operator<<(ostream & os,const vector<T>& v)
{
    bool first=true;
    os<<"[";
    for(unsigned ll i=0;i<v.size();i++)
    {
        if(!first)os<<", ";
        os<<v[i];
        first=false;
    }
        return os<<"]";
}
template<typename T>
inline ostream &operator<<(ostream & os,const set<T>&v)
{
    bool first=true;
    os<<"[";
    for(typename set<T>::const_iterator ii=v.begin();ii!=v.end();++ii)
    {
        if(!first)os<<", ";
        os<<*ii;
        first=false;
    }
    return os<<"]";
}
template<typename T1, typename T2>
inline ostream &operator<<(ostream & os,const map<T1, T2>&v)
{
        bool first=true;
        os<<"[";
        for(typename map<T1,T2>::const_iterator ii=v.begin(); ii!=v.end();++ii)
        {
            if(!first)os<<", ";
            os<<*ii;
            first=false;
        }
        return os<<"]";
}

ll massiv[MAXN];

int main(){
FAST_READ;
cin.tie(0);
ll n,k;
cin>>n>>k;
for(ll i=1;i<=n;i++)
{
  cin>>massiv[i];
}
//sort(massiv+1,massiv+(n+1));
//arr(massiv,n);
ll cnt=0;
ll mina=LONG_LONG_MAX;
ll posm;

for(ll i=1;i<=n;i++)
{
  if(massiv[i]<mina)
  {
    mina=massiv[i];
    posm=i;
  }
}

if(posm+(k-1)>k)
{
  posm=n-(k-1);
}

for(ll i=posm;i<n;i+=(k-1))
{
  cnt++;
}
//cnt--;
//deb(cnt);
for(ll i=1;i<posm;i+=(k-1))
{
  cnt++;
}
cout<<cnt<<endl;


return 0;
} 

Measured memory_bytes: 1024
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
	int f = 1, x = 0;
	char ch;

	do{
		ch = getchar();
		if (ch == '-')
			f = -1;
	}while(ch < '0' || ch > '9');
	do{
		x = x * 10 + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return f * x;
}

int a, b, c;

int main()
{
	a = read();
	b = read();
	c = read();

	if ((a == 5 && b == 5 && c == 7) || (a == 5 && b == 7 && c == 5) || (a == 7 && b == 5 && c == 5))
		printf("YES\n");
	else
		printf("NO\n");

	return 0;
}


Measured memory_bytes: 3640
N = int(input())
W = []
flag = "Yes"
last_chara = ''
for i in range(N):
  now_W = input()
  www = list(now_W)
  if i != 0:
    if www[0] != last_chara:
      flag = "No"
      break
  if now_W in W:
    flag = "No"
    break
  W.append(now_W)
  last_chara = www[-1]
print(flag)

Measured memory_bytes: 3060
#include <string>
#include <assert.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char const *argv[]){
    int n, m;
    cin >> n >> m;
    vector<string> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    bool isMatch = false;
    for (int i = 0; i <= n - m; i++) {
        for (int j = 0; j <= n - m; j++) {
            isMatch = true;
            // b 
            for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                    if (a[i+k][j+l] != b[k][l]) isMatch = false;
                }
            }
            if (isMatch) break;
        }
        if (isMatch) break;
    }
    if (isMatch) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()


def ismm(s):
    pat = [i+1 for i in range(12)]
    if int(s) in pat:
        return True
    else:
        return False
s1 = S[0:2]
s2 = S[2:4]
# if s1 == '00' or s2 == '00':
#     print('NA')
#     exit(0)
if ismm(s1):
    if ismm(s2):
        #両方MM
        print('AMBIGUOUS')
    else :
        #前だけMM
        print('MMYY')
else:
    if ismm(s2):
        #後ろだけMM
        print('YYMM')
    else :
        print('NA')




    


Measured memory_bytes: 3060
s = input()
if s == 'SSS':
    print(0)
elif s == 'RSS' or s == 'SRS' or s == 'SSR' or s == 'RSR':
    print(1)
elif s == 'RRS' or s == 'SRR':
    print(2)
elif s == 'RRR':
    print(3)


Measured memory_bytes: 8952
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <map>
#include <queue>
#include <string>
using namespace std;

int prime[1000000];
bool isprime[1000001];

int sieve(int n){
	int p=0;
	for(int i=0;i<=n;i++)isprime[i]=true;
	isprime[0]=isprime[1]=false;
	for(int i=0;i<=n;i++){
		if(isprime[i]){
			prime[p++]=i;
			for(int j=i*2;j<=n;j+=i)isprime[j]=false;
		}
	}
	return p;
}

int main(){
	sieve(1e+6);
	int n;
	while(cin>>n){
		if(!n)return 0;
		int ans=0;
		for(int i=2;i<=n/2;i++)if(isprime[i]&&isprime[n-i])ans++;
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 0
# include<bits/stdc++.h>
# include<unordered_map>
# include<unordered_set>
//# include<prettyprint.hpp>
using namespace std;
# define ll long long
# define endl '\n'
int n, m;
vector<vector<int> > d;
vector<int> vis;
void bfs(int src){
    queue<int> q;
    q.push(src);
    vis[src] = 0;
    while(q.size()){
        int f = q.front();
        q.pop();
        for(auto i:d[f]){
            if (vis[i]==-1){
                vis[i] = f;
                q.push(i);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    d.resize(n);
    vis.resize(n, -1);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        a--, b--;
        d[a].push_back(b);
        d[b].push_back(a);
    }
    bfs(0);
    for(auto i:vis) if (i==-1) return cout << "No\n", 0;
    cout << "Yes" << endl;
    for(int i = 1; i < n; i++) cout << vis[i]+1 << endl;
    return 0;
}

Measured memory_bytes: 10148
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace atcoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var buffer = Console.ReadLine().Split(' ');
            int N = int.Parse(buffer[0]);
            int D = int.Parse(buffer[1]);

            int count = 0;
            for (int i = 0; i < N; i++)
            {
                double x, y;
                buffer = Console.ReadLine().Split(' ');
                x = double.Parse(buffer[0]);
                y = double.Parse(buffer[1]);

                if (Math.Sqrt(x * x + y * y) <= D)
                    count++;
            }

            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 22072
#include <iostream>

int main()
{
	int a, b, c;
	int k;
	std::cin >> a >> b >> c;
	std::cin >> k;

	for (int i_a = 0; i_a <= k; i_a++)
	{
		for (int i_b = 0; i_b <= k - i_a; i_b++)
		{
			for (int i_c = 0; i_c <= k - i_a - i_b; i_c++)
			{
				if (((a << i_a) < (b << i_b)) && ((b << i_b) < (c << i_c)))
				{
					std::cout << "Yes" << std::endl;
					return 0;
				}
			}
		}
	}
	
	std::cout << "No" << std::endl;
	return 0;
}

Measured memory_bytes: 3600
//
// Created by sark2 on 17-07-2019.
//

#include "bits/stdc++.h"

using namespace std;
#define IOS cin.sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cases int t;cin>>t;while(t--)
typedef long double ld;
typedef long long ll;
#define mod 1000000007
ll solve(vector<vector<int>>&a, int m , int n){

    ll dp[m][n];
    memset(dp,0,sizeof dp);

    for(int i = m-1; i >= 0; i--){
        if(a[i][n-1] == 0) dp[i][n-1] = 1;
        else{
            break;
        }
    }
    for(int i = n-1; i >= 0; i--){
        if(a[m-1][i] == 0) dp[m-1][i] = 1;
        else{
            break;
        }
    }

    for(int i = m-2; i >=0; i--){
        for(int j = n-2; j >=0; j--){
            if(a[i+1][j] != -1){
                dp[i][j] += dp[i+1][j]%mod;
            }
            if(a[i][j+1] != -1){
                dp[i][j] += dp[i][j+1]%mod;
            }
            dp[i][j]%=mod;
        }
    }
    return dp[0][0];

}

int main() {
    IOS

    int m,n;
    cin>>m>>n;
    char c;
    vector<vector<int>>a(m,vector<int>(n,0));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin>>c;
            if(c =='#') a[i][j] = -1;
            else a[i][j] = 0;
        }
    }

    cout<<solve(a,m,n);


}


Measured memory_bytes: 12032
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    int N;
    int score;

    pair<pair<string, int>, int> p[120];

    cin >> N;
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        cin >> score;
        p[i] = make_pair(make_pair(s, -score), i);
    }

    sort(p, p + N);

    for(int j = 0; j < N; j++){
        cout << p[j].second + 1 << endl;
    }
}

Measured memory_bytes: 256
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error("\n");
  var start = Date.now();
  Main();
  var end = Date.now() - start;
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function makeClone(obj){return JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var N = nextInt();
	if(N >= 400 && N <= 599){
		myout(8);
	}else if(N >= 600 && N <= 799){
		myout(7);
	}else if(N >= 800 && N <= 999){
		myout(6);
	}else if(N >= 1000 && N <= 1199){
		myout(5);
	}else if(N >= 1200 && N <= 1399){
		myout(4);
	}else if(N >= 1400 && N <= 1599){
		myout(3);
	}else if(N >= 1600 && N <= 1799){
		myout(2);
	}else if(N >= 1800 && N <= 1999){
		myout(1);
	}
}


Measured memory_bytes: 30164
#include <iostream>
#define REP(i, a, b) for (auto i = (a); i < (b); ++i)
using namespace std;

using ll = long long;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n;
	int a[n];
	REP(i, 0, n) cin >> a[i];
	int cur = 1;
	REP(i, 0, n)
		if (a[i] == cur) ++cur;
	// REP(i, 0, n) cerr << a[i] << ' '; cerr << '\n';
	// cerr << cur;
	if (cur == 1) cout << -1;
	else cout << n - cur + 1;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
 int main()
{
  
  int a,b;
  cin>>a>>b;

  int x=(ceil)(a/0.08);

  int y=(ceil)(b/0.1);

  int ans1=min(x,y);
  int x1=ans1*0.08;
  int y1=ans1*0.1;
int check=0;
  if(x1==a && y1==b)
  {
      cout<<ans1;
        check=1;
  }
  else if(check==0)
    {
        ans1=max(x,y);
        x1=ans1*0.08;
        y1=ans1*0.1;
        if(x1==a && y1==b)
        {
            cout<<ans1;
            check=1;
        }
    }
    if(check==0)
    cout<<-1;


  
  



}

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

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

int main() {
    int N = 0;
    cin >> N;
    vector<int> nums(N);
    
    rep(i, N) scanf("%d", &nums[i]);

    int count = 0;
    rep(i, N) { //counting numbers that is not sequential.
        if (nums.at(i) != i+1) { 
            count++;
        }
    }
    if (count<=2) printf("YES");
    else { printf("NO"); }
}

Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();

    std::io::stdin().read_to_string(&mut buf).unwrap();

    let mut iter = buf.split_whitespace();
    let a: usize = iter.next().unwrap().parse().unwrap();
    let b: usize = iter.next().unwrap().parse().unwrap();

    println!("{}", if a * b % 2 == 1 { "Yes" } else { "No" });
}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n; cin >> n;
    vvint f(n,vint(10)), p(n,vint(11));
    rep(i,n)rep(j,10) cin >> f[i][j];
    rep(i,n)rep(j,11) cin >> p[i][j];
    int ans = -inf;
    REP(i,1<<10) {
        int sum = 0;
        rep(j,n) {
            int ct = 0;
            rep(k,10) {
                if ((i>>k & 1) && f[j][k]) ct++;
            }
            sum += p[j][ct];
        }
        ans = max(ans,sum);
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N=5050;
int n,k,a[N],f[N],mx,sum,tre[N];

inline void ad(int x,int val)
{for(;x<=k;x+=(x&(-x))) tre[x]=max(tre[x],val);}

inline int get(int x)
{
	int re=0;
	for(;x;x-=(x&(-x))) re=max(re,tre[x]);
	return re;
}

int main(){
	int i,j,res;
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;++i) {scanf("%d",&a[i]);a[i]=min(a[i],k);sum+=a[i];}
	sort(a+1,a+n+1);
	for(f[0]=1,mx=0,i=n;i>=1;--i){
		sum-=a[i];if(sum<k) res=get(k-sum-1);
		mx=min(mx+a[i],k);
		for(j=mx;j>=a[i];--j) if(!f[j] && f[j-a[i]]){
			ad(j,j);f[j]=1;
		}
		if(sum>=k) continue;
		if(sum+res<k-a[i]) break;
	}
	printf("%d\n",i);		
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>


int main (void){
        long long int N,K;
        long long int ans=0;
        int over;
        int max;
        scanf("%lld %lld",&N,&K);
        if (K==0) {
                ans=N*N;
        }else{
                for (int i = K+1; i <=N; i++) {
                        ans+=(N/i+1)*(i-K);
                        over=i*(N/i+1)-N-1;
                        max=i-K;
                        if (max<over) {
                                ans-=max;
                        }else{
                                ans-=over;
                        }
                }
        }
        printf("%lld",ans);
        return 0;
}

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

A = list(map(int,input().split()))
N = A[0]
K = A[1]

Win_rate = 0
for i in range(1,N+1):
    POINT = i
    Ex_Val = 1/N
    Win_count = 0
    while K > POINT:
        POINT = POINT*2
        Win_count+=1
        
    Win_Val = (1/2)**Win_count
    Win_rate += Win_Val*Ex_Val

print(Win_rate)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

int main() {
    int A, B, K;
    cin >> A >> B >> K;
    vector<int> k;
    for (int i = 1; i <= A && i <= B; i++) {
        if (A % i == 0 && B % i  == 0) {
            k.push_back(i);
        }
    }
    cout << k[k.size() - K] << endl;
    return 0;
}



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

int main() {
  int N;
  cin >> N;
 
  for(int i=0; i<N; i++){
    string A;
    cin >> A;
    if(A=="Y"){
      cout << "Four" << endl;
      break;
    }
    if(i==N-1){
      cout << "Three" << endl;
    }
  }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000000007;
const ll INF = 1061109567;
const double EPS = 1e-10;

int main(){
	ll a[5],N;
	ll ans;
	string s;
	cin >> N;
	for (int i = 0; i < 5; i++) {
		a[i] = 0;
	}
	for (int i = 0; i < N; i++) {
		cin >> s;
		if (s[0] == 'M') {
			a[0]++;
		}
		else if (s[0] == 'A') {
			a[1]++;
		}
		else if (s[0] == 'R') {
			a[2]++;
		}
		else if (s[0] == 'C') {
			a[3]++;
		}
		else if (s[0] == 'H') {
			a[4]++;
		}
	}
	ans = a[0] * a[1] * a[2] + a[0] * a[1] * a[3] + a[0] * a[1] * a[4] + a[0] * a[2] * a[3] + a[0] * a[2] * a[4]
		+ a[0] * a[3] * a[4] + a[1] * a[2] * a[3] + a[1] * a[2] * a[4] + a[2] * a[3] * a[4] + a[1] * a[3] * a[4];
	cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
  #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl "\n"
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
	string s;
	cin>>s;
	int cnt=0;
	for(int i=0;i<(int)s.size()-1;i++){
	  if(s[i]==s[i+1]){
		   if(s[i]=='0')s[i+1]='1';
		   else s[i+1]='0'; 
		   cnt++;
		 }	
	}
	//cout<<s<<endl;
	cout<<cnt<<endl;
}
int32_t main(){
   IOS;
   solve();
   //debug();
  #ifdef LOCAL_DEFINE
   cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
  #endif	
}


Measured memory_bytes: 512
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n,m=map(int,input().split())
a=list(map(int,input().split()))
a[0]%=m
for i in range(1,n):
    a[i]=(a[i-1]+a[i])%m
a.sort()
ans=0
count=1
for i in range(n):
    if a[i]==0:
        ans+=1
for i in range(1,n):
    if a[i]==a[i-1]:
        count+=1
    else:
        if count>1:
            ans+=cmb(count,2)
        count=1
if count>1:
    ans+=cmb(count,2)
print(ans)

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

int main(void){
    int N, M;
    cin >> N >> M;
    vector<int> p(M);
    vector<string> s(M);
    for (int i = 0; i < M; i++)
        cin >> p[i] >> s[i];
        
    vector<int> accflag(N, 0);
    map<int, int> mp;
    int miss_ans = 0;
    int acc_ans = 0;
    for (int i = 0; i < M; i++) {
        if (accflag[p[i]-1] == 0 && s[i] == "WA") {
            mp[p[i]-1]++;
        }
        else if (accflag[p[i]-1] == 0 && s[i] == "AC") {
            accflag[p[i]-1] = 1;
            miss_ans += mp[p[i]-1];
            acc_ans++;
        }
    }
    cout << acc_ans << " " << miss_ans << endl;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;

int main(){
  int N,M; cin >> N >> M;
  vector<pair<int64_t,int>> drink(0);
  rep(i,N){
    int64_t a;
    int b;
    cin  >> a >> b;
    drink.push_back(make_pair(a,b));
  }

  sort(all(drink));

  int64_t ans =0;
  for(auto p:drink){
    if(M-p.second<=0){
      ans+=M*p.first;
      break;
    }else{
      ans+=p.first*p.second;
      M-=p.second;
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <tuple>
#include <thread>///////////////////

#define rep(i,m,n) for(int i=(m);i<(n);++i)
#define rem(i,m,n) for(int i=(m);i>(n);--i)
#define MOD 1000000007

using namespace std;

using ll = long long int;
using std::swap;

vector<int> v;
vector<int> w;
vector<long long int> vll;
vector<long long int> wll;
//vector<vector<int>> vec(50, vector<int>(4, 0));
vector<vector<int>> vv;

int N, Y;
int mode = 0;

//tuple<int, int, int> calc(int A, int B, int C) {}



int main() {
	string S;
	cin >> S;
	if (S == "AAA" || S == "BBB")cout << "No" << '\n';
	else cout << "Yes" << '\n';

	return 0;
}

Measured memory_bytes: 256
n = int(input())
S = []
for i in range(n):
    S.append(input())

import collections

c = collections.Counter(S)

c = dict(c)

value_c = []
for value in c.values():
    value_c.append(value)
max_c = max(set(value_c))

value = []
for item, key in c.items():
    if key == max_c:
        value.append(item)
        
value.sort()
for i in value:
    print(i)

Measured memory_bytes: 41700
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.TreeSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author KharYusuf
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CGacha solver = new CGacha();
        solver.solve(1, in, out);
        out.close();
    }

    static class CGacha {
        public void solve(int testNumber, FastReader s, PrintWriter w) {
            TreeSet<String> t = new TreeSet<>();
            int n = s.nextInt();
            while (n-- > 0) t.add(s.next());
            w.println(t.size());
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {

            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {

                curChar = 0;

                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }

            return buf[curChar++];
        }

        public int nextInt() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();

                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public String next() {

            int c = read();

            while (isSpaceChar(c))
                c = read();

            StringBuilder res = new StringBuilder();

            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {

            if (filter != null)
                return filter.isSpaceChar(c);

            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 64888
#include "bits/stdc++.h"
using namespace std;
using ll = long long; using ull = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
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>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(ll i = (ll)(n)-1;i >= 0;--i)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1);
const double EPS = 1e-10;
const ll MOD = 1e9+7;
//#define int ll
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
vvl dp;
vl w,v;
ll W;
ll n;
ll solve(ll i=0,ll j=0){
  if(j==n) return 0;
  if(dp.at(i).at(j)>=0) return dp.at(i).at(j);
  if(i+w.at(j)>W) return dp.at(i).at(j) = solve(i,j+1);
  return dp.at(i).at(j) = max(solve(i,j+1),solve(i+w.at(j),j+1)+v.at(j));
}
signed main(){
  cin >> n >> W;
  w.resize(n);
  v.resize(n);
  dp.assign(W+1,vl(n,-1));
  REP(i,n) cin >> w.at(i) >> v.at(i);
  cout << solve() << endl;
}


Measured memory_bytes: 82304
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size
#define se second
#define fe first
#define mper make_pair
#define all(x) x.begin(), x.end()
#define mal ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define vl vector<ll>
#define vi vector<int>
#define vli vector <pair <ll, int> >
#define vll vector <pair <ll, ll> >
#define vii vector <pair <int, int> >
using namespace std;

const ll MAXN = 1e5 + 100;
const ll inf = 1e-16;
ll n, k, a[MAXN], pref[MAXN], ans = inf, b[MAXN];


int main(){

//freopen("ladder.in", "r", stdin);
//freopen("ladder.out", "w", stdout);

cin >> n >> k;

for(int i = 1; i <= n; ++i) {

    cin >> a[i];
    pref[i] = pref[i - 1] + a[i];

    b[i] = b[i - 1] + max(0ll, a[i]);

}

for(int l = 1, r = l + k - 1; r <= n; ++l, ++r) {

    if(r <= n) {

        ll sum = max(pref[r] - pref[l - 1], 0ll) + max(b[l - 1] + b[n] - b[r], 0ll);

        ans = max(ans, sum);

    }

}



cout << ans;

return 0;
}


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

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

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

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

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

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

fn sum(mut n: usize) -> usize {
    let mut res = 0;
    while n > 0 {
        res += n % 10;
        n /= 10;
    }
    res
}

fn main() {
    input! {
        n: usize,
    }
    if n % sum(n) == 0 {
        println!("Yes");
    } else {
        println!("No");
    }

}


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

int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 3 != 0 and i % 5 != 0) ans += i;
    }
    
    cout << ans << '\n';
    return 0;
}

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

using namespace std ;

const int MAX = 2e5 + 10 ;

long long arr[MAX] , arr2[MAX] , pref[MAX] ;
int n , m , k ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>k ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= m ; ++i)
	{
		cin>>arr2[i] ;
		pref[i] = arr2[i] ;
		pref[i] += pref[i-1] ;
	}
	long long sum = 0 ;
	int ans = 0 ; 
	for(int i = 0 ; i <= n ; ++i)
	{
		sum += arr[i] ;
		long long x = k - sum ;
		if(x < 0)
			break ;
		int l = 0 , r = m ;
		int best = 0 ;
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			if(pref[mid] <= x)
				best = mid , l = mid+1 ;
			else
				r = mid-1 ;
		}
		ans = max(ans , i+best) ;
	}
	return cout<<ans<<"\n" , 0 ;
}		

Measured memory_bytes: 8336
#include <bits/stdc++.h>
using namespace std;
struct P
{
    //string r;
    int x,y,z;

    bool operator<(const P &a)const{
       // if(y!=a.y)
       // return y>a.y;
       return x>a.x;
//        return z>a.z;
    }
};
struct S
{
    //double a;
    int x,y;
};
vector<int> v[311210];

int a,b,c,i,k,d,n,m,e,dy[15]={0,0,-1,1,-1,1,-1,1},dx[15]={-1,1,0,0,1,1,-1,-1};
int l[55];
int o[5555];
//int dy[10]={1,0,-1,-1,-1,0},dx[10]={0,1,1,0,-1,-1};
//int dy1[10]={1,1,0,-1,0,1},dx1[10]={0,1,1,0,-1,-1};
long long x,y,z,mod=100000007;
P u[1600];
int j[5333];
queue<P> q;
//queue<int> q;
stack<int> s,s1;
//queue<P> q;

deque<int> de;
//'1'==49;
//'A'==65;
//'a'==97;
//unordered_map<int, int > p;
string r,r1;
//char r[310];
//char r1[222][555];
bool as(P a,P b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    return a.z<b.z;
}

int main()
{
    scanf("%d",&a);
    printf("%d",48-a);
}


Measured memory_bytes: 7552
N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

ans=sum(S[0:K])
temp=ans

for i in range(N-K):
    temp=temp-S[i]+S[i+K]
    if ans<temp:
        ans=temp
    else:
        pass
    
print(ans)

Measured memory_bytes: 24676
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
use proconio::{fastout, input};
#[fastout]
fn main() {
    input! {
        n: usize,
        t: usize,
        t_list: [usize; n],
    }
    let mut ans = t;

    for i in 0..t_list.len() - 1 {
        if t_list[i] + t > t_list[i + 1] {
            ans += t_list[i + 1] - t_list[i];
        } else {
            ans += t;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 5404
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    int N;
    cin >> N;
    vector<string> vec;
    for(int i=0;i<N;i++){
        string tmp;
        cin >> tmp;
        vec.push_back(tmp);
    }
    
    // 昇順ソート(1)
    for(int i=0;i<N;i++){
        sort(vec[i].begin(), vec[i].end());
    }
    // 昇順ソート(2)
    sort(vec.begin(), vec.end());

    // 組み合わせの数(nC2)を求める
    ll count = 1, ans = 0;
    for(int i=1;i<N;i++){
        if(vec[i] == vec[i-1]){
            count++;
        }else{
            ans += count*(count - 1)/2;
            count = 1;
        }
    }
    if(count >= 2)
        ans += count*(count - 1)/2;
    
    cout << ans << endl;

}

Measured memory_bytes: 7284
// Problem : AT1979 [AGC001A] BBQ Easy
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/AT1979
// Memory Limit : 250 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <algorithm>
#include <iostream>
using namespace std;
int a[ 210 ];
int main()
{
    int n;
    cin >> n;
    for ( int i = 0; i < 2 * n; i++ )
    {
        cin >> a[ i ];
    }
    sort( a, a + 2 * n );
    long long int ans = 0;
    for ( int i = 0; i < 2 * n; i += 2 )
    {
        ans += min( a[ i ], a[ i + 1 ] );
    }
    cout << ans << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define eb emplace_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"LINE %d: (%s) = ",__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }

const ll MAXn=2e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;
const ll C = 2000;
const ll M = 4e3+5;

int a[MAXn],b[MAXn];
int dp[M][M], grid[M][M];
int mod2 = 500000004;
int add(int x,int y){
    int ret = x + y;
    if (ret >= MOD) ret -= MOD;
    return ret;
}
int sub(int x,int y){
    int ret = x - y;
    if (ret < 0) ret += MOD;
    return ret;
}
int main(){
    IOS();
    int n;
    cin >> n;
    REP (i,n) {
        cin >> a[i] >> b[i];
        dp[a[i]+C][b[i]+C]++;
    }
    for (int i=2*C;i>=0;i--) {
        for (int j=2*C;j>=0;j--) {
            dp[i][j] = add(dp[i][j],add(dp[i+1][j],dp[i][j+1]));
        }
    }
    grid[0][0] = 1;
    REP (i,2*C+1) REP (j,2*C+1) {
        if (i) grid[i][j] = add(grid[i][j],grid[i-1][j]);
        if (j) grid[i][j] = add(grid[i][j],grid[i][j-1]);
    }

    ll ans = 0;
    REP (i,n) {
        ans = add(ans,dp[C-a[i]][C-b[i]]);
        ans = sub(ans,grid[2*a[i]][2*b[i]]);
    }
    ans = ans*mod2 % MOD;
    cout << ans << endl;
}


Measured memory_bytes: 130344
use proconio::{fastout, input};
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::collections::HashSet;

#[derive(Clone, Eq, PartialEq)]
struct Node {
    s: String,
    is_left: bool,
    cost: i64 
}

impl Ord for Node {
    fn cmp(&self, other: &Node) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Node) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn is_palindrome(lhs: &String, rhs: &String) -> bool {
    let (ln, rn) = (lhs.len(), rhs.len());
    let n = std::cmp::min(ln, rn);

    for i in 0..n {
        if lhs.as_bytes()[i] != rhs.as_bytes()[rn - i - 1] { return false; }
    }
    return true;
}

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize,
        Item: [(String, i64); N],
    }

    let mut heap = BinaryHeap::new();

    for item in &Item {
        heap.push(Node { s: item.0.clone(), is_left: true, cost: item.1 });
    }

    let mut lhs = HashSet::new();
    let mut rhs = HashSet::new();

    let mut res = -1;
    
    while let Some(Node { s, is_left, cost}) = heap.pop() {
        // コスト最小順で見つかった最初のコストを採用して終了
        if is_palindrome(&s, &s) { res = cost; break; }

        let cache = if is_left { &mut lhs } else { &mut rhs };
        if cache.contains(&s) { continue; }

        cache.insert(s.clone());

        for item in &Item {
            let ls = if is_left { &s } else { &item.0 };
            let rs = if is_left { &item.0 } else { &s };
            if !is_palindrome(&ls, &rs) { continue; }

            let ln = ls.len();
            let rn = rs.len();

            let ss = (if ln < rn { &rs[0..(rn - ln)] }
                              else       { &ls[rn..ln] }).to_string();

            heap.push(Node { s: ss.clone(), is_left: ln >= rn, cost: cost + item.1 });
        }
    }

    println!("{:?}", res);
}


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

#include <limits.h>

using namespace std;

typedef long long ll;

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

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

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

    for (int i = 0; i < 3; i++) {
        if (s[i] == '1') {
            cout << "9";
        } else {
            cout << "1";
        }
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
	t[i+1]=t[i]+(s[i:i+2]=='AC')
for i in range(q):
	l,r=map(int,input().split())
	print(t[r-1]-t[l-1])

Measured memory_bytes: 52056
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  ll N, M;
  cin >> N >> M;
  if (N!=1&&M!=1) cout << (N-2)*(M-2) << endl;
  else if (N==1&&M!=1) cout << M-2 << endl;
  else if (N!=1&&M==1) cout << N-2 << endl;
  else cout << 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define LOCAL
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define forn(i,a,b) for(int i=a;i<b;i++)
#define ft first
#define sd second
#define sz size()
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
//cout << fixed << setprecision(12) <<x<<endl;

int main(){
fastIO;
#ifdef LOCAL
     freopen("in.txt", "r", stdin);
#endif

string s,s1;
cin>>s>>s1;
int c=0;
forn(i,0,s.sz){
    if(s[i]!=s1[i]) c++;
}
cout<<c<<endl;
}



Measured memory_bytes: 3796
import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    k = 1
    while k*(k+1)//2 < N:
        k += 1
    if k*(k+1)//2 > N:
        k -= 1

    r = N-(k*(k+1)//2)

    for i in range(k, 0, -1):
        if i > k-r:
            print(i+1)
        else:
            print(i)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10000
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int n ;
  cin >> n ;
  int t , c ;
  t = n;
  while(true){
    c += t % 10;
    t = t/10;
    if( t == 0 ){
      break;
    }
  }
  if(n % c == 0 ){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

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

typedef long long ll;

int main(){
  int a,b;
  cin >> a >> b;
  int d = a*b;
  if(d%2 == 0) cout << "No" << endl;
  else cout << "Yes" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception{
		Scanner input = new Scanner(System.in);
		
		int count = 0;
		boolean isEven = true;
		int N = input.nextInt();
		
		int[] A = new int[N];
		
		for(int i = 0; i < N; i++) {
			A[i] = input.nextInt();
			if(A[i]%2 == 1) isEven = false;
		}
		while(isEven) {
			count++;
			for(int i = 0; i < N; i++) {
				A[i] /= 2;
				if(A[i]%2 == 1) {
					isEven = false;
					break;
				}
			}
		}
		
		System.out.println(count);
		
		
	}

}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define mtp make_tuple
#define mpr make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 1e5 + 5;
const ll maxm = 1e3 + 5;
template<class T>
inline void qwrite(T a){
	if(!a){
		putchar('0');
		return ;
	}
 	if(a < 0){
		putchar('-');
		a = -a;
	}
	if(a > 9) qwrite(a / 10);
	putchar(a % 10 + 48);
	return ;
}
template<class T>
inline T ab(T a){
	return (a > 0) ? a : -a;
}
template<class T>
inline void swa(T &a, T &b){
	a ^= b ^= a ^= b;
	return ;
}
ll cnt, a, b, c, k;
int main(){
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	cin >> a >> b >> c >> k;
	if(k >= a){
		cnt += a;
		k -= a;
	} else {
		cout << k << endl;
		return 0;
	}
	if(k >= b){
		k -= b;
	} else {
		cout << cnt << endl;
		return 0;
	}
	if(k >= c){
		cnt -= c;
	} else {
		cout << cnt - k << endl;
		return 0;
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 3632
# union-findで行けそう。

n, m = map(int, input().split())
par = [-1] * (n + 1)


def find(a):
    if par[a] < 0:
        return a
    else:
        par[a] = find(par[a])
        return par[a]


def unite(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return False
    else:
        if par[a] < par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


for i in range(m):
    x, y, z = map(int, input().split())
    unite(x, y)
cnt = 0
for i in range(n):
    if par[i + 1] < 0:
        cnt += 1
print(cnt)


Measured memory_bytes: 130648
#include<stdio.h>
#include<stdlib.h>

int main(){
  int k,a,b;
  scanf("%d%d%d",&k,&a,&b);
  
  for(int i=a;i<=b;i++){
  	if(i%k==0){
      printf("OK");
      return 0;
    }
  }
  
  printf("NG");
  return 0;
}

Measured memory_bytes: 1732