akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;

int N;
int ans[100010];

struct edge { int to; int cost; };
struct sets { int v, p, d; };
vector<edge> tree[100010];


void bfs(int v,int p,int d) {

	queue<sets> q;
	q.push(sets{ v,p,d });

	while (!q.empty()) {
		sets cur = q.front();
		q.pop();

		ans[cur.v] = cur.d;
		for (int i = 0; i < tree[cur.v].size(); i++) {
			edge e = tree[cur.v][i];
			if (e.to == cur.p)
				continue;

			q.push(sets{ e.to,cur.v,cur.d + e.cost });
		}
	}
}



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


	cin >> N;

	REP(i, N - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		tree[a].push_back(edge{ b,c });
		tree[b].push_back(edge{ a,c });
	}

	int Q, K;
	cin >> Q >> K;
	K--;

	bfs(K,-1,0);

	REP(i, Q) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		cout << ans[x] + ans[y] << endl;
	}

	return 0;
}



Measured memory_bytes: 10480
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int SUM(int m){
    
    int sum = 0;
    for (int i = 1; i <= m; ++i) {
        sum += i;
    }
    return sum;
} 

int main() {
    int a,b; cin >> a >> b;
    
    print(SUM(b - a) - b);
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	if(N%2==0) {
		cout<<0.5<<endl;
	}
	else {
		_P("%.12lf\n",(N+1)/(2.0*N));
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define FOR(i,a,b) for (int i=(a),for_##i##_max=(b);i<=(for_##i##_max);++i)
#define RFOR(i,a,b) for (int i=(a),rfor_##i##_min=(b);i>=(rfor_##i##_min);--i)
#define REP(i,n) for (int i=0,rep_##i##_len=(n);i<(rep_##i##_len);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

namespace { // Basics

template<typename T>
void chmin(T &x, T y) {
  x = std::min(x, y);
}

template<typename T>
void chmax(T &x, T y) {
  x = std::max(x, y);
}

template<typename T>
__attribute__((unused))
const auto minimum = static_cast<T const &(*)(T const &, T const &)>(std::min);

template<typename T>
__attribute__((unused))
const auto maximum = static_cast<T const &(*)(T const &, T const &)>(std::max);

template<typename T>
int cmp3(T lhs, T rhs) { return (lhs == rhs) ? 0 : (lhs > rhs) ? 1 : -1; }

template<typename T>
__attribute__((unused))
T constexpr infty = std::numeric_limits<T>::max / 3;
template<>
__attribute__((unused))
auto constexpr infty<int> = 1'100'100'100;
template<>
__attribute__((unused))
auto constexpr infty<long long int> = 100'500'400'300'200'100LL;

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

} // namespace

using namespace std;

bool solve(vector<tuple<int,int,int,int>> const &S) {
  lli level = 0;
  for (auto &&t : S) {
    int lowst = get<2>(t), tot = get<3>(t);
    if (level + lowst < 0) {
      return false;
    }
    level += tot;
  }
  return level == 0;
}

int main() {
  // cout << fixed << setprecision(10);

  int N;
  cin >> N;
  vector<tuple<int,int,int,int>> S;
  REP(i, N) {
    string row;
    cin >> row;
    int lowst = 0, tot = 0;
    for (char c : row) {
      tot += (c == '(' ? 1 : -1);
      chmin(lowst, tot);
    }
    if (tot >= 0) {
      S.emplace_back(100, -lowst, lowst, tot);
    } else {
      S.emplace_back(101, lowst-tot, lowst, tot);
    }
  }
  sort(begin(S), end(S));
  cout << (solve(S) ? "Yes" : "No") << endl;
  return 0;
}


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

int main(){
	int n,c=0,i=0;
	cin>>n;
	while(n!=c){
		c=0;
		i++;
		for(int j=1; j<=i;j++){
			if(i%j==0) c++;
		}
	}
	cout<<i<<endl;
	return 0;
}


Measured memory_bytes: 3084
// Abu Hurayra (HurayraIIT)
// IIT, Jahangirnagar University

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;

typedef long long LL;
typedef long long int int64;
typedef unsigned long long int  uint64;
typedef vector<int> vi; 

#define READ freopen("input.txt", "r", stdin);
#define WRITE freopen("output.txt", "w", stdout);
#define fast_io ios_base::sync_with_stdio(0);  cin.tie(0);
#define sz(a) int((a).size())
#define space " "
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define pi acos(-1.0)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define MOD 1000000007
#define PRECISION(x) cout << fixed << setprecision(x); 
 
 
int main()
{
    fast_io
    
    int n,i,j,k,s=0;
    cin >> n ;
    int a[n];
    for(i=0;i<n;i++)
    {
        cin  >> a[i];
    }
    //sort(a,a+n);
    for(i=0;i<n-2;i++)
    {
        for(j=i+1;j<n-1;j++)
        {
            for(k=j+1;k<n;k++)
            {
                if(a[i]==a[j] || a[j]==a[k] || a[i]==a[k]) continue;
                if(a[i]+a[j]>a[k] && a[i]+a[k]>a[j] && a[k]+a[j]>a[i]) s++;
            }
        }
    }

    cout << s << endl;

    
    
    return 0;
}


 

Measured memory_bytes: 3648
#pragma GCC optimize("O3")

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout cout << fixed << setprecision(15)

//typedef===============
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define eb emplace_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (n); ++(i))
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; --(i))
#define For(i, a, b)    for(int i = (a); (i) < (b) ; ++(i))
#define CtoI(c)         int((c)) - int('0')

//functions=============
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template<typename T> void sortVector(vector<T> &v, bool lesser = true) { lesser ? sort(all(v)) : sort(all(v), greater<T>()); }
bool isPrime(int n){
    if(n < 2) return false; else if(n == 2) return true; else if(n%2 == 0) return false;
    double sqrtNum = sqrt(n); for(int i = 3;i <= sqrtNum; i += 2) if(n%i == 0) return false;
    return true; }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };

