akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define IN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////
int f2(int x){
	if (x % 2 == 0) return 2;
	else return 1;
}

int main(){
	int N; SCD(N);
	static int a[100004];
	vector<int> v;

	ARSCD(a,N);
	
	sort(a,a+N);
	
	int count = 1;
	REP(i,N-1){
		if (a[i] == a[i+1]){
			count++;
		}else{
			v.PB(f2(count));
			count = 1;
		}
	}
	v.PB(f2(count)); 
	
	int one,two;
	
	REP(i,v.size()){
		if (v[i] == 1) one++;
		else two++;
	}
	
	int ans = one + 2 * (two/2);
	
	PRINTD(ans);
	
	return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
vvi E(210000);
ll n,k=0;
vector<pair<ll,ll>>pll(210000);
map<pair<ll,ll>,ll>MP;
vi ans(210000);
void dfs(int now,int par,int col){
  ll co=1;
  for(auto a:E[now]){
    //cout<<"!"<<endl;
    if(a==par)continue;
    if(co == col)co++;
    ans[MP[mp(now,a)]]=co;
    dfs(a,now,co);
    co++;
  }
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=0;i<n-1;i++){
    ll a,b;cin>>a>>b;
    a--;b--;
    pll[i]=mp(a,b);
    E[a].pb(b);
    E[b].pb(a);
    MP[mp(a,b)]=i;
  }
  for(int i=0;i<n;i++)
    k=max(k,(ll)E[i].size());
  cout<<k<<endl;
  dfs(0,-1,0);
  for(int i=0;i<n-1;i++)
    cout<<ans[i]<<endl; 
  return 0;
}


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

#define weight first
#define value second


int main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int N,W;
	cin>>N>>W;

	vector<pair<int,int>> v(N);
	sort(v.begin(),v.end());

	for (int i = 0; i < N ; i++) {
		cin>>v[i].weight>>v[i].value;
	}

	vector<long long> dp(1e5+1,W+1);
	dp[0]=0;

	for(int i = 0; i < N ; i++) {
		for (int j = 1e5; j > 0; --j)
		{
			if(j-v[i].value>=0) {
				dp[j] = min(dp[j],dp[j-v[i].value] + v[i].weight);
			}
		}
	}

	int i;
	for (i = 1e5; i >= 0  ; --i)
	{
		if(dp[i] <= W)
			break;
	}

	cout<<i;

	return 0;
}

Measured memory_bytes: 4000
def main():
    from collections import Counter
    from string import ascii_lowercase

    S = input()

    ctr = Counter(S)
    for count in ctr.values():
        if count > 1:
            print(-1)
            return

    for char in ascii_lowercase:
        if ctr[char] == 0:
            print(S + char)
            return

    lis = list(S)
    stock = []
    ma = None
    while lis:
        x = lis.pop()
        if ma is None or ma < x:
            ma = x
        stock.append(x)
        if lis and lis[-1] < ma:
            stock.sort()
            for char in stock:
                if lis[-1] < char:
                    print(''.join(lis[:-1]) + char)
                    return
    print(-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3896
#include <bits/stdc++.h>
//#include <mylib.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_EQ(i,a,b) for(int i = (a); i <= (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)
#define rep_eq(i,n) FOR_EQ(i,0,n)
#define rep_re(i,n) FOR_RE(i,n,0)

#define DEBUG_VARIABLE(variable) cout << #variable << ":" << variable << endl

#define WHITE 1//（未訪問）
#define GRAY 2//（訪問）未だに訪問していない頂点への辺を持っている。スタックに退避。
#define BLACK 3//（訪問完了）未訪問への頂点への辺を持たない
#define N 100
#define INFTY (1 << 21) //10^21
#define INF (1 << 9)
int M[N][N];//隣接行列
int color[N];

//1個上から時計周り
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//上右下左
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};
static const int NIL = -1;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
int n;

void printArray(int *array, int);
void printVector(Vector &v);
void printDimention(DVector &dv);

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

    string s_, t;
    cin >> s_ >> t;
    vector<char> s;
    bool flg;
    if(s_.size() < t.size()){
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    
    for(int i = s_.size() - t.size(); i >= 0; i--){
        flg = true;
        
        rep(j, t.size()){
            if(s_[i + j] != t[j] && s_[i + j] != '?'){
                if(i == 0){
                    cout << "UNRESTORABLE" << endl;
                    return 0;
                }
                flg = false;
                break;
            }
        }
        
        if(flg){
            rep(k, s_.size()){
                if(k < i){
                    if(s_[k] == '?'){
                        s.push_back('a');
                    }else{
                        s.push_back(s_[k]);
                    }
                }else if(i <= k && k < i + t.size()){
                    s.push_back(t[k - i]);
                }else{
                    if(s_[k] == '?'){
                        s.push_back('a');
                    }else{
                        s.push_back(s_[k]);
                    }
                }
            }
            break;
        }
    }
    
    rep(i, s.size()){
        cout << s[i];
        if(i == s.size() - 1)  cout << endl;
    }
}

