akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define itn int
#define rep(i,n) for(int i = 0;i < n;i++)

ll dp[1005][100005];

int main(void){
    int n,W;
    cin >> n >> W;
    int w[n],v[n];
    for(int i = 0;i < n;i++)cin >> w[i] >> v[i];
    
    for(int i = 0;i <= n;i++){
        for(int j = 0;j <= 100000;j++)dp[i][j] = 1e17;
    }
    
    dp[0][0] = 0;
    
    for(int i = 0;i < n;i++){
        for(int j = 0;j <= 100000;j++){
            if(j >= v[i]){
                dp[i+1][j] = min(dp[i][j],dp[i][j-v[i]]+w[i]);
            } else {
                dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
            }
        }
    }
    
    int ans = 0;
    for(int i = 0;i <= 100000;i++){
        if(dp[n][i] <= W)ans = max(ans,i);
    }
    cout << ans << endl;
}

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

typedef long long ll;
//loop
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//STL
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

//const
#define MOD 1000000007 //10^9+7:合同式の法

//acronym
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

void Main() {
    int a, b;
    cin >> a >> b;
    string win;
    if (a == b) {
        win = "Draw";
    }
    else if (a == 1) {
        win = "Alice";
    }
    else if (b == 1) {
        win = "Bob";
    }
    else {
        if (a > b) {
            win = "Alice";
        } else {
            win = "Bob";
        }
    }
    cout << win << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Main();
	return 0;
}


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

using ll=long long;

using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;

int main() {
  int MAX=pow(10,5)+1;
  vi is_prime(MAX,1);
  is_prime[0]=0,is_prime[1]=0;
  rep(i,2,sqrt(MAX)) {
    if (is_prime[i]==0) {
      continue;
    }
    for (int j=i*2;j<MAX;j+=i) {
      is_prime[j]=0;
    }
  }
  vi a(MAX,0);
  rep(i,0,MAX) {
    if (i%2==0) {
      continue;
    } else if (is_prime[i] && is_prime[(i+1)/2]) {
      a[i]=1;
    }
  }
  vi s(MAX+1,0);
  rep(i,0,MAX) {
    s[i+1]=s[i]+a[i];
  }
  int Q; cin >>Q;
  rep(q,0,Q) {
    int l,r; cin >>l >>r;
    r++;
    cout <<s[r]-s[l] <<endl;
  }
  return 0;
}


Measured memory_bytes: 4516
//============================================================================
//Everyone has a different way of thinking, so God Created us
//   Hope You Respect My Way..,Thank You ):
// Author      : Murad
// Name        : Codeforces.cpp & Atcoder.cpp
// Description : Problem name
//============================================================================
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define pi 3.1415926536
#define forn(i,a,b)for(int i=a;i<b;i++)
#define LL long long
#define ULL unsigned long long
#define MP make_pair
#define ff first
#define ss second
#define endl '\n'
#define INF 1e9 + 1
#define _INF INT32_MIN
#define pq priority_queue
#define MM multimap
#define PB push_back
#define vii vector<int>
#define ipair pair<int,int>
#define lpair pair<LL,LL>
#define El3zba ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define modd 1000000007
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1,v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1,v2,v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
//std::transform(s1.begin(), s1.end(), s1.begin(),::tolower);
char alphz[27] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };
float Euclidean(LL x1, LL x2, LL y1, LL y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}
LL gcd(LL a,LL b) {
	return !b ? a : gcd(b, a % b);
}
LL LCM(LL a, LL b) {
	return (a*b) / gcd(a, b);
}
void PrimeFactor(LL n)
{
	while (n % 2 == 0) {
		//printf("%d ", 2);
//		aa.insert(2);
		n /= 2;
	}
	for (int i = 3; i <= sqrt(n); i += 2)
	{
		if (n%i == 0) {
			//printf("%d ", i);
			//aa.insert(i);
			n /= i;
		}
	}
	if (n > 2){
		//printf("%d ", n);
	//	aa.insert(n);
	};
}
bool is_square(LL x) {
	LL l = 0, r = x;
	while (l <= r) {
		LL mid = l + (r - l) / 2;
		if (mid*mid == x)return true;
		if (mid*mid > x)r = mid - 1;
		else l = mid + 1;
	}
	return false;
}
LL power(LL x, LL y)
{
	LL temp;
	if (y == 0)return 1;
	temp = power(x, y / 2);
	if (y % 2 == 0)
		return temp*temp;
	else return x*temp*temp;
}
bool is_Prime(int x) {
	if (x == 2)return 1;
	else if (x % 2 == 0 || x < 2)return 0;
	for (int i = 3; i*i <= x; i += 2)
		if (x%i == 0)return 0;
	return 1;
}
int main()
{
	El3zba;
	/***  بسم الله الرحمن الرحيم   ***/
	int n;
	cin >> n;
	if (n % 4 == 0 || n % 7 == 0)
		return cout << "Yes\n",0;
	else {
		int sum = 0;
		while (n>4)
		{
			n -= 4;
			sum += 4;
			if (n % 7 == 0)
				return cout << "Yes\n", 0;
		}
		if (n == 0)
			return cout << "Yes\n",0;
	}
	cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char s[101],t[101];
int main()
{
	scanf("%s",s);
	scanf("%s",t);
	sort(s,s+strlen(s));
	sort(t,t+strlen(t),greater<char>());
	printf("%s",strcmp(s,t)<0?"Yes":"No");
	return 0;
}

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

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}