/*--------additional--------*/



/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    int n; cin >> n;
    vector<ll> L(n);
    rep(i, n) cin >> L[i];

    sortVector(L);
    int ans = 0;

    for(int i = 0;   i < n-2; ++i)
    for(int j = i+1; j < n-1; ++j)
    for(int k = j+1; k < n;   ++k){
        if( L[i] + L[j] > L[k] &&
            L[j] + L[k] > L[i] &&
            L[k] + L[i] > L[j] &&
            L[i] != L[j] && L[j] != L[k] && L[k]!= L[i])
            ++ans;
    }

    cout << ans << endl;

return 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define fi first
#define se second
#define vi_a vector<int>a;
#define p_b push_back
#define ll int
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define getfiles ifstream cin("input.txt");ofstream cout("output.txt");
#define closefiles cin.close();cout.close();
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define endl "\n"
using namespace std;

int main()
{
    ll n;
    cin>>n;
    vector<ll>dp(n);
    vector<ll>a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(ll i=2;i<n;i++){
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n-1];
}


Measured memory_bytes: 1024
#include <iostream>

int main(){
    long n,m;
    bool toshi[7368792];
    while(1){
        std::cin >> m >> n; 
        if(m==0 && n==0) break;
        long count=0;
        for(int i=0;i<7368792;i++){
            toshi[i] = false;
        }
        while(count <= n){
            if(!toshi[m]){
                for(long j=1;j*m<7368792;j++){
                    toshi[j*m] = true;
                }
                ++count;
            }
            ++m;
        }
        std::cout << m-1 << std::endl;
    }
}



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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 1e9
#define INF_LL 1LL<<60
#define ll long long

#define MAX_V       (301)

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a+b+c>=22) cout << "bust" << endl;
    else cout << "win" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[15][10000];
int record[15];
int h,w,K,res=0x3f3f3f3f;
int main(){
	scanf("%d %d %d",&h,&w,&K);
	for(int i=0;i<h;i++)
                  cin>>s[i];
	for(int i=0;i<1<<h-1;i++){
		memset(record,0,sizeof( record));
		bool f=0;
		int now=0;
		for(int j=0;j<h-1;j++)
		 if(i>>j&1) now++;
		for(int j=0;j<w;j++){
			int id=0;
			bool p=0;
			for(int k=0;k<h;k++){
				record[id]+=(s[k][j]=='1');
				if(record[id]>K)  p=1;
				if(i>>k&1) id++;
			}
			if(p==1){
				now++;
				memset(record,0,sizeof record);
				id=0;
				for(int k=0;k<h;k++)
				{
					record[id]+=(s[k][j]=='1');
					if(record[id]>K)  f=1;
					if(i>>k&1) id++;
				}
			}
		}
		if(!f&&now<res)
			res=now;
	}
	cout<<res<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	int n,ans=0,cur=0;string s;cin>>n>>s;
	for(int i=0;i<s.length();i++){
		if(s[i]=='D')cur--;
		else cur++;
		ans = max(ans,cur);
	}
	cout<<ans;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
  int a, b, c, max, copy;

  scanf("%d %d %d", &a, &b, &c);
  max = a;
  if (max < b) {
    max = b;
  }else {
    copy = a;
    a = b;
    b = copy;
  }
  if (max < c) {
    max = c;
  }else {
    copy = b;
    b = c;
    c = copy;
  }
  if (a > b) {
    copy = a;
    a = b;
    b = copy;
  }

  printf("%d\n", c - a);

  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
bool fun(int x){
	int i,cnt=0;
	for( i=2;i*i<=x;i++ )
	{
		if( x%i==0 )
			cnt++;
	}
	if( cnt==3 )
		return true;
	return false;
}
int main() {
	int n;
	while( cin>>n ){
		if( n<105 )
			cout<<0<<endl;
		else
		{
			int i,ret=0;
			for( i=105;i<=n;i++ ){
				if( i%2 && fun(i) )
					ret++;
			}
			cout<<ret<<endl;
		}
	}
	return 0;
	}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int price[6] = {600, 800, 1000, 1200, 1400, 1600};

void solve()
{
	int n;
	while(cin >> n, n)
	{
		int x, y, h, w;
		int pos1 = 0;
		int pos2 = 0;
		int sum = 0;
		while(n--)
		{
			cin >> x >> y >> h >> w;
			int size = x + y + h;
			if(size <= 60)
			{
				pos1 = 0;
			}
			else if(size <= 80)
			{
				pos1 = 1;
			}
			else if(size <= 100)
			{
				pos1 = 2;
			}
			else if(size <= 120)
			{
				pos1 = 3;
			}
			else if(size <= 140)
			{
				pos1 = 4;
			}
			else if(size <= 160)
			{
				pos1 = 5;
			}
			else
			{
				pos1 = 6;
			}

			if(w <= 2)
			{
				pos2 = 0;
			}
			else if(w <= 5)
			{
				pos2 = 1;
			}
			else if(w <= 10)
			{
				pos2 = 2;
			}
			else if(w <= 15)
			{
				pos2 = 3;
			}
			else if(w <= 20)
			{
				pos2 = 4;
			}
			else if(w <= 25)
			{
				pos2 = 5;
			}
			else
			{
				pos2 = 6;
			}
			if(pos1 < pos2)
			{
				swap(pos1, pos2);
			}
			if(pos1 == 6)
			{
				continue;
			}
			sum += price[pos1];
		}
		cout << sum << endl;
	}
}

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

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

using namespace std;


int main() {
    int ans = 0;
    int N, M, X;
    cin >> N >> M >> X;
    for(int i = 0 ; i < M ; i++){
        int a;
        cin >> a;
        if( a > X ){
            ans++;
        }
    }
    cout << min(ans, M - ans) << endl;
}


Measured memory_bytes: 256
import sys
import numpy as np
def f(n,a_):
      a=[]
      for i,ai in enumerate(a_):
            a.append([1+i,ai])
      a.sort(key=lambda x:x[1],reverse=True)
      dp=np.zeros((n+1,n+1),np.int64) #dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
      dp[1,1]=a[0][1]*(n-a[0][0])
      dp[1,0]=a[0][1]*(a[0][0]-1)
      for i in range(2,n+1):#i人目の幼児。a[i-1]
            dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) #i人目を左にする。その時左に溜まっているのはi-1人
            dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) #i人目を右にする。その時右に溜まっているのはi-1人
            #i人目を左に
            l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] #j:左に溜まっている人数
            #i人目を右に
            r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] #j:右に溜まっている人数
            dp[i,1:i]=np.maximum(l,r)
      return max(dp[n])