//配列の表示
void printArray(int array[], int n){
    rep(i, n){
        if(i)   cout << " ";
        cout << array[i];
    }
    cout << endl;
}

//Vectorの表示
void printVector(Vector &v){
    rep(i, (int)v.size()){
        if(i)   cout << " ";
        cout << v[i];
    }
    cout << endl;
}

//二次元配列の表示
void printDimention(DVector &dv){
    rep(i, (int)dv.size()){
        rep(j, (int)dv[i].size()){
            if(j)   cout << " ";
            cout << dv[i][j];
        }
        cout << endl;
    }
}

//numの中に何個2がかかってるか
int factor2(int num){
    int cnt = 0;
    while(num % 2 == 0){
        num /= 2;
        cnt++;
    }
    return cnt;
}

Measured memory_bytes: 256
a,b = gets.split(" ").map(&:to_i)
s = gets.chomp
flag = true
s.split("").each_with_index do |x, i|
  flag = false if (i != a && !['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'].include?(x)) || (i == a && x != '-')
end
puts flag ? "Yes" : "No"

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

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0) 
#define MAXN 11111

const int INF = 1 << 29 ;
typedef long long ll ;
typedef pair < int , int > pii ;

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

int main() {
    int h , w , x , y , count ;
    char grid[55][55];
    string s ;
    
    cin >> h >> w ;
    for(int i =0 ;i<h ;i++) scanf("%s" ,grid[i]) ;

    for(int i = 0 ; i<h ;i++) {
        for(int j = 0 ; j<w ;j++) {
            if(grid[i][j] == '.') {
                count = 0 ;
                for(int k = 0 ; k<8 ; k++) {
                    x = i + dx[k] ;
                    y = j +dy[k] ;
                    if(grid[x][y] == '#') count++ ;
                }
                grid[i][j] = count + '0' ;
            }
        }
    }

    for(int i = 0 ; i<h ; i++) {
        for(int j = 0 ; j<w ; j++) 
            cout << grid[i][j] ;
        cout << endl ;
    }
    return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<int,int>
#define endl "\n"
#define MAXN 100005
#define mod 1000000007
using namespace std;

void solve()
{
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
    ll n;
    cin>>n;
    double p[n];
    for (ll i = 0; i < n; i++)
    {
        /* code */
        cin>>p[i];
    }
    vector< vector<double> > dp(n, vector<double>(n + 1, 0.0));
    dp[0][1] = p[0];
    dp[0][0] = 1 - p[0];
    double ans = 0;
    for (ll i = 1; i < n; i++)
    {
        /* code */
        for(ll j = 0; j<=(i+1); j++)
        {
            if(j == 0)
            {
                dp[i][j] = dp[i-1][j]*(1 - p[i]);
            }
            else
            {
                dp[i][j] = dp[i-1][j-1]*p[i] + dp[i-1][j]*(1 - p[i]);
            }
            if(i==(n - 1))
            {
                if(2*j > n)
                    ans = ans + dp[i][j];
            }
        }
    }
    if(n==1)
        ans = p[0];
    printf("%.10lf\n", ans);
}

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

ll ADP[100005], ABDP[100005], ABCDP[100005];

int main() {
  string S;
  cin>>S;
  ll num = 1;
  if(S[0]=='A') ADP[0] = 1;
  if(S[0]=='?') {
    ADP[0] = 1;
    num *= 3;
  }
  for(int i=1;i<S.size();++i) {
    if(S[i]=='A') {
      ADP[i] = (ADP[i-1]+num)%mod;
      ABDP[i] = ABDP[i-1];
      ABCDP[i] = ABCDP[i-1];
    }
    if(S[i]=='B') {
      ADP[i] = ADP[i-1];
      ABDP[i] = (ADP[i-1]+ABDP[i-1])%mod;
      ABCDP[i] = ABCDP[i-1];
    }
    if(S[i]=='C') {
      ADP[i] = ADP[i-1];
      ABDP[i] = ABDP[i-1];
      ABCDP[i] = (ABCDP[i-1]+ABDP[i-1])%mod;
    }
    if(S[i]=='?') {
      ADP[i] = (ADP[i-1]*3%mod+num)%mod;
      ABDP[i] = (ADP[i-1]+ABDP[i-1]*3%mod)%mod;
      ABCDP[i] = (ABCDP[i-1]*3%mod+ABDP[i-1])%mod;
      num *= 3;
      num %= mod;
    }
  }
  cout<<ABCDP[S.size()-1]<<endl;
}



Measured memory_bytes: 6104
#include<bits/stdc++.h>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> vvi;
typedef std::vector<long long> vl;
typedef std::vector<std::vector<long long>> vvl;
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;
 
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;
}


ll gcd(ll n, ll m) {
    ll tmp;
    while (m!=0) {
        tmp = n % m;
        n = m;
        m = tmp;
    }
    return n;
}
 