void solve(long long N){
    cout << "ABC" << N << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N,H;
	int a[100005];
	int b[100005];
	cin>>N>>H;
	int amax=0;
	for(int i=0;i<N;i++)
	{
		cin>>a[i]>>b[i];
		if(a[i]>amax)
		{
			amax=a[i];
		}
	}
	sort(b,b+N);
	int x=0;
	for(int i=N-1;i>=0;i--)
	{
		if(b[i]>amax&&H>0)
		{
			x++;
			H-=b[i];
		}
		else
		{
			break;
		}
	}
	while(H>0)
	{
		H-=amax;
		x++;
	}
	cout<<x<<endl;
	return 0;
 } 

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

int main(){
	int a, b;
  	cin >> a >> b;
  	
	int ans = 0;
  	int tap = 1;
  	while(tap < b){
      	tap += a-1;
    	ans++;
    }
  
  	cout << ans << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define chmax(a,b) if(a<b)a=b;
#define chmin(a,b) if(b<a)a=b;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
constexpr int dx[] = {1, 0, -1,  0};
constexpr int dy[] = {0, 1,  0, -1};
#define N 3
#define N2 9
constexpr char dir[4] = {'u', 'l', 'd', 'r'};
struct Puzzle {
	vi f;
	int space;
	string path;
	Puzzle(): space(0), path("") {
		vi b(N2, 0);
		f = b;
	}
	bool operator < (const Puzzle &p) const {
		rep(i, 0, N2) {
			if(f[i] == p.f[i]) continue;
			return f[i] > p.f[i];
		}
		return false;
	}
};
bool isTarget(Puzzle p) {
	rep(i, 0, N2)
		if(p.f[i] != (i + 1)) return false;
	return true;
}
string bfs(Puzzle s) {
	deque<Puzzle> Q;
	map<Puzzle, bool> V;
	Puzzle u, v;
	s.path = "";
	Q.eb(s);
	V[s] = true;
	int sx, sy, tx, ty;
	while(!Q.empty()) {
		u = Q.front(); Q.pop_front();
		if(isTarget(u)) return u.path;
		sx = u.space / N;
		sy = u.space % N;
		rep(r, 0, 4) {
			tx = sx + dx[r];
			ty = sy + dy[r];
			if(tx < 0 || tx >= N || ty < 0 || ty >= N) continue;
			v = u;
			swap(v.f[u.space], v.f[tx * N + ty]);
			v.space = tx * N + ty;
			if(!V[v]) {
				V[v] = true;
				v.path += dir[r];
				Q.eb(v);
			}
		}
	}
	return "unsoIvable";
}
int main() {
	Puzzle in;
	rep(i, 0, N2) {
		cin >> in.f[i];
		if(in.f[i] == 0) {
			in.f[i] = N2;
			in.space = i;
		}
	}
	string ans = bfs(in);
	P(len(ans));
	return 0;
}

Measured memory_bytes: 38968
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    ll t;
    cin >> n >> t;
    vector<int> a(n);
    ll sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n;){
        int pos = i;
        while(pos + 1 < n && a[pos] + t >= a[pos + 1]){
            pos++;
        }
        sum += (a[pos] + t - a[i]);
        i = pos + 1;
    }
    cout << sum;
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

Measured memory_bytes: 1024
def num2alpha(num):
    if num <= 26:
        return chr(64 + num).lower()
    elif num % 26 == 0:
        return num2alpha(num // 26 - 1) + chr(90).lower()
    else:
        return num2alpha(num // 26) + chr(64 + num % 26).lower()


n = int(input())
print(num2alpha(n))


Measured memory_bytes: 9056
#include<cstdio>
using namespace std;
int n,k;
bool BO[10];
bool Check(int n){
	while(n>0){
		if(BO[n%10])return false;
		n/=10;
	}
	return true;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0,tmp;i<k;++i){scanf("%d",&tmp);BO[tmp]=true;}
	while(!Check(n))++n;
	printf("%d",n);
}

Measured memory_bytes: 128
N = int(input())
NN = N
if N % 2 != 0:
    print(0)
    exit()

ans = 0
tmp_list = [0] * 40
for i in range(40):
    tmp_list[i] = N // (10 * 5 ** i)
ans = sum(tmp_list)
print(ans)

Measured memory_bytes: 3060
def judge(num, legs):
  if legs % 2 != 0:
    return "No"
  elif legs // 4 > num:
    return "No"
  elif legs // 2 < num:
    return "No"
  elif (legs // 4) == num and (legs % 4) != 0:
    return "No"
  else:
    return "Yes"


list1 = input().split()
num = int(list1[0])
legs = int(list1[1])

print(judge(num, legs))

Measured memory_bytes: 9184
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
const int N = 200001;
using namespace std;




int main() {
//    cout << fixed << setprecision(10);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    string s;
    cin >> n >> s;
    int dp[n + 1][3];
    memset(dp, 0, sizeof dp);

    for (int i = 0; i < n; i++) {
        dp[i + 1][0] = dp[i][0];
        dp[i + 1][1] = dp[i][1];
        dp[i + 1][2] = dp[i][2];

        if (s[i] == 'R') ++dp[i + 1][0];
        if (s[i] == 'G') ++dp[i + 1][1];
        if (s[i] == 'B') ++dp[i + 1][2];

    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 3; j < n; j++) {
            if (s[i] != s[j]) {
                int tarL;
                char ot;
                if (s[i] != 'R' && s[j] != 'R') {
                    tarL = 0;
                    ot = 'R';
                }
                if (s[i] != 'G' && s[j] != 'G') {
                    tarL = 1;
                    ot = 'G';
                }
                if (s[i] != 'B' && s[j] != 'B') {
                    tarL = 2;
                    ot = 'B';
                }

                ans += dp[j][tarL] - dp[i + 1][tarL];
                if ((j - i) % 2 == 0 && s[(i + j) / 2] == ot) {
                    --ans;
                }
            }
        }
    }

    cout << ans;


}


Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>; // グラフ型
typedef long long ll;
#define _GLIBCXX_DEBUG

 // 深さ優先探索
vector<bool> seen;
int dfs(const Graph &G, ll v) {
    seen[v] = true; // v を訪問済にする
    int score = 0; 

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー

        // 負荷さ優先探索中の処理



        dfs(G, next_v); // 再帰的に探索, 毎回mat渡してええの？
    }
    return score;
} 