if __name__ == '__main__':
      input = sys.stdin.readline
      n=int(input())
      a_=list(map(int,input().split()))
      print(f(n,a_))


Measured memory_bytes: 50140
#include <bits/stdc++.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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

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

    char flg = ((s[0] == 'B')? 'B':'W');
    int ans = 0;

    for(int i=0; i<s.size(); i++){
        if(flg == 'B' && s[i] == 'W'){ ans++; flg = 'W'; }
        else if(flg == 'W' && s[i] == 'B') { ans++; flg = 'B'; } 
    }

    cout << ans << endl;
}

Measured memory_bytes: 512
n=int(input())
a=list(map(int,input().split()))

sum=0
for i in range(n):
    sum=sum+a[i]

for j in range(1,n,2):
    sum=sum-a[j]*2

ans=[sum]
ch=sum
for i in range(0,n-1):
    ch=a[i]*2-ch
    ans.append(ch)

print(' '.join(map(str, ans)))

Measured memory_bytes: 84580
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n,k,ans=1;
int main(){
	cin >> n >> k;
	for(int i = 1;i < n;i++){
		ans*=(k-1);
		}
		printf("%lld\n",ans*k);
	return 0;
	}

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

typedef long long ll;
typedef tuple<ll, ll, ll> mytuple;
const ll INF = 1e9;
const ll MOD = 1000000007;
const double pi = 3.141592653589793238;

// a と b の最大公約数を返す関数
long long GCD(long long a, long long b) { if (b == 0) {return a;} else {return GCD(b, a % b);} }
// a と b の最小公倍数を返す関数
long long LCM(long long a, long long b) { return a/GCD(a,b)*b; }

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

int main() {
  int N; cin >> N;

  map<string, int> m;
  for(int i = 0; i < N; i++) {
    string a; cin >> a;
    if(m.count(a) > 0) {
      m.at(a)++;
    } else {
      m.emplace(a, 1);
    }
  }

  cout << m.size() << endl;
  return 0;
}


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

int main(){
    int n,l=0;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a.at(i);
    sort(a.begin(),a.end());
    cout<<a.at(a.size()-1)-a.at(0)<<endl;
}

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

int main(){
  string S; cin>>S;
  int cnt[3] ={};
  for(int i=0;i<S.size();i++)
    cnt[S[i] - 'a']++;
  sort(cnt,cnt+3);
  int dif = cnt[2] - cnt[0];
  if(dif >= 2) cout<<"NO"<<endl;
  else cout<<"YES"<<endl;
  return 0;
}


Measured memory_bytes: 512
def e_crested_ibis_vs_monster():
    H, N = [int(i) for i in input().split()]
    Monsters = [[int(i) for i in input().split()] for j in range(N)]

    # dp[i][j]: 最初の i 種類の魔法でモンスターに j ダメージ与える場合の消費魔力の最小値
    # としたとき、更新順序を工夫することで添字 i をなくせる
    dp = [0] + [float('inf')] * H
    for a, b in Monsters:
        for j in range(H + 1):
            nj = min(j + a, H)
            dp[nj] = min(dp[nj], dp[j] + b)
    return dp[H]

print(e_crested_ibis_vs_monster())