ll lcm(ll n, ll m) {
    return abs(n) / gcd(n, m)*abs(m);//gl=xy
}

using namespace std;

void solve()
{
  ll n, m;
  cin >> n >> m;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];
  vector<bool> v(n,true);
  rep(i, m)
  {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if(h[a]>h[b]){
      v[b] = false;
    }
    else if(h[a]<h[b]){
      v[a] = false;
    }
    else {
      v[a] = false;
      v[b] = false;
    }
  }
  int ans = 0;
  rep(i, n)
  {
    if(v[i])
      ++ans;
  }
  cout << ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(15);
    solve();
    return 0;
}



Measured memory_bytes: 3992
#include <iostream>
#define COST_MAX 1000000

using namespace std;

int main() {
  int n;
  int m;
  while(1) {
    cin >> n;
    if(n == 0) break;
    cin >> m;

    int dist[n][n];
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
	dist[i][j] = COST_MAX;
      }
    }

    for(int i = 0; i < m; i++) {
      int a, b, d;
      scanf("%d,%d,%d", &a, &b, &d);
      dist[a][b] = dist[b][a] = d;
    }

    int cost[n];
    bool visited[n];
    for(int i = 0; i < n; i++) {
      cost[i] = COST_MAX;
      visited[i] = false;
    }
    cost[0] = 0;
    int pre[n];

    while(1) {
      int min = COST_MAX;
      int p;
      for(int i = 0; i < n; i++) {
	if(!visited[i] && cost[i] < min) {
	  min = cost[i];
	  p = i;
	}
      }
      if(min == COST_MAX) break;

      visited[p] = true;
      for(int i = 0; i < n; i++) {
	if(!visited[i] && dist[i][p] < cost[i]) {
	  cost[i] = dist[i][p];
	  pre[i] = p;
	}
      }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
      if(cost[i] == 0) continue;
      ans += cost[i] / 100 - 1;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main(){
	char a, b;
	scanf("%c %c", &a, &b);
	if(a == 'H'){
		if(b == 'H'){
			printf("H");
		}else{
			printf("D");
		}
	}else{
		if(b == 'H'){
			printf("D");
		}else{
			printf("H");
		}
	}
	return 0;
}

Measured memory_bytes: 128
process.stdin.resume();
process.stdin.setEncoding('utf8');
var lines = [];
var reader = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout,
    terminal: false
});
reader.on('line', (line) => {
    lines.push(line);
});
reader.on('close', () => {
    const a = parseInt(lines[0]);
    console.log(a + Math.pow(a,2) + Math.pow(a,3));
});

Measured memory_bytes: 30128
#include <stdio.h>
#define N 100

int main(){

  int m[N][N];
  int n,u,k,v;
  int i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++) m[i][j]=0;
  }

  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      m[u][v]=1;
    }
  }

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j) printf(" ");
      printf("%d",m[i][j]);
    }
    printf("\n");
  }

  return 0;
}

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

int main(){
  string s;
  cin >>s;
  int i;
  int n=s.size();
  int k=0,l=n;
  for(i=0;i < n;i++) {
    if(s[i]=='A') break;
    else k++;
  }
  for(i=0;i < n;i++) {
    if(s[n-i]=='Z') break;
    else l--;
  }
 cout <<l-k+1;
}


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

typedef long long int ll;
typedef pair<ll,ll> P;