/*
//桁数の計算
ll keta(ll num){
  ll ans= 0 ;
  ll rem;

  for (ll i = 4; i >= 0 ; i--){
    rem = pow(10,i);
    ans += (num / rem); 
    num = num % rem;
  }
  return ans;
}
*/

ll Lucas(ll N){
  if (N == 0){
    return 2;
  }else if(N == 1){
    return 1;
  }
  ll ans;
  ans = Lucas(N-1) + Lucas(N-2);

  return ans;

}


int main() {
  string S, op1, op2, op3;
  ll A, B, C, D;
  cin >> S;

  A = (int)S[0] - 48;
  B = (int)S[1] - 48;
  C = (int)S[2] - 48;
  D = (int)S[3] - 48;
  ll ans;

  for (int tmp = 0; tmp < (1 << 3); tmp++) {
    ans = A;
    bitset<3> se(tmp);
    if (se.test(2)){
      ans += B;
      if (se.test(1)){
        ans += C;
        if (se.test(0)){
          ans += D;
        }else{
          ans -= D;
        }
      }else{
        ans -= C;
        if (se.test(0)){
          ans += D;
        }else{
          ans -= D;
        }
      }
    }


    if (!se.test(2)){
      ans -= B;
      if (se.test(1)){
        ans += C;
        if (se.test(0)){
          ans += D;
        }else{
          ans -= D;
        }
      }else{
        ans -= C;
        if (se.test(0)){
          ans += D;
        }else{
          ans -= D;
        }
      }
    }
  
    //cout << ans << endl;
    
    // ビット列を出力
    if (ans == 7){
      op1 = se.test(2) ? "+" : "-";
      op2 = se.test(1) ? "+" : "-";
      op3 = se.test(0) ? "+" : "-";
      break;
    }
  }


  //cout << A <<  B <<  C  << D << endl;
  
  cout << A << op1 << B << op2 << C << op3 << D <<"=7" << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

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

    li n;
    cin >> n;
    vector<vector<li>> g(n);
    vector<li> rev(n);

    for (int i = 0; i < n; ++i) {
        li fr;
        cin >> fr;
        fr--;
        rev[i] = fr;
        g[fr].push_back(i);
    }

    vector<bool> vis(n);
    li loop = 0;
    while (not vis[loop]) {
        vis[loop] = true;
        loop = rev[loop];
    }

    if (loop == -1) {
        // unreachable
        cout << "POSSIBLE" << endl;
        cerr << "unreachable" << endl;
        return 0;
    }

    vector<li> indegs(n);
    queue<li> q;
    for (int i = 0; i < n; ++i) {
        indegs[i] = g[i].size();
        if (indegs[i] == 0) {
            q.emplace(i);
        }
    }

    vector<li> grundy(n, -1);
    const auto calc_grundy = [&](const li pos) {
        set<li> nexts;
        for (auto &next : g[pos]) {
            nexts.insert(grundy[next]);
        }
        for (int i = 0; i < n; ++i) {
            if (nexts.find(i) == nexts.end()) {
                return i;
            }
        }
    };

    while (not q.empty()) {
        auto pos = q.front();
        q.pop();
        grundy[pos] = calc_grundy(pos);
        const li prev = rev[pos];
        if (--indegs[prev] == 0) {
            q.emplace(prev);
        }
    }

    vector<li> candidates;
    set<li> nexts;
    for (auto &next : g[loop]) {
        nexts.emplace(grundy[next]);
    }
    for (int i = 0; i < n && candidates.size() < 2; ++i) {
        if (nexts.find(i) == nexts.end()) {
            candidates.push_back(i);
        }
    }

    for (int i = 0; i < 2; ++i) {
        const li candidate = candidates[i];
        grundy[loop] = candidate;
        li pos = rev[loop];
        while (pos != loop) {
            grundy[pos] = calc_grundy(pos);
            pos = rev[pos];
        }

        if (calc_grundy(loop) == candidate) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 14976
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<int, int>;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define SIZE(x) ((ll)(x).size())
#define INF 1000000000000

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main() {
    vector<int> a(3);
    rep(i,3) cin >> a.at(i);
    sort(all(a));
    rep(i,2) cout << a.at(i) << " ";
    cout << a.at(a.size()-1) << endl;
}


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

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

const int INF=1001001001001001001ll;

int N;
int H[5555],P[5555];

int dp[5555][5555];


signed main(){
    cin>>N;
    rep(i,N)cin>>H[i]>>P[i];

    vpint ord;
    rep(i,N)ord.pb({H[i]+P[i],i});
    sort(all(ord));


    fill_n(*dp,5555*5555,INF);
    dp[0][0]=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            int w=ord[i].se;
            chmin(dp[i+1][j],dp[i][j]);
            if(dp[i][j]<=H[w]){
                chmin(dp[i+1][j+1],dp[i][j]+P[w]);
            }
        }
    }

    for(int i=N;i>=0;i--){
        if(dp[N][i]<INF){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}


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

int n,m,u,v,p[10009];

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;p[u]++;p[v]++;
	}
	for(int i=1;i<=n;i++) cout<<p[i]<<endl;
	return 0;
}


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