Measured memory_bytes: 46556
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    double h,w,x,y;
    cin>>w>>h>>x>>y;
    cout<<fixed<<setprecision(10)<<h*w/2<<" ";
    if(w/2==x&&h/2==y)cout<<1<<endl;
    else cout<<0<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main() {
  int n;
  ll d, a;
  cin >> n >> d >> a;
  vector<P> p(n);
  rep(i,n) {
    cin >> p[i].first >> p[i].second;
  }
  sort(p.begin(), p.end());
  d = d*2;
  ll tot = 0;
  queue<pair<ll,ll>> q;
  ll ans = 0;
  rep(i,n) {
    ll x = p[i].first;
    ll h = p[i].second;
    while (q.size() && q.front().first < x) {
      tot -= q.front().second;
      q.pop();
    }
    h -= tot;
    if (h > 0) {
      ll num = (h+a-1)/a;
      ans += num;
      ll damage = num*a;
      tot += damage;
      q.emplace(x+d, damage);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3456
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
const ll infty = 1000000000007;

typedef tuple<ll, int, int> edge;

int N, Q;
int A[200010];
int B[200010];
ll C[200010];
ll X[200010];
vector<edge> V;

const int UFSIZE = 200010;
int union_find[UFSIZE];

void init() {
  for (auto i=0; i<UFSIZE; i++) {
    union_find[i] = i;
  }
}

int root(int a) {
  if (a == union_find[a]) return a;
  return (union_find[a] = root(union_find[a]));
}

bool issame(int a, int b) {
  return root(a) == root(b);
}

void unite(int a, int b) {
  union_find[root(a)] = root(b);
}

bool isroot(int a) {
  return root(a) == a;
}

int main () {
  cin >> N >> Q;
  for (auto i = 0; i < Q; ++i) {
    cin >> A[i] >> B[i] >> C[i];
  }
  fill(X, X+200010, infty);
  for (auto i = 0; i < Q; ++i) {
    V.push_back(edge(C[i], A[i], B[i]));
    X[A[i]] = min(X[A[i]], C[i]+1);
    X[B[i]] = min(X[B[i]], C[i]+2);
  }
  for (auto i = 0; i < 3*N; ++i) {
    X[(i+1)%N] = min(X[i%N]+2, X[(i+1)%N]);
  }
  for (auto i = 0; i < N; ++i) {
    V.push_back(edge(X[i], i, (i+1)%N));
  }
  sort(V.begin(), V.end());
  init();
  int used = 0;
  ll ans = 0;
  auto it = V.begin();
  while (used < N-1) {
    ll c = get<0>(*it);
    int a = get<1>(*it);
    int b = get<2>(*it);
    if (!issame(a, b)) {
      used++;
      ans += c;
      unite(a, b);
    }
    it++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 15212
fun main(args: Array<String>) {
    val MOD = 1000000007L
    fun modpow(a: Long, p: Int): Long {
        if (p == 0) return 1
        return if (p % 2 == 0) {
            val halfP = p / 2
            val half = modpow(a, halfP)
            half * half % MOD
        } else {
            a * modpow(a, p - 1) % MOD
        }
    }

    fun calcComb(a: Int, b: Int): Long {
        if (b > a - b) return calcComb(a, a - b)
        var ansMul = 1L
        var ansDiv = 1L
        for (n in 0 until b) {
            ansMul *= (a - n).toLong()
            ansDiv *= (n + 1).toLong()
            ansMul %= MOD
            ansDiv %= MOD
        }
        return ansMul * modpow(ansDiv, MOD.toInt() - 2) % MOD
    }
    
    val (N, M) =listOfInt()
    var MNokori = M
    var ans = 1L
    var n = 2
    while (n * n <= MNokori) {
        if (MNokori % n == 0) {
            var cnt = 0
            while (MNokori % n == 0) {
                cnt++
                MNokori /= n
            }
            ans *= calcComb(N + cnt - 1, N - 1)
            ans %= MOD
        }
        n += 1
    }
    if (MNokori != 1) {
        ans *= calcComb(N + 1 - 1, N - 1)
        ans %= MOD
    }
    println(ans)
}
fun next() = readLine()!!
fun nextInt() = Integer.parseInt(next())
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }
fun listOfLong() = listOfString().map { java.lang.Long.parseLong(it) }



Measured memory_bytes: 38032
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char s[200001];
int main()
{
    int n, ans, len, i;
    while(~scanf("%s",s))
    {
        len = strlen(s);
        int f, tem;
        for(i = 0; i < len; ++i)
        {
            if(s[i]=='A') {f = i;
            break;}
        }
        for(i = len-1; i >= 0; --i)
        {
            if(s[i]=='Z') {tem = i;
            break;}
        }
        //cout <<"tem="<<tem<<"   flag="<<f<<endl;
        ans = tem - f +1;
        cout << ans << endl;
    }
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int main()
{
 ll n,m;
 cin>>n>>m;
 ll a[n];
 ll sum=0;
 for(ll i=0;i<n;i++)
 {
     cin>>a[i];
     sum+=a[i];
 }
 sort(a,a+n);
 ll cnt=0;
 ll res=0;
 if(sum%(4*m)==0)
 res=sum/(4*m);
 else
 res=sum/(4*m)+1;
for(ll i=0;i<n;i++)
{
    if(a[i]>=res)
    cnt++;
}
if(cnt>=m)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
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; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class FThreeVariablesGame {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n; cin >> n;
      vector<int> c(3);
      cin >> c[0] >> c[1] >> c[2];
      vector<P> vec(n);
      rep(i, n) {
        string s; cin >> s;
        vec[i].first = s[0]-'A';
        vec[i].second = s[1]-'A';
      }

      vector<int> ret(n);

      rep(i, n) {
        if (c[vec[i].first] == 0 && c[vec[i].second] == 0) {
          cout << "No" << endl;
          return;
        }
        if (c[vec[i].first] > c[vec[i].second]) {
          ret[i] = vec[i].second;
          c[vec[i].first]--;
          c[vec[i].second]++;
        } else if (c[vec[i].first] < c[vec[i].second]) {
          ret[i] = vec[i].first;
          c[vec[i].first]++;
          c[vec[i].second]--;
        } else {
          if (i == n - 1) {
            ret[i] = vec[i].first;
            c[vec[i].first]++;
            c[vec[i].second]--;
          } else {
            vector<bool> next(3);
            next[vec[i + 1].first] = true;
            next[vec[i + 1].second] = true;
            if (!next[vec[i].first]) {
              ret[i] = vec[i].second;
              c[vec[i].first]--;
              c[vec[i].second]++;
            } else {
              ret[i] = vec[i].first;
              c[vec[i].first]++;
              c[vec[i].second]--;
            }
          }
        }
      }

      cout << "Yes" << endl;
      for(auto ch: ret) {
        cout << (char) ('A'+ch) << '\n';
      }

    }
};

signed main() {
  FThreeVariablesGame solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 5344
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<chrono>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)


int main() {
	IO;
	int n,m;
	cin>>n>>m;
	vector<pair<ll,ll>> evs;
	for(int i=0;i<m+n;++i) {
		ll x,cnt=1;
		if(i>=n) cin>>cnt;	
		cin>>x;
		
		evs.push_back({x,cnt});
	}
	sort(all(evs));
	reverse(all(evs));
	ll ans=0, rem=n;
	for(auto i:evs) {
		//~ cerr<<i.xx<<" "<<i.yy<<"!\n";
		ll akt=min(rem, i.yy);
		ans+=i.xx*akt;
		rem-=akt;
	}
	cout<<ans<<"\n";
	return 0;
}


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

typedef long long int ll;

const long long MAX = 1e9+7;

vector<bool> is_prime(1001, true);

void sieve_of_eratosthenes(int n){
	is_prime[0] = is_prime[1] = false;

	for (int i=2; i<=n; i++)
        if(is_prime[i] &&  i*i*1ll<=n)
            for (int j=i*i*1ll; j<=n; j+=i)
                is_prime[j] = false;
}

int legendre(int n){

    ll res = 1;
    for (int i=1; i<=n; i++){
        if(is_prime[i]){

            ll sum_expo = 0;
            ll pot = 1;
            while((n/pot)>0){
                pot = pot * i;
                sum_expo += n/pot;
            }

            if(sum_expo == 0) break;
            res = (res * (sum_expo + 1))%MAX;
        }
    }
    return res;
}

void solve(){
    int n; cin>>n;
    sieve_of_eratosthenes(n);
    cout<<legendre(n)<<endl;
}

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


Measured memory_bytes: 3516
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mkp make_pair
#define int long long
#define fori(j,n) for(int i=j;i<n;i++)
#define forb(n,j) for(int i=n-1;i>=0;i--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define PI 3.141592653589793
#define M 1000000007
using namespace std;
int fast(int a,int b)
{
    int ans=1;
    a=a%M;
    if(a==0)
        return 0;
    while(b>0)
    {
        if(b&1)
        {
            ans=(ans*a)%M;
        }
        b>>=1;
        a=(a*a)%M;
    }
}
int N;
int v[105];
int w[105];
int dp[105][100002];
int cal(int i,int W)
{
    if(i>N)
        return 0;
    if(dp[i][W]!=-1)
        return dp[i][W];
    int ans=0;
    int notinclude=cal(i+1,W);
    int include=0;
    if(W-w[i]>=0)
         include=v[i]+cal(i+1,W-w[i]);
    return dp[i][W]=max(include,notinclude);
}
int32_t main()
{
    IOS;
    int W;
    memset(dp,-1,sizeof(dp));
    cin>>N>>W;
    fori(0,N)
    {
        cin>>w[i]>>v[i];
    }
    cout<<cal(0,W);
    return 0;
}


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

#define all(x) (x).begin(),(x).end()
#define SP <<" "<<
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000

typedef long long LL;
typedef long double LD;

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> s(n);
  for(int i=0;i<n;i++){
    cin >> s[i];
  }
  sort(all(s),greater<int>());
  vector<LL> dp(x+1,0);
  dp[x]=1;
  for(int i=0;i<n;i++){
    LL tmp;
    for(int j=0;j<=x;j++){
      tmp=dp[j];
      dp[j]=dp[j]*(n-i-1)%MOD;
      dp[j%s[i]]=(dp[j%s[i]]+tmp)%MOD;
    }
  }
  LL ans=0;
  for(int i=0;i<=x;i++){
    ans=(ans+dp[i]*i%MOD)%MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

ps = set()
for i,m in enumerate(sieve_eratosthenes(1000000)):
    if m == 1:
        ps.add(i)

from collections import defaultdict
import math

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
one = False
for i in range(n):
    if a[-1] == 1:
        a.pop()
        one = True
        n -= 1
    else:
        break

if n==0 or n==1:
    print("pairwise coprime")
    exit()

a.sort()

g = a[0]
for i in range(1,n):
    g = math.gcd(g, a[i])

if g == 1:
    if n > len(ps):
        print("setwise coprime")
    else:
        d = defaultdict(int)
        for i in range(n):
            f = factorization(a[i])
            for x, y in f:
                d[x] += 1
        for i in d.values():
            if i != 1:
                print("setwise coprime")
                exit()
        print("pairwise coprime")

else:
    if one:
        print("setwise coprime")
    else:
        print("not coprime")

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

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

    if (n == 1) {
        if (a[0]%2) cout << 2 << endl;
        else cout << 1 << endl;
        return 0;
    }

    ll ans = 1;
    rep(i, n) ans *= 3;

    ll t = 1;
    rep(i, n) {
        if (a[i]%2 == 0) t *= 2;
    }

    cout << ans - t << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  VEC<int>a(5);
  REP(i,0,5)cin>>a[i];
  int k;
  cin>>k;
  sort(ALL(a));
  if(a[4]-a[0]>k)cout<<":("<<endl;
  else cout<<"Yay!"<<endl;

  return 0;
}


Measured memory_bytes: 256
import heapq
import collections

cnt=1
cnts=collections.defaultdict(int)
median=0
left_cnt=0
right_cnt=0
left_sum=0
right_sum=0
left_pos=[]
right_pos=[]
b=0
q=int(input())
initial=list(map(int,input().split()))
median=initial[1]
b+=initial[2]
cnts[median]=1
for _ in range(q-1):
  query=list(map(int,input().split()))
  if query[0]==1:
    cnt+=1
    b+=query[2]
    if query[1]==median:
      cnts[median]+=1
    elif query[1]<median:
      left_cnt+=1
      left_sum+=query[1]
      cnts[query[1]]+=1
      if cnts[query[1]]==1:
        heapq.heappush(left_pos,-query[1])
    elif query[1]>median:
      right_cnt+=1
      right_sum+=query[1]
      cnts[query[1]]+=1
      if cnts[query[1]]==1:
        heapq.heappush(right_pos,query[1])
    if left_cnt+1<=(cnt+1)//2<=left_cnt+cnts[median]:
      continue
    elif left_cnt+1>(cnt+1)//2:
      heapq.heappush(right_pos,median)
      right_cnt+=cnts[median]
      right_sum+=median*cnts[median]
      median=-heapq.heappop(left_pos)
      left_cnt-=cnts[median]
      left_sum-=median*cnts[median]
    elif (cnt+1)//2>left_cnt+cnts[median]:
      heapq.heappush(left_pos,-median)
      left_cnt+=cnts[median]
      left_sum+=median*cnts[median]
      median=heapq.heappop(right_pos)
      right_cnt-=cnts[median]
      right_sum-=median*cnts[median]
  elif query[0]==2:
    value=b
    if left_cnt!=0:
      value+=abs(left_sum-median*left_cnt)
    if right_cnt!=0:
      value+=abs(right_sum-median*right_cnt)
    print(median,value)

Measured memory_bytes: 22448
#include <bits/stdc++.h>
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define loop(j, n) for(int i=j; i<=n; ++i)
using namespace std;

void printArray(int*, int, int);
void printCharArray(char*, int, int);
void ruffleSort(int*, int);

int t; 

int main(int argc, char const *argv[])
{   
    IOS;
    ll x, k, d;
    cin >> x >> k >> d;
    x=abs(x);
    if(x>0 && (x/d)>=k) {
        x-=(k*d);
        cout << x;
    }
    else {
        ll y=x/d;
        x-=y*d;
        k-=y;
        if(k%2==0) {
            cout << abs(x);
        }
        else {
            cout << min(abs(x-d), abs(x+d));
        }
    }
    return 0;
}

void printArray(int *a, int start, int end) {
    for(int i=start; i<=end; ++i) {
        cout << *(a+i) << ' ';
    }
}

void printCharArray(char *a, int start, int end) {
    for(int i=start; i<=end; ++i) {
        cout << *(a+i) << ' ';
    }
}

void ruffleSort(int *a, int n) {
    unsigned seed=0;
    shuffle(a, a+n, default_random_engine(seed));
    sort(a, a+n);
}

Measured memory_bytes: 3620
#include <cstdio>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 205;
const int M = 1000000;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
const double eps = 1e-8;
int n,m;
int k;
int d[N][N];
int s[N*N];
int main () 
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(s,0,sizeof s);
        memset(d,0,sizeof d);
        scanf("%d",&k);
        for (int i=1;i<=k;i++)
            scanf("%d",&s[i]);
        int tmp=1;
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if (i%2==0)
                    d[i][j]=tmp;
                else
                    d[i][m-1-j]=tmp;
                s[tmp]--;
                if (s[tmp]==0)
                    tmp++;
            }
        }
        for (int i=0;i<n;i++)
            for (int j=0;j<m;j++)
            {
                printf("%d",d[i][j]);
                if (j<m-1)
                    printf(" ");
                else
                    printf("\n");
            }
    }
    return 0;
}

/*

2 2
3
2 1 1

3 5
5
1 2 3 4 5

*/

Measured memory_bytes: 640
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[5],maxc;
int main()
{
 scanf("%s",s);
 int len=strlen(s);
 maxc=s[0];
 for(int i=0;i<len;i++)
  if(s[i]>s[0])
  {
   maxc=s[0]+1;
   break;
  }
 for(int i=0;i<len;i++)
  printf("%c",maxc);
 return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if((a>=-100 && a<=100) && (b>=-100 && b<=100) && (c>=-100 && c<=100)){
        if(c>=a && c<=b){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
using namespace std;
main(){
  int m,n;
  while(cin>>m>>n,n){
    int a1[n][n],a2[n][n],q,w,e,r;
    r(i,n)r(j,n){
      if(i==j)a2[i][j]=a1[i][j]=0;
      else a2[i][j]=a1[i][j]=INF;
    }
    while(m--){
      scanf("%d%d%d%d",&q,&w,&e,&r);q--;w--;
      a1[q][w]=a1[w][q]=e;
      a2[q][w]=a2[w][q]=r;
    }
    r(k,n)r(i,n)r(j,n){
      if(a1[i][k]+a1[k][j]<=INF)a1[i][j]=min(a1[i][j],a1[i][k]+a1[k][j]);
      if(a2[i][k]+a2[k][j]<=INF)a2[i][j]=min(a2[i][j],a2[i][k]+a2[k][j]);
    }
    cin>>e;
    while(e--){
      scanf("%d%d%d",&q,&w,&r);q--;w--;
      if(r)cout<<a2[q][w]<<endl;
      else cout<<a1[q][w]<<endl;
    }
  }
}

Measured memory_bytes: 3236
#include<stdio.h>
int main(){
  int i,j,n;
  scanf("%d",&n);
  long int a[n+101],b[n+100],sum=0;
  for(i=0;i<=n;i++) scanf("%ld",&a[i]);
  for(i=0;i<n;i++) scanf("%ld",&b[i]);

  for(i=0;i<n;i++){
    if(a[i] > b[i]){
      sum += b[i];
      continue;
    }else{
      sum += a[i];
      if(a[i+1] > b[i]-a[i]){
        sum += b[i] - a[i];
        a[i+1] -= b[i] - a[i];
        continue;
      }else{
        sum += a[i+1];
        a[i+1] = 0;
        continue;
      }
    }
  }
  printf("%ld\n",sum);
  return 0;
}

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

int main(){
  string S, T;
  cin >> S >> T;
  int L=S.size();
  int sspel[26]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
  int tspel[26]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
  string ans="Yes";
  for(int i=0; i<L; i++){
    sspel[S.at(i)-97]++;
    tspel[T.at(i)-97]++;
    if(sspel[S.at(i)-97]!=tspel[T.at(i)-97]){
      ans="No";
      break;
    }
  }
  cout << ans << endl;
  
}

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

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int A=gi();
	    int B=gi();
	    
//	    for(int i=0; i<N;i++) {
//	    	A[i]=gi();
//	    	s+=A[i];
//	    }
//	    
	    
       // System.out.print(sb.toString());

        if (A>B) {
    	    for(int i=0; i<A;i++) {
    	    	System.out.print(B);
	    }
        }else{
        	for(int i=0; i<B;i++) {
    	    	System.out.print(A);
	    }
        }
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

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

int main() {
	string tmp;
	string longest;
	int mlength=0;
	map<string,int> m;
	while(cin >> tmp)
	{
		m[tmp]++;
		if (tmp.size()>mlength)
		{
			mlength=tmp.size();
			longest=tmp;
		}
	}
	string frequent;
	int mfreq=0;
	for (map<string,int>::iterator it=m.begin(); it!=m.end(); ++it)
	{
		if (it->second > mfreq)
		{
			mfreq=it->second;
			frequent=it->first;
		}
	}
	cout << frequent << " " << longest << endl;
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_SIZE 400

void coloring_replace(int w, int h, int orig, int new, int col[MAX_SIZE][MAX_SIZE])
{
    int x, y;

    if (orig == new) {return;}

    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            if (col[y][x] == -1) {break;}
            if (col[y][x] == orig) {col[y][x] = new;}
        }
    }

    return;
}

int coloring(int w, int h, char s[MAX_SIZE][MAX_SIZE + 1], int col[MAX_SIZE][MAX_SIZE])
{
    int x, y;
    int count = 0;

    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            col[y][x] = -1;
        }
    }

    col[0][0] = count; // (0, 0)は色番号0
    count++;
    y = 0;
    for (x = 1; x < w; x++) {
        if (s[y][x - 1] != s[y][x]) {
            col[y][x] = col[y][x - 1];
        } else {
            col[y][x] = count;
            count++;
        }
    }
    for (y = 1; y < h; y++) {
        for (x = 0; x < w; x++) {
            if (s[y - 1][x] != s[y][x]) {
                col[y][x] = col[y - 1][x];
                if (x > 0 && s[y][x - 1] != s[y][x] && col[y][x - 1] != col[y][x]) {
                    coloring_replace(w, h, col[y][x - 1], col[y][x], col); //同じ色にする
                }
            } else if (x > 0 && s[y][x - 1] != s[y][x]) {
                col[y][x] = col[y][x - 1];
            } else {
                col[y][x] = count;
                count++;
            }
        }
    }

    return count;
}

int main(int argc, char *argv[])
{
    int h, w;
    int x, y;
    char s[MAX_SIZE][MAX_SIZE + 1];
    int col[MAX_SIZE][MAX_SIZE];
    int col_b[MAX_SIZE * MAX_SIZE], col_w[MAX_SIZE * MAX_SIZE];
    long long ans;
    int i;
    int n_color;

    scanf("%d %d", &h, &w);

    for (i = 0; i < h; i++) {
        scanf("%s", s[i]);
    }

    // マップを塗分ける
    n_color = coloring(w, h, s, col);

    for (i = 0; i < n_color; i++) {
        col_w[i] = 0;
        col_b[i] = 0;
    }

    // マップの黒と白の数を塗分けた色別にカウントする
    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            if (s[y][x] == '#') {
                col_b[col[y][x]]++;
            } else {
                col_w[col[y][x]]++;
            }
        }
    }
    
    ans = 0;
    for (i = 0; i < n_color; i++) {
        ans += (long long) col_w[i] * col_b[i];
    }

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