int main(){
    string s;
    cin>>s;
    if(s.size()%2){cout<<"No"<<endl;return 0;}
    for(int i=0;i<s.size()/2;i++){
        if(s[i*2]=='h'&&s[i*2+1]=='i'){
            
        }else{
            cout<<"No"<<endl;return 0;
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}

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

int main(int argc, char *argv[]) {
  // read inputs
  int A, B;
  scanf("%d %d", &A, &B);
  // solve
  if (A >= 13) {
    printf("%d\n", B);
  } else if (A >= 6) {
    printf("%d\n", B / 2);
  } else {
    printf("0\n");
  }
  
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int count(int);
int main(void){
    int n,x;
    while(1){
        cin >> n;
        if(n==0) break;

        x=count(n)/10;
        cout << x/365+1 << endl;
    }
}

int count(int n){
    if(n==1) return 1;
    else if(n==2) return 2;
    else if(n==3) return 4;
    else return count(n-1)+count(n-2)+count(n-3);
}


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

int main(){
    char b;
    cin >> b;
    if(b == 'A') cout << 'T' << endl;
    if(b == 'C') cout << 'G' << endl;
    if(b == 'G') cout << 'C' << endl;
    if(b == 'T') cout << 'A' << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    int H,W;
    int i,j;

    while(1){
        scanf("%d %d", &H,&W);
        if (H == 0 &&  W == 0){
            break;
        }
        else{
            for (i = 0; i < H; i ++){
                for (j = 0; j < W; j++){
                    printf("#");
                }
                printf("\n");
            }
            printf("\n");
        }
    }
    return(0);
}

Measured memory_bytes: 572
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAX = 100100;

vector<pair<int, int>> E[MAX];

int a[MAX];
int sa[MAX];

void Dfs(int x, int prev, int dad) {
  for (auto& p: E[x]) {
    int y = p.first;
    int w = p.second;
    if (y != dad) {
      Dfs(y, w, x);
      sa[x] ^= sa[y];
    }
  }

  a[x] = sa[x] ^ prev;
  sa[x] = sa[x] ^ a[x];

}

int main(void) {
  int N;
  scanf("%d", &N);
  REP(i, N-1) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    E[a].push_back({b, c});
    E[b].push_back({a, c});
  }

  Dfs(0, 0, -1);

  int mask = 0;
  int ret = 0;
  FOR(i, 1, N) {
    if (a[i] == 0) continue;
    if (mask & (1<<a[i])) {
      ret++;
    }
    mask ^= 1 << a[i];
  }

  queue<int> Q[16];
  vector<int> dist(1<<16, 1000000000);

  dist[mask] = 0;
  Q[0].push(mask);

  REP(i, 16) {
    while (!Q[i].empty()) {
      int mask = Q[i].front();
      Q[i].pop();
      if (i != dist[mask]) continue;

      REP(x, 16) {
        if (mask & (1<<x)) {
          if (i + 1 < 16) {
            int nmask = mask ^ (1 << x);
            if (i + 1 < dist[nmask]) {
              dist[nmask] = i + 1;
              Q[i + 1].push(nmask);
            }
          }


          REP(y, x) {
            if ((mask & (1<<y))) {
              REP(z, 16) {
                int nmask = mask, cost = i;

                nmask ^= 1 << x;
                nmask ^= 1 << y;
                cost++;

                if (x != z) {
                  if (nmask & (1 << (x^z))) cost++;
                  nmask ^= 1 << (x^z);
                }

                if (y != z) {
                  if (nmask & (1 << (y^z))) cost++;
                  nmask ^= 1 << (y^z);
                }
                if (cost < 16 && cost < dist[nmask]) {
                  dist[nmask] = cost;
                  Q[cost].push(nmask);
                }
              }
            }
          }
        }
      }
    }
  }

  ret += dist[0];
  printf("%d\n", ret);
  return 0;
}


Measured memory_bytes: 14208
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <climits>
#include <memory>
#include <sstream>
#include <iomanip>

using namespace std;


int main() {

	string n;
	cin >> n;
	int ans = 0;
	for (int i = 0; i < n.size(); i++) {
		if (n[i] == '2')ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

string s[2010];

struct CumulativeSum2D{
    vector<vector<int> > data;
    CumulativeSum2D(int H, int W) : data(H + 1, vector<int>(W + 1, 0)) {}
    //要素(x,y)に値zを加える
    void add(int x, int y, int z){
        ++x, ++y;
        if(x >= data.size() || y >= data[0].size()) return;
        data[x][y] += z;
    }
    void build(){
        for(int i = 1; i < data.size(); i++) {
        for(int j = 1; j < data[i].size(); j++) {
            data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
            }
        }
    }
    //左上[sy, sx], 右下(gx, gy)の矩形内の和を求める(半開区間) (0-index)
    int query(int sx, int sy, int gx, int gy){
        return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
    }
};

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    rep(i, 0, n){
        cin >> s[i];
    }
    CumulativeSum2D cs(n, m), yoko(n, m - 1), tate(n - 1, m);
    rep(i, 0, n){
        rep(j, 0, m){
            cs.add(i, j, s[i][j] == '1');
        }
    }
    rep(i, 0, n){
        rep(j, 0, m - 1){
            if(s[i][j] == s[i][j + 1] && s[i][j] == '1'){
                yoko.add(i, j, 1);
            }
        }
    }
    rep(j, 0, m){
        rep(i, 0, n - 1){
            if(s[i][j] == s[i + 1][j] && s[i][j] == '1'){
                tate.add(i, j, 1);
            }
        }
    }
    cs.build();
    yoko.build();
    tate.build();
    rep(i, 0, q){
        int x1, y1, x2, y2;
        cin >> y1 >> x1 >> y2 >> x2;
        x1--; y1--; x2--; y2--;
        int num = cs.query(y1, x1, y2 + 1, x2 + 1);
        int y = yoko.query(y1, x1, y2 + 1, x2);
        int t = tate.query(y1, x1, y2, x2 + 1);
        int ans = num - y - t;
        cout << ans << endl;
    }
}

Measured memory_bytes: 100224
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<math.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); i++)

int main(){
    int a, b;
    cin >> a >> b;
    cout << (6 - a - b) << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		int N = int.Parse(str[0]);
		int A = int.Parse(str[1]);
		int B = int.Parse(str[2]);
		int C = int.Parse(str[3]);
		int[]D = new int[N];
		for(var i=0;i<N;i++){
			D[i] = int.Parse(Console.ReadLine());
		}
		int ans = 999999999;
		for(var i=0;i<(int)Math.Pow(4,N);i++){
			var lista = new List<int>();
			var listb = new List<int>();
			var listc = new List<int>();
			for(var j=0;j<N;j++){
				int a = i/(int)Math.Pow(4,j)%4;
				if(a==0){
					lista.Add(D[j]);
				} else if(a==1){
					listb.Add(D[j]);
				} else if(a==2){
					listc.Add(D[j]);
				}
			}
			if(lista.Count>0 && listb.Count>0 && listc.Count>0){
				int suma = 0;
				int mp = 0;
				for(var j=0;j<lista.Count;j++){
					suma += lista[j];
				}
				mp += (lista.Count-1)*10;
				mp += Math.Abs(suma-A);
				int sumb = 0;
				for(var j=0;j<listb.Count;j++){
					sumb += listb[j];
				}
				mp += (listb.Count-1)*10;
				mp += Math.Abs(sumb-B);
				int sumc = 0;
				for(var j=0;j<listc.Count;j++){
					sumc += listc[j];
				}
				mp += (listc.Count-1)*10;
				mp += Math.Abs(sumc-C);
				ans = Math.Min(mp,ans);
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 15300
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <cstdlib>
#include <typeinfo>

using namespace std;

#define FOR(i,n) for(i=0;i<n;++i)

int i,j;

int main(void){
    
    string s;
    cin >> s;
    bool alp[26];
    FOR(i,26) alp[i]=false;
    
    FOR(i,s.length()){
        
        if(alp[s[i]-'a']){
            cout<<"no";
            return 0;
        }
        
        alp[s[i]-'a']=true;
        
    }
    
    cout<<"yes";
    return 0;
    
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
	int w, n;
	scanf("%d", &w);
	int *l = new int[w];
	for(int i = 0; i < w; i++){
		l[i] = i + 1;
	}
	scanf("%d", &n);
	int a, b;
	for(int i = 0; i < n; i++){
		scanf("%d,%d", &a, &b);
		int temp = l[a - 1];
		l[a - 1] = l[b - 1];
		l[b - 1] = temp;
	}
	for(int i = 0; i < w; i++){
		printf("%d\n", *(l++));
	}
	return 0;
}


Measured memory_bytes: 2668
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<typename T> using v2 = vector<vector<T>>;
template<typename T> using v3 = vector<vector<vector<T>>>;
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 200;
const ll INFLL = 2e18 + 200;

struct info {
    vector<ll> contest, minus;
    ll score;

    info(ll value) {
        contest = vector<ll>();
        minus = vector<ll>(26, 0);
        score = value;
    }

    info() {
        contest = vector<ll>();
        minus = vector<ll>(26, 0);
        score = 0;
    }
};

int main() {
    ll D;
    cin >> D;
    vector<ll> c(26);
    cin >> c;
    vector<vector<ll>> satisfaction(26, vector<ll>(D + 1));
    for (int i = 1; i <= D; i++) {
        for (int j = 0; j < 26; j++) {
            ll temp;
            cin >> temp;
            satisfaction[j][i] = temp;
        }
    }
    vector<vector<info>> dp(D + 1, vector<info>(26));
    for (int day = 1; day <= D; day++) {
        for (int now = 0; now < 26; now++) {
            for (int before = 0; before < 26; before++) {
                auto before_info = dp[day - 1][before];
                for (int i = 0; i < 26; i++) {
                    before_info.minus[i] += c[i];
                }
                before_info.contest.push_back(now);
                before_info.minus[now] = 0;
                before_info.score += satisfaction[now][day];
                for (int i = 0; i < 26; i++) {
                    before_info.score -= before_info.minus[i];
                }
                if (dp[day][now].contest.empty()) {
                    dp[day][now] = before_info;
                    continue;
                }
                if (dp[day][now].score < before_info.score) dp[day][now] = before_info;
            }
        }
    }
    auto ans = dp[D][0];
    for (int i = 0; i < 26; i++) {
        if (ans.score < dp[D][i].score) ans = dp[D][i];
    }
    for (int i = 0; i < D; i++) {
        cout << ans.contest[i] + 1 << endl;
    }
}


Measured memory_bytes: 20284
using System;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var T = new int[100000];
            var X = new int[100000];
            var Y = new int[100000];
            for (int i = 0; i < N; i++)
            {
                var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                T[i] = input[0];
                X[i] = input[1];
                Y[i] = input[2];
            }

            for (int i = 0; i < N; i++)
            {
                if ((X[i] + Y[i]) > T[i])
                {
                    Console.WriteLine("No");
                    return;
                }

                if (T[i] % 2 == 0)
                {
                    if ((X[i] + Y[i]) % 2 != 0)
                    {
                        Console.WriteLine("No");
                        return;
                    }
                }
                else
                {
                    if ((X[i] + Y[i]) % 2 == 0)
                    {
                        Console.WriteLine("No");
                        return;
                    }
                }
            }
            Console.WriteLine("Yes");
        }
    }
}



Measured memory_bytes: 18400
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)(a);i<=(sign)(b);++i)
#define Fordown(i,a,b) for(register sign i=(sign)(a);i>=(sign)(b);--i)
const int N=1e5+5;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
#endif
}
int n,m;
void input()
{
	n=read<int>(),m=read<int>();
}
int num[N],may[N];
void work()
{
	int x,y;
	For(i,1,n)num[i]=1;
	may[1]=1;
	For(i,1,m)
	{
		x=read<int>(),y=read<int>();
		--num[x],++num[y];
		if(may[x])may[y]=1;
		if(!num[x])may[x]=0;
	}
	int ans=0;
	For(i,1,n)ans+=may[i];
	write(ans,'\n');
}
int main()
{
	//file();
	input();
	work();
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int main(){
  int N;
  cin>>N;
  vector<long long>  data(N);
  vector<long long> kazu(N,0);
  rep(i,N){
    cin>>data.at(i);
    kazu.at(data.at(i)-1)++;
  }
  long long pattern=0;
  rep(i,N){
    if(kazu.at(i)>1){
      pattern+=kazu.at(i)*(kazu.at(i)-1)/2;
    }
  }
  rep(i,N){
    if(kazu.at(data.at(i)-1)==0||kazu.at(data.at(i)-1)==1){
      cout<<pattern<<endl;
    }else{
      cout<<pattern-kazu.at(data.at(i)-1)+1<<endl;
    }
  }
}


Measured memory_bytes: 5760
#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
	int i = 0;
	int j = 0;
	int flag = 0;
	int print = 0;
	int N = 0;
	
	cin>>N;
	for(i=1;i<=N;i++)
	{
		
		for(j=1;j<=i;j++)
		{
			if(i%2 == 0)
			{
				break;
			}
			if(i%j==0)
			{
				flag = flag + 1;
			}
			
			if(flag==8)
			{
				print = print + 1;
			}
		}
		flag = 0;
	}
	cout<<print;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static int n,m,s,g,money,pillar;
	static int[][] edge;
	static int[][] min;
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		n=cin.nextInt();
		m=cin.nextInt();
		edge=new int[n+1][n+1];
		min=new int[n+1][2];
		for(int i=0;i<=n;i++){
			min[i][0]=min[i][1]=1<<30;
		}
		for(int i=0;i<=n;i++){
			Arrays.fill(edge[i], 1<<30);
		}
		for(int i=1;i<=m;i++){
			String[] s = cin.next().split(",");
			
			int a=Integer.parseInt(s[0]);
			int b=Integer.parseInt(s[1]);
			int c=Integer.parseInt(s[2]);
			int d=Integer.parseInt(s[3]);
			edge[a][b]=c;
			edge[b][a]=d;
		}
		String[] ss = cin.next().split(",");
		s=Integer.parseInt(ss[0]);
		g=Integer.parseInt(ss[1]);
		money=Integer.parseInt(ss[2])-Integer.parseInt(ss[3]);
		PriorityQueue<int[]> q = new PriorityQueue<int[]>(100,new Comparator<int[]>(){
			public int compare(int[] a,int [] b){
				return a[1]-b[1];
			}
		});
		q.add(new int[]{s,0});
		min[s][0]=0;
		while(!q.isEmpty()){
			int[] p = q.poll();
			int now=p[0];
			int cost=p[1];
			for(int i=1;i<=n;i++){
				if(edge[now][i]!=1<<30){
					if(min[i][0]>cost+edge[now][i]){
						min[i][0]=cost+edge[now][i];
						q.add(new int[]{i,min[i][0]});
					}
				}
			}
		}
		
		q.add(new int[]{g,0});
		min[g][1]=0;
		while(!q.isEmpty()){
			int[] p = q.poll();
			int now=p[0];
			int cost=p[1];
//			System.out.println(now+" "+cost);
			for(int i=1;i<=n;i++){
				if(edge[now][i]!=1<<30){
					if(min[i][1]>cost+edge[now][i]){
						min[i][1]=cost+edge[now][i];
						q.add(new int[]{i,min[i][1]});
					}
				}
			}
		}
		System.out.println(money-min[g][0]-min[s][1]);
	}
}