#define ll long long
#define ppi pair<int, int>
#define pb push_back
#define vi vector<int>
#define fi first
#define se second
#define forn(i,n) for(ll i = 0; i < n; i++)
#define forx(i,x,n) for(ll i = x; i < n; i++)

using namespace std;


char a[1001][1001];
ll DP[1001][1001];
const int m = 1e9+7;
int main()
{
	int h, w; cin >> h >> w;  
	forn(i,h) forn(j,w) cin>>a[i][j];
	DP[0][0] = 0;
	forn(i,h) if(a[i][0] == '.') DP[i][0] = 1; else break;
	forn(i,w) if(a[0][i] == '.') DP[0][i] = 1; else break;
	forx(i,1,h) 
		forx(j,1,w) 
			if(a[i][j] == '.') DP[i][j] = (DP[i-1][j]+DP[i][j-1])%m;
			else DP[i][j] = 0;
	cout<<DP[h-1][w-1];
 	
}

Measured memory_bytes: 9088
use std::io::{self, Read};

fn main() {
    let mut n = String::new();
    io::stdin().read_to_string(&mut n).unwrap();

    let mut n: u16 = n.trim().parse().unwrap();

    while n != 0 {
        if n % 10 == 7 {
            println!("Yes");
            return;
        }

        n /= 10;
    }

    println!("No");
}


Measured memory_bytes: 2076
#include<bits/stdc++.h>
# define ll long long
# define ld long double
# define pb push_back
#define F first
#define S second
 
// #define loop(i,n) for(int i=0;i<n;i++)
// #define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
 
  
    // for(int i=0;i<n;i++){  
        
    //     int x,y;
    //     cin>>x>>y;
        
    //     v.pb({x,y});         //make pair in vector
    // }
 
using namespace std;

#define P 1000000007


int main()
{ fast;
ll a,b,c,d;
cin>>a>>b>>c>>d;

ll count=0;

while(a>0 and c>0)
{  if(c>0)
	{c=c-b;
		count++;}

    if(c<=0)
    { break;}		

   if(a>0)
   	{a=a-d;
   	  count++;}


    if(a<=0)
    { break;}		


  
}
//cout<<count;
if(a<=0)
{cout<<"No"<<"\n";}
else 
{cout<<"Yes"<<"\n";}

}


Measured memory_bytes: 3652
#include "bits/stdc++.h"
using namespace std;

using ll = long long int;
#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()

#define pi 3.14159265358979323846

template<class T>bool ch1000000(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; }




ll cnt_rep = 0;
ll powmod(ll N, ll P, ll M){
  cnt_rep++;
  if(P == 0) return 1;
  if(P%2 == 0){
    ll t = powmod(N, P/2, M);
    return t*t % M;
  }
  return (N * powmod(N, P-1, M)) % M;
}