Measured memory_bytes: 2048
<?php
	$n = fgets(STDIN);
	$h = explode(' ', trim(fgets(STDIN)));
	$count[-1] = 0;
	for($i=0;$i<$n-1;$i++){
      if($h[$i] >= $h[$i+1]){
        $count[$i]=$count[$i-1]+1;
      }else{
        $count[$i]=0;
      }
    }
	echo(max($count));

Measured memory_bytes: 35372
#include <stdio.h>
int main() {
    int x[4], y[4], dx, dy;
    scanf("%d %d %d %d", x, y, x+1, y+1);
    dx = x[1] - x[0];
    dy = y[1] - y[0];
    x[2] = x[1] - dy;
    y[2] = y[1] + dx;
    x[3] = x[2] - dx;
    y[3] = y[2] - dy;
    printf("%d %d %d %d", x[2], y[2], x[3], y[3]);
    return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
#define N 100000
int binarySearch(int);
int n,q,S[N],T[N];
int main(){
  int i,j,count = 0,num;

  scanf("%d",&n);

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

  scanf("%d",&q);

  for(i = 0;i < q;i++){
    scanf("%d",&T[i]);
  }
  for(i = 0;i < q;i++){
  num = binarySearch(T[i]);
  if(num == 1)count++;
  }
   printf("%d\n",count);

  return 0;
}

int binarySearch(int key){
  int left,right,mid;
  left = 0;
  right = n;
  while(left < right){
    mid = (left + right) / 2;
    if(S[mid] == key){
      return 1;
    }
    else if(key < S[mid]){
      right = mid;
    }
    else{
	  left = mid + 1;
    }
  }
    return 0;
	      
}

Measured memory_bytes: 1184
// ABEY SAALE
// QUESTION KHUD KR SOLUTION KYU DEKH RHA H
 
 
 
 
 
 
 
 
//MAAF KIJIYEGA ME GUSSE ME IDHAR UDHAR NIKAL JATA HU
#include<bits/stdc++.h>
#define mod 1000000007
#define fr first
#define se second
#define ll long long
#define PI 3.1415926535 
#define pb push_back
#define mpr make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define senky_bansal ios_base::sync_with_stdio(false);
#define IIIT_ALLAHABAD    cin.tie(NULL);cout.tie(NULL);
using namespace std;

ll fac[2000005];
void pre(){ fac[0]=1; fac[1]=1; for(int i=2;i<200005;i++) fac[i]=(i*fac[i-1])%mod;}
ll power(ll a,ll b){ll res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b=b/2;}return res%mod;}
ll ncr(ll n,ll r){return ((fac[n]*power(fac[r],mod-2))%mod*power(fac[n-r],mod-2))%mod;}
// DEKHIYE JI  WALID JO THE ABBA HAMARE WO YEH function CHHOD KR GYE THE

signed main()
{   



      
      senky_bansal
      IIIT_ALLAHABAD
      
      // pre();
      ll t;
      // cin>>t;
      t=1;
      while(t--)
      { 
         
         ll n,k;
         cin>>k>>n;
         ll a[n+5];
         for(int i=1;i<=n;i++)
         {
              cin>>a[i];
         }
         // a[i+1]=n;
         ll ans1 = 0;
         ll prev = 0;
         for(int i=1;i<=n;i++)
         {
              // ll temp = prev;
              ll temp;
              if(i==1)
              {
                   temp = min(a[n]-a[i],a[i]+k-a[i+1]);
              }
              else if(i==n)
              {
                   temp = min(a[n]-a[1],k-a[n]+prev);
              }
              else
              {
                  temp = min(k-a[i]+prev,a[i]+k-a[i+1]);
              }

              prev = a[i];
              if(ans1==0)
                ans1 = temp;
            else
                ans1 = min(ans1,temp);
         }
         cout<<ans1<<endl;
      }
      






}



























Measured memory_bytes: 1792