Measured memory_bytes: 15348
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    string S;
    cin >> S;
    const int N = S.size();
    vector<int> ans(N, 0);
    rep(i, 0, N - 1)
    {
        if (S[i] == 'R' && S[i + 1] == 'L')
        {
            int j = i;
            while (S[j] == 'R')
            {
                if ((i - j) % 2 == 0) ++ans[i];
                else ++ans[i + 1];
                --j;
            }

            j = i + 1;
            while (S[j] == 'L')
            {
                if ((j - (i + 1)) % 2 == 0) ++ans[i + 1];
                else ++ans[i];
                ++j;
            }
        }
    }
    rep(i, 0, N)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 1104
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int N; cin >> N;
    int t = 1;
    int cnt = 1;
    int ans  = 1;
    while(t <= N){
        t  = (1LL << cnt);
        ++cnt;
        if(t > N){
            cout << ans << endl;
            return 0;
        } else {
            ans = t;
        }
    }
}


Measured memory_bytes: 256
N=int(input())
T,A=map(int,input().split())
H=list(map(int,input().split()))
no=0
noabs=100000.0
for i in range(N):
    NT=T-H[i]*0.006
    if noabs>=abs(NT-A):
        no=i+1
        noabs=abs(NT-A)
print(no)

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

int main()
{
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    rep (i, n) cin >> p[i];
    rep (i, n) cin >> q[i];
    vector<int> one_case;

    for (int i = 1; i <= n; i++) one_case.emplace_back(i);

    int a = 0, b = 0;
    int cnt = 0;
    do {
        int i = 0, aflag = 0, bflag = 0;
        cnt++;
        for (auto num : one_case) {
            if (num == p[i]) aflag++;
            if (num == q[i]) bflag++;
            i++;
        }
        if (aflag == n) a = cnt;
        if (bflag == n) b = cnt;
    } while (next_permutation(one_case.begin(), one_case.end()));

    cout << abs(a-b) << endl;
    return 0;
}

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