ll gcd(ll a, ll b){
  ll resi, g, l;
  if(a > b){
    g = a; l = b;
  }else if(b > a){
    g = b; l = a;
  }else{
    return a;
  }
  resi = g % l;
  if(resi != 0){
    return gcd(l, resi);
  }else{
    return l;
  } 
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

int ans = 0;
int N, M, Q;

template<typename T>
void showall(vector<T> v){
  rep(i, 0, v.size()){
    cout << v[i] << " ";
  }
  cout << endl;
}

template<typename T>
ll com(T n, T m, T mod){
  ll a = 1, b = 1, ans;
  if(n == m || m == 0){
    ans = 1;
  }else{
    for(ll i = 0;i < m; i++){
      a *= n-i;
      a %= mod;
      b *= i+1;
      b %= mod;
    }
    ans = (a * powmod(b, mod-2, mod)) % mod;
  }
  
  return ans;
}



int main() {
  char a;
  cin >> a;

  if(isupper(a)){
    cout << "A" << endl;
  }else{
    cout << "a" << endl;
  }

  
  
  // cout << setprecision(8) << ans << endl;  // For double
}



Measured memory_bytes: 3588
#include <stdio.h>

int main(void){

  char s[11];
  scanf("%s", s);

  if (s[5] == '1') {
    printf("TBD\n");
  } else if (s[6] > '4') {
    printf("TBD\n");
  } else {
    printf("Heisei\n");
  }

  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

class Main{

	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String s;
		if(a < b){
			s = "a < b";
		}else if(a > b){
			s = "a > b";
		}else{
			s = "a == b";
		}
		System.out.println(s);
	}
}


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


int MOD=1000000007;


int main(){
    int N,D;
    cin >> N >> D;
    if(N%(D*2+1)==0) cout << N/(D*2+1) << endl;
    else cout << N/(D*2+1)+1 << endl;
}


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

vector<int> sub(string s) {
  vector<int> ret;
  map<char, int> mp;
  int cnt = 0;
  for (char c : s) {
    if (!mp.count(c)) {
      mp[c] = cnt;
      ++cnt;
    }
    ret.push_back(mp[c]);
  }
  return ret;
}

string s, t;
int main() {
  cin >> s >> t;
  cout << (sub(s) == sub(t) ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 3324
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>


#define ll long long int

using namespace std;

int main() {
    const double PI  =3.141592653589793238463;
    int a,b,h,m;
    cin >> a >> b >> h >> m;

    double w1 = 2*PI * (h + 1.0*m/60) / 12;
    double w2 = 2*PI * m / 60;
    double alpha = abs(w2 - w1);
    double res = sqrt(a*a + b*b - 2*a*b*cos(alpha));
    cout << setprecision(10) << res << endl;
    return 0;
}

Measured memory_bytes: 4180
M,z,s=998244353,1,0
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for _ in'_'*input():
 a=input();s+=a;i=s;z*=3
 while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z-=d[i]*3;i-=1
print(z+~s%2*e[i+1]*3)%M

Measured memory_bytes: 157732
#include <iostream>
using namespace std;
int n, a[200009], s[200009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n;
	int c = 1;
	long long cur = 0, sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		while (a[i] <= a[s[c - 1]]) {
			c--;
			cur -= 1LL * a[s[c]] * (s[c] - s[c - 1]);
		}
		cur += 1LL * a[i] * (i - s[c - 1]);
		s[c++] = i;
		sum += cur;
	}
	cout << sum << "\n";
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct data{
  bool isNull;
  ll mini;
  ll sum;
  data(){
    isNull=true;
  }
};

data merge(const data &a,const data &b){
  if(a.isNull)return b;
  if(b.isNull)return a;
  data d;
  d.isNull=false;
  d.mini=min(a.mini,b.mini);
  d.sum=a.sum+b.sum;
  return d;
}

struct segtree{
  int size;
  vector< data > t;
   
  void init(int n=1){
    t.clear();
    size=1;
    while(size<n)size*=2;
    t.resize(size*2);
  }

  void Update(int i,ll value){
    i+=(size-1);
    t[i].isNull=false;
    t[i].mini=value;
    while(i){
      i=(i-1)/2;
      t[i]=merge(t[i*2+1],t[i*2+2]);
    }
  }
  
  
  data Dfs(int a,int b,int k,int l,int r){
    if(b<=l || r<=a)return data();
    if(a<=l && r<=b)return t[k];
    int m=(l+r)/2;
    data lc=Dfs(a,b,k*2+1,l,m);
    data rc=Dfs(a,b,k*2+2,m,r);
    return merge(lc,rc);
  }
  
  ll getMin(int a,int b){
    return Dfs(a,b,0,0,size).mini;
  }
};

segtree T;
 
int main(){

   
  int n,q;
  scanf("%d %d",&n,&q);
  T.init(n);
  for(int i=0;i<n;i++){
    T.Update(i, INT_MAX);
  }
  while(q--){
    int type,a,b;
    scanf("%d %d %d",&type,&a,&b);
    if(type==0){
      T.Update(a,b);
    }else{
      printf("%lld\n", T.getMin(a,b+1) );
    }
  }
  return 0;
}




Measured memory_bytes: 8900
#include <bits/stdc++.h>
 
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>
#define debug cout << "Ok" << endl;

using namespace std;

void solve(){

	return;
}
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	int n,m, ma=0,tot;

	cin >> m >> n;
	vector<int>v(n);

	cin >> v[0];
	tot=v[0];
	for(int i=1;i<n;i++){
		cin >> v[i];
		ma = max(ma, abs(v[i] - v[i-1])); 
	}
		ma = max(ma, abs(v[0] + (m-v[n-1])  )); 

	cout << m - ma << endl;
	return 0;
}

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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int L = a + b;
  int R = c + d;
  
  if(L > R)puts("Left");
  else if(L == R)puts("Balanced");
  else puts("Right");
  
}

Measured memory_bytes: 256
N = gets.to_i
# [{}] * N だとバグる
DP = Array.new(N) { {} }

def dfs(k, his)
  return 1 if k == N
  return DP[k][his] if DP[k].include? his
  DP[k][his] = 'ACGT'.chars
    .select {|c|
      his + c !~ /AGC|GAC|ACG|A.GC|AG.C/
    }.map {|c|
      dfs(k + 1, his[1..-1] + c)
  }.inject(:+) % (10 ** 9 + 7)
end

p dfs(0, 'TTT')

Measured memory_bytes: 2684
a = input()
n = len(a)
count0 = 0    #start from 0
count1 = 0    #start from 1
for i in range(n):
    if i % 2 == 0 and int(a[i]) ==1:
        count0 = count0 +1
    elif i % 2 == 0 and int(a[i]) ==0:
        count1 = count1 +1
    elif i % 2 == 1 and int(a[i]) ==1:
        count1 = count1 +1
    elif i % 2 == 1 and int(a[i]) ==0:
        count0 = count0 +1

print(min(count0, count1))



Measured memory_bytes: 3188
import math as mt
a, b, h, m = list(map(int, input().split()))
h_e = 360/12
m_e = 360/60


ang = abs(h_e*(h + m/60) - m*m_e)
if ang > 180:
  ang = 180 - (ang%180)
print('{:.12f}'.format(mt.sqrt(a*a + b*b -2*a*b*mt.cos(ang/360*2*mt.pi))))

Measured memory_bytes: 9440
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repp(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define rrep(i, n, m) for (int i = n; i >= m; i--)
#define p(a, b) printf(a, b);
#define c(s) cout << (s) << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define cyn(c) cout << (c ? "Yes" : "No") << endl;
#define cYN(c) cout << (c ? "YES" : "NO") << endl;
#define pyn(c) printf("%s\n", c ? "Yes" : "No");
#define pYN(c) printf("%s\n", c ? "YES" : "NO");
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> P;
template <class T>
bool contain(const std::string &s, const T &v)
{
    return s.find(v) != std::string::npos;
}

int main() {
    int n,m; bool ok=false;
    char a[55][55]={},b[55][55]={};
    cin >> n >> m;
    rep(i,n)rep(j,n)cin>>a[i][j];
    rep(i,m)rep(j,m)cin>>b[i][j];

    rep(i,n-m+1){
        rep(j,n-m+1){
            bool flag = true;
            rep(k,m){
                rep(l,m){
                    if(a[i+k][j+l]!=b[k][l]){
                        flag = false;
                    }
                }
            }
            if(flag)ok=true;
        }
    }
    if(ok){
        yes;
    }else{
        no;
    }
}

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

int n;
vector<int> pre, in, post;
int p;

void dfs(int l, int r) {
  if ( l >= r ) return;
  int root = pre[p++];
  int mid = find(in.begin(), in.end(), root)-in.begin();  
  dfs(l, mid);
  dfs(mid+1, r);
  post.push_back(root);
}

int main() {
  cin >> n;

  pre = vector<int>(n);  
  for ( int i = 0; i < n; i++ ) cin >> pre[i];

  in = vector<int>(n);
  for ( int i = 0; i < n; i++ ) cin >> in[i];

  dfs(0, n);

  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << post[i];
  }
  cout << endl;

  return 0;
}



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

#define fs first
#define sc second
#define mp make_pair
#define eb emplace_back
#define sz(s) ((int) s.size())
#define all(s) s.begin(), s.end()

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef unsigned long long ull;

const ll linf = (ll) 1e18;

const int A = 26;
const int L = 17;
const int B = 315;
const int N = (int) 1e5;
const int inf = (int) 1e9;
const int mod = (int) 1e9 + 7;

const int di[] = {-1, +0, +1, +0};
const int dj[] = {+0, +1, +0, -1};

const ull pr = 31;
const ull hmod = (ull) 1e9 + 7;

const double pi = acos(-1.0);
const double eps = 1e-11;

inline void init() {
	
}
inline void solve() {
	int n; cin >> n;
	multiset<int> s;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		s.insert(x);
	}		
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		int x; cin >> x;
		auto it = s.find(x);
		if (it == s.end()) {
			puts("NO");
			return;
		} else {
			s.erase(it);
		}
	}
	puts("YES");
}
int main() {
	#ifdef LOCAL
		#define name ""
		freopen(name".in", "r", stdin);
		freopen(name".out", "w", stdout);
	#endif
	int tests = 1;
	while (tests--) {
		init();
		solve();
	}
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <complex>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#include <set>
#include <map>
#include <unordered_map>
#include <numeric>
#include <functional>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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; }
inline void Yes(bool condition){ if(condition) PRINT("Yes"); else PRINT("No"); }
template<class itr> void cins(itr first,itr last){
    for (auto i = first;i != last;i++){
        cin >> (*i);
    }
}
template<class itr> void array_output(itr start,itr goal){
    string ans = "",k = " ";
    for (auto i = start;i != goal;i++) ans += to_string(*i)+k;
    if (!ans.empty()) ans.pop_back();
    PRINT(ans);
}
ll gcd(ll a, ll b) {
    return a ? gcd(b%a,a) : b;
}
const ll INF = 1e15;
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
typedef pair<ll,ll> P;
typedef pair<double,double> point;
const ll MAX = 2000005;
constexpr ll nx[8] = {1,0,-1,0,1,-1,1,-1};
constexpr ll ny[8] = {0,1,0,-1,1,1,-1,-1};
ll RepeatSquaring(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P%2==0){
        ll t = RepeatSquaring(N, P/2, M);
        return t*t % M;
    }
    return N * RepeatSquaring(N, P-1, M)%M;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    cins(all(a));
    SORT(a);
    bool ok = 1;
    if (n%2){
        if (a[0] != 0) ok = 0;
        rep(i,1,n){
            if (a[i] != (i+1)/2*2) ok = 0;
        }
        if (ok){
            PRINT(RepeatSquaring(2,n/2,MOD));
        }
        else{
            PRINT(0);
        }
    }
    else{
        rep(i,n){
            if (a[i] != i/2*2+1) ok = 0;
        }
        if (ok){
            PRINT(RepeatSquaring(2,n/2,MOD));
        }
        else{
            PRINT(0);
        }
    }
}


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

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

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

    int n, k;   cin >> n >> k;
    string s;   cin >> s;

    string res = s;

    char a = *min_element(all(s));

    function<void(string,int)>  dfs = [&](string S,int b)   {
        if (S == string(n,a))   {
            res = S;
            return;
        }
        if (b > k)  {
            if (res > S)
                res = S;
            return;
        }
        string R = S;   reverse(all(R));
        R = S + R;

        int cnt = 0;
        int len = 0;

        for(int i = 0 ; i < n + n ; ++i)    {
            if (R[i] == a)
                cnt++;
            else
                cnt = 0;

            if (len < cnt)
                len = cnt;
        }
        cnt = 0;

        for(int i = 0 ; i < n + n ; ++i)    {
            if (R[i] == a)
                cnt++;
            else
                cnt = 0;

            if (cnt == len) {
                int l = (b < k ? i - n : i - len) + 1;

                if (l < 0)  continue;
                if (l > n)  continue;

                dfs(string(R.begin() + l,R.begin() + l + n),b + 1);
            }
        }
    };

    dfs(s,1);

    cout << res << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "-----------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    ll n, a, b, c, d, e; cin >> n >> a >> b >> c >> d >> e;
    ll m = min({ a,b,c,d,e });
    cout << 4LL + (n + m - 1) / m << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
    fast;
    int a,b;
    cin>>a>>b;
    if(a<b*2)
    {
        cout<<0<<endl;
    }
    else
        cout<<a-b*2<<endl;
    
    
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
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;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll N;
ll X[202020],XX;
__int128 S[202020];
__int128 ans=1LL<<60;

std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}


int main(){
  cin>>N>>XX;
  RREP(i,N){
    cin>>X[i];
    S[i]=S[i-1]+X[i];
  }
  
  for(int i=1; i<=N; ++i){
    __int128 cnt=XX*i;
    
    int left=N;
    int step=1;
    while(left>0){
      if(step==1) cnt+=5*(S[left]-S[max(left-i,0)]);
      else cnt+=(2*step+1)*(S[left]-S[max(left-i,0)]);
      left-=i;
      step++;
    }
    
    chmin(ans,cnt);
  }
  
  cout<<ans+XX*N<<endl;
  return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
char v[1005][1005];
int dp[1005][1005];
int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> v[i][j];
    for(int i = 0; i < n; i ++)
    {
        if(v[i][0] == '#')
            break;
        dp[i][0] = 1;
    }
    for(int i = 0; i < m; i ++)
    {
        if(v[0][i] == '#')
            break;
        dp[0][i] = 1;
    }
    for(int i = 1; i < n; i ++)
        for(int j = 1; j < m; j ++)
            if(v[i][j] != '#')
                dp[i][j] = dp[i - 1][j] % 1000000007 + dp[i][j - 1] % 1000000007;
    cout << dp[n - 1][m - 1] % 1000000007;
    return 0;
}