int main(){
    string s;
    int ans, t;
    
    cin >> s;
    ans = 1000;
    for ( int i = 2;i < s.size(); i++ ) {
        t = (s[i-2] - '0') * 100 + (s[i-1] - '0') * 10 + s[i] - '0';
        
        ans = min(ans, abs(t-753));
    }
    cout << ans << endl;
    
    return (0);
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
 
template <class T> using V = vector<T>;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
 
const long long INF = 1LL << 60;
 
using ll = long long;
using vll = V<ll>;
 
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)

/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  int n,k;
    cin>>n>>k;
  vll A(n);
  FOR(i,0,n){
    cin>>A[i];
  }

  ll ans=INF;
  FOR(i,0,n-k+1){
    ll now;
    if(A[i]*A[i+k-1]<0){
      now=2*min(abs(A[i]),abs(A[i+k-1]))+max(abs(A[i]),abs(A[i+k-1]));
    }
    else{
      now=max(abs(A[i]),abs(A[i+k-1]));
    }
    chmin(ans,now);
  }

  cout<<ans<<endl;
}


Measured memory_bytes: 1024
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static AtCoder.Program;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            new ABC132().SolveA(new ConsoleInput(Console.In, ' '));
        }

    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }

    }
  class ABC132
  {
    public void SolveA(ConsoleInput cin)
        {
            var S = cin.Read.ToCharArray();
            var sortedS = S.OrderBy(x => x).ToArray();
            if (sortedS[0] == sortedS[1] && sortedS[2] == sortedS[3] && sortedS[0] != sortedS[2]) WriteLine("Yes");
            else WriteLine("No");
            ReadLine();

        }
  }
}

Measured memory_bytes: 13396
S = list(input())
T = list(input())


ans = 0
for j in range(len(S)-len(T)+1):
    can = True
    SS = S[:]
    for i, t in enumerate(T):
        s = S[j+i]
        if s != '?' and s != t:
            can = False
            break
        elif s == '?':
            SS[j+i] = t
    if can:
        ans = SS

if ans == 0:
    print('UNRESTORABLE')
else:
    Ans = ans[:]
    for i, a in enumerate(ans):
        if a == '?':
            Ans[i] = 'a'
    print(''.join(Ans))

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define INF ((1LL<<62)-(1LL<<31))
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
#define invp(a,p)pom(a,p-2,p)
#define MOD 1000000007

int cmp(const void*aa, const void*bb){
	ll a=llabs(*(ll*)aa);
	ll b=llabs(*(ll*)bb);
	return a<b?1:a>b?-1:0;
}

ll a[200010];
int main(){
	int n,k;
	scanf("%d%d",&n,&k);
	rep(i,0,n)scanf("%lld",a+i);
	//絶対値の降順にソート
	qsort(a,n,sizeof(ll),cmp);
	
	//Kが奇数かつ全てが負
	int neg=1;
	rep(i,0,n)if(a[i]>=0)neg=0;
	if(neg&&k%2==1){
		ll ans=1;
		for(int i=n-1;i>=n-k;i--)ans=ans*(MOD+a[i])%MOD;
		printf("%lld",ans);
		return 0;
	}
	
    //絶対値上位K個の積を計算する
	ll ans=1;
	int sign=0,zero=0;
	rep(i,0,k){
		ans=ans*a[i]%MOD;
		if(a[i]<0)sign^=1;
		if(a[i]==0)zero=1;
	}
	
	//K=Nのときと、絶対値上位K個の積が非負のとき
	if(sign==0||zero||k==n){
		printf("%lld",(ans+MOD)%MOD);
		return 0;
	}
	
	//使ったもののうち、正で絶対値最小、負で絶対値最小を探す
	ll p1=INF,m1=INF;
	rep(i,0,k){
		if(a[i]<0)m1=a[i];
		else p1=a[i];
	}
	
	//使っていないもののうち、非負で絶対値最大、負で絶対値最大を探す
	ll p2=INF,m2=INF;
	for(int i=n-1;i>=k;i--){
		if(a[i]<0)m2=a[i];
		else p2=a[i];
	}
	
	if(p2==INF){
		// 正の数を抜いて負の数を入れるしかない
		ans=ans*invp(p1,MOD)%MOD*(MOD+m2)%MOD;
	}else if(m2==INF || p1==INF){
		// 負の数を抜いて非負の数を入れるしかない
		ans=ans*invp(MOD+m1,MOD)%MOD*p2%MOD;
	}else{
		// 正の数を抜いて負の数を入れる・負の数を抜いて非負の数を入れる
		// どちらがいいか選ぶ
		if(p2*p1>=m2*m1){//p2/m1>=m2/p1
			// 負の数を抜いて非負の数を入れる
			ans=ans*invp(MOD+m1,MOD)%MOD*p2%MOD;
		}else{
			// 正の数を抜いて負の数を入れる
			ans=ans*invp(p1,MOD)%MOD*(MOD+m2)%MOD;
		}
	}
	printf("%lld\n",(ans+MOD)%MOD);
}

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