Measured memory_bytes: 5120
t=int(input())
b=[int(i) for i in input().split()]
a=[0]*t 
a[0]=b[0]
for i in range(1,t):
    if i<t-1:
        if b[i-1] < b[i]:
                a[i] = b[i-1]
        else:
            a[i] = b[i]
    else:
        a[i]=b[i-1]
print(sum(a))

Measured memory_bytes: 3064
N,W = map(int,input().split())
w1,v1 = map(int,input().split())
d = [[-v1],[],[],[]]
for i in range(N-1):
    w,v = map(int,input().split())
    x = w - w1
    d[x].append(-v)
d[0].sort()
n0 = len(d[0])
d[1].sort()
n1 = len(d[1])
d[2].sort()
n2 = len(d[2])
d[3].sort()
n3 = len(d[3])
s0 = [0]
s1 = [0]
s2 = [0]
s3 = [0]
for i in range(n0):
    x = s0[-1] + d[0][i]
    s0.append(x)
for i in range(n1):
    x = s1[-1] + d[1][i]
    s1.append(x)
for i in range(n2):
    x = s2[-1] + d[2][i]
    s2.append(x)
for i in range(n3):
    x = s3[-1] + d[3][i]
    s3.append(x)
d = [[[[0 for i in range(n3+1)] for j in range(n2+1)] for k in range(n1+1)] for l in range(n0+1)]
for i in range(n0+1):
    for j in range(n1+1):
        for k in range(n2+1):
            for l in range(n3+1):
                s = s0[i] + s1[j] + s2[k] + s3[l]
                s = -s
                x = w1*(i+j+k+l) + j + 2*k + 3*l
                if x <= W:
                    d[i][j][k][l] = s