int main(){
    string s;
    cin >> s;
    int n = s.size();
    string ans = s.substr(0, n - 8);
    cout << ans << endl;
}

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

int main() {
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int A = x2 - x1;
    int B = y2 - y1;
    cout << x2 - B << " " << y2 + A << " " << x2 - B - A << " " << y2 + A - B << endl;
}

Measured memory_bytes: 256
mod=998244353

def cmb(n,r):
  if r<0 or r>n:
    return 0
  return (g1[n]*g2[r]*g2[n-r])%mod

g1=[1,1]
g2=[1,1]
inv=[0,1]
for i in range(2,1000003):
  g1.append((g1[-1]*i)%mod)
  inv.append((-inv[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inv[-1])%mod)

N,K=map(int,input().split())
P=0
for k in range(N-1,K):
  P=(P+cmb(K-1,k))%mod
print(P)

Measured memory_bytes: 212896
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

int main(void){
    int n, k, q;
    cin >> n >> k >> q;

    vector<int> a(q);

    vector<int> pt(n, 0);
    for(int i = 0; i < q; i++){
        int a;
        cin >> a;
        a--;
        pt[a]++;
    }

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

    for(int i = 0; i < n; i++){
        if(k - (q - pt[i]) > 0){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
using namespace std;
int main(){

    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];
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(a[i][j]!=b[0][0])continue;
            bool f = 1;

            for(int k=0; k<m; k++){
                for(int l=0; l<m; l++){
                    if(i+k>=n || j+l>=n || a[i+k][j+l]!=b[k][l]){
                        f = 0;
                        break;
                    }
                }
            }

            if(f){
                puts("Yes");
                return 0;
            }

        }
    }

    puts("No");

    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;
typedef long long lint;

const int MAXN = 111;
int dp[2][3*MAXN][MAXN];

void chmax(int& a, const int& b) {
    a = max(a, b);
}

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 0; i < 3*MAXN; i++) {
        for (int j = 0; j < MAXN; j++) {
            dp[0][i][j] = dp[1][i][j] = -1000 * 1000 * 1000;
        }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i < N; i++) {
        const int cur = i%2, tar = cur^1;
        int cost = w[i] - w[0];
        for (int j = 0; j < 3*N; j++) {
            for (int cnt = 0; cnt < N; ++cnt) {
                chmax(dp[tar][j+cost][cnt+1], dp[cur][j][cnt] + v[i]);
                chmax(dp[tar][j][cnt], dp[cur][j][cnt]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        lint loss = W - (lint)i * w[0];
        if (loss < 0) break;
        int rest = min<int>(loss, 3*N);
        int maxi = 0;
        for (int j = 0; j <= rest; j++) {
            for (int k = 0; k <= i; k++) {
                chmax(ans, dp[N%2][j][k]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

A, B, Q = I()
inf = float("inf")
s = [-inf]+sorted([k() for _ in range(A)])+[inf]
t = [-inf]+sorted([k() for _ in range(B)])+[inf]
aa = []

for i in range(Q):
    q = k()
    S = bisect.bisect(s,q)
    T = bisect.bisect(t,q)
    ans = inf
    for j in [s[S-1],s[S]]:
        for z in [t[T-1],t[T]]:
            x = abs(j-q)+abs(j-z)
            y = abs(z-q)+abs(j-z)
            ans = min(ans,x,y)
    aa.append(ans)

for i in aa:
    print(i)


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;

int main(){
  int N,A,B; cin>>N>>A>>B;
  cout<<min(B,A*N)<<endl;
  return 0;
}

Measured memory_bytes: 256