ans = 0
for i in range(n0+1):
    for j in range(n1+1):
        for k in range(n2+1):
            for l in range(n3+1):
                x = d[i][j][k][l]
                ans = max(ans,x)
print(ans)

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

int main()
{
int A,B,ans=1;scanf("%d %d",&A,&B);
if(B==1){printf("0\n");return 0;}
B-=A;
while(B>0){B=B-A+1;ans++;}
printf("%d\n",ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 10;
int A[MAX],sum1[MAX],sum2[MAX];
int main ()
{
    int N;cin >> N;
    for(int i=1;i<=N;i++)cin >> A[i];
    for(int i=1;i<=N;i++)
    {
        if(i%2)
        {
            sum1[i]=sum1[i-1]-A[i];
            sum2[i]=sum2[i-1]+A[i];
        }
        else
        {

            sum1[i]=sum1[i-1]+A[i];
            sum2[i]=sum2[i-1]-A[i];
        }
    }
    /*for(int i=1;i<=N;i++)cout<<sum1[i]<<" ";
    cout<<endl;
    for(int i=1;i<=N;i++)cout<<sum2[i]<<" ";
    cout<<endl;*/
    int x1 = sum2[N]/2;
    cout<<2*x1;
    for(int i=2;i<=N;i++)
    {
        if(i>1)cout<<" ";
        if(i%2){
                cout<<2*(x1+sum1[i-1]);
        }
        else{
            cout<<2*(sum2[i-1]-x1);
        }
    }
    cout<<endl;
    return 0;
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long
#define mod 1000000007
#define IINF INT_MAX
#define INF 1LL << 30


int main() {
    int n, k; cin >> n >> k;
    k--;
    string s; cin >> s;

    for(int i = 0; i < n; i++){
        if(i == k){
            if(s[i] == 'A') cout << 'a';
            if(s[i] == 'B') cout << 'b';
            if(s[i] == 'C') cout << 'c';
        }else{
            cout << s[i];
        }
    }
    cout << "\n";

    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main
{
	public static void main(String[] args) 
	{
		Scanner in=new Scanner(System.in);
		for(;;)
		{
			int n=in.nextInt();
			if(n==0)
				return;
			int a[]=new int[n];
			for(int i=0;i<n;i++)
				a[i]=in.nextInt();
			Arrays.sort(a);
			
			long ans=0;
			long wai=0;
			for(int i=0;i<n;i++)
			{
				ans+=wai;
				wai+=a[i];
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int w,h,n;
int x[105],y[105],a[105];
int l,r,u,d;
int main(void){
	cin>>w>>h>>n;
	l=0; r=w; u=h; d=0;
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i]>>a[i];
		if(a[i]==1){
			l=max(l,x[i]);
		}else if(a[i]==2){
			r=min(r,x[i]);
		}else if(a[i]==3){
			d=max(d,y[i]);
		}else{
			u=min(u,y[i]);
		}
	}
	if(r-l<=0||u-d<=0){
		cout<<0<<endl;
	}else{
		cout<<(r-l)*(u-d)<<endl;
	}
	
	
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <stack>
#include <cassert>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int a[N];
int n;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie();
    
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a, a + n);
    for(int i = 1; i < n; ++i) {
        if(a[i] == a[i-1]) {
            cout << "NO\n";
            return 0;
        }
    }
    cout << "YES\n";
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n, l;
int a[200000];	//a[i] = 高橋家から反時計回りに歩くとき、i(>=0)番目に遭遇する木までの移動距離
int b[200000];	//b[i] = 高橋家から時計回りに歩くとき、i(>=0)番目に遭遇する木までの移動距離
int ra[200001];	//ra[i] = a[0]+…+a[i-1], ただしra[0] = 0
int rb[200001];	//rb[i] = b[0]+…+b[i-1], ただしrb[0] = 0

int solve(int ra[], int rb[], int a[], int b[]) {
	int i;
	int ret = 0;
	
	//最初はi番目の木に遭遇するまで、時計回りに移動する
	for (i = 0; i < n; i++) {
		int m = n - i;
		int cost;
		if (m % 2 == 1) {	//a->b->a->…->a
			cost = 
			2 * (ra[i + (m + 1) / 2] - ra[i]) + 
			2 * rb[m / 2] - 
			a[i + m / 2];
		}
		else {
			cost = 
			2 * (ra[i + m / 2] - ra[i]) +
			2 * (rb[m / 2]) - 
			b[m / 2 - 1];
		}
		ret = max(ret, cost);
	}
	return ret;
}

signed main() {
	int i;
	
	cin >> l >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i];
		b[n - 1 - i] = l - a[i];
	}

	ra[0] = 0;
	rb[0] = 0;
	for (i = 1; i <= n; i++) {
		ra[i] = ra[i - 1] + a[i - 1];
		rb[i] = rb[i - 1] + b[i - 1];
	}
	
	int ans1 = solve(ra, rb, a, b);	//最初、反時計回りに移動する
	int ans2 = solve(rb, ra, b, a);	//最初、時計回りに移動する(この場合は円を裏返して解けばOK）
	cout << max(ans1, ans2) << endl;
	return 0;
}

Measured memory_bytes: 6528