akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
// #define mp make_pair
#define nt _int128 
#define fir first
#define sec second
#define fast_as_levi ios_base::sync_with_stdio(false) , cin.tie(NULL);
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define inf 0x3f3f3f3f
 
const ll mod = 1e9 + 7;
const ll mx = 2e6 + 5;
const ll mxi = 2e3 + 5;


int main()
{
    fast_as_levi;
    ll i,j,n;
    cin>>n;
    ld dp[n+1][n+1];
    ld ar[n+1];
    for(i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    
    for(i=1;i<=n;i++)
    {
        for(j=0;j<=i;j++)
        {
            if(j>0)
            {
                dp[i][j] += dp[i-1][j-1] * ar[i-1];     //for heads showing up 
            }
            dp[i][j] += dp[i-1][j] * (1-ar[i-1]);       //for tails showing up
        }
    }
    // for(i=0;i<=n;i++)
    // {
    //     for(j=0;j<=n;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    
    
    //The answer would be the sum of all cases, where number of heads are greater than tails,
    // i.e, we get heads more than in more than half of the cases when any set of coins are tossed 
    // or , where i > N/2.

    ld ans = 0;
    for(i=0;i<=n;i++)
    {
        if(i>n/2)
        ans += dp[n][i];
    }
    cout<<setprecision(12)<<ans;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

int a, b, c, d, x, y;

int main() {
    cin >> a >> b;
    ll ans = a * b;
    if (a >= 10 || b >= 10) ans = -1;
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  int n;
  cin>>n;
  map<int,int> cnt;
  for(int x=1;x*x<n;x++){
    for(int y=1;y*y<n;y++){
      for(int z=1;z*z<n;z++){
        cnt[x*x+y*y+z*z+x*y+y*z+z*x]++; 
      }
    }
  }
  rep(i,1,n+1){
   cout<<cnt[i]<<endl; 
  }
  
  
  
  
}

Measured memory_bytes: 5216
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use proconio::{input, marker::*};
use superslice::*;
fn main() {
    const LIMIT: usize = 2500;
    input! {
        n: usize, m: usize, s: usize,
        uvab: [(Usize1, Usize1, usize, usize); m],
        charge_time: [(usize, usize); n],
    }
    let s = s.min(LIMIT);

    let mut rails = vec![Vec::new(); n];
    for (st1, st2, fare, time) in uvab {
        rails[st1].push((st2, fare, time));
        rails[st2].push((st1, fare, time));
    }

    let mut dp = vec![vec![usize::max_value(); LIMIT+1] ;n];
    dp[0][s] = 0;
    
    let mut q = BinaryHeap::new();
    // Reverse(total_time), station, coin
    q.push((Reverse(0), 0, s));

    while let Some((Reverse(total_time), station, coin)) = q.pop() {
        for &(to, fare, time) in &rails[station] {
            let next_time = total_time + time;
            if coin >= fare && next_time < dp[to][coin - fare] {
                dp[to][coin - fare] = next_time;
                q.push((Reverse(next_time), to, coin - fare));
            }
        }
        if coin < LIMIT {
            let (charge_coin, charge_time) = charge_time[station];
            let next_coin = LIMIT.min(coin + charge_coin);
            let next_time = total_time + charge_time;
            if next_time < dp[station][next_coin] {
                dp[station][next_coin] = next_time;
                q.push((Reverse(next_time), station, next_coin));
            }
        }
    }

    for station in 1..n {
        let ans = dp[station].iter().cloned().min().unwrap();
        println!("{}", ans);
    }


    

}


Measured memory_bytes: 4768
//In the name of God:)
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define ll long long int
#define fast  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MAXN = 1e5 + 10;


int main(){
    int n , m;
    scanf("%d%d", &n , &m);
    printf("%d\n" , m * (m-1) / 2 + n * (n-1) / 2);
}


Measured memory_bytes: 256
N = int(input())
A = sorted([int(a) for a in input().split()])
X = A[-1]
Y = 0
mi = 1<<99
for i in range(N-1):
    if abs(X - A[i]*2) < mi:
        mi = X - A[i]*2
        Y = A[i]

print(X, Y)

Measured memory_bytes: 62704
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

struct pnt {
	int x, y;
	constexpr pnt(int x = 0, int y = 0) noexcept : x(x), y(y) {};
	constexpr bool operator==(const pnt &rhs) const noexcept { return x == rhs.x && y == rhs.y; }
	constexpr bool operator<(const pnt & rhs) const noexcept { return x < rhs.x || x == rhs.x && y < rhs.y; }
	constexpr pnt operator+(const pnt &rhs) const noexcept { return pnt(x + rhs.x, y + rhs.y); }
	constexpr pnt operator-(const pnt &rhs) const noexcept { return pnt(x - rhs.x, y - rhs.y); }
	constexpr pnt operator-() const noexcept { return pnt(-x, -y); }
	constexpr int operator*(const pnt &rhs) const noexcept { return x * rhs.x + y * rhs.y; }
	friend istream& operator>>(istream& is, pnt &p) { return is >> p.x >> p.y; }
	friend ostream& operator<<(ostream& os, const pnt &p) { return os << p.x << " " << p.y << "\n"; }
	constexpr pnt nor(const pnt &rhs) const noexcept { return pnt(rhs.y, -rhs.x); }
	template<class T> T& operator[](vector<vector<T>> &v) { return v[x][y]; }
};

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

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int H, W;
	cin >> H >> W;

	vector<vector<char>> grid(H, vector<char>(W));
	for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> grid[i][j];

	vector<vector<int>> visited(H, vector<int>(W, -1));
	queue<pnt> que;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (grid[i][j] == '#') {
				que.emplace(i, j);
				visited[i][j] = 0;
			}
		}
	}


	auto in_grid = [&](pnt &p) {return 0 <= p.x&&p.x < H && 0 <= p.y&&p.y < W; };
	int ans = 0;
	while (!que.empty()) {

		auto now = que.front();
		que.pop();

		vector<pnt> dxdy{ {-1,0},{1,0},{0,-1},{0,1} };
		for (const auto &e : dxdy) {

			auto next = now + e;
			if (in_grid(next) && next[visited] == -1) {
				next[visited] = now[visited] + 1;
				chmax(ans, next[visited]);
				que.emplace(next);
			}

		}

	}

	cout << ans << "\n";

	return 0;
}

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

typedef pair<long long, long long> p;

int main(void){
  int N,M;
  cin >> N >> M;

  string ans;
  if(N != M){
    ans = "No";
  }else{
    ans = "Yes";
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define INF 10000000001
#define DIM 200001
#define mod 1000000007
#define PI 3.1415926535897932384626433
#define se second
#define fi first
#define pb push_back
#define T true
#define F false
#define endl "\n"
typedef char ch;
typedef bool boll;
typedef string st;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef set < string > sst;
typedef set < long long > sl;
typedef queue < long long > que;
typedef vector < long long > vec;
typedef map < long long, long long > mll;
typedef pair < long long, long long > pll;
typedef vector < pair < long long, long long > > vpl;
typedef pair < long long, unsigned long long > pul;


int main(){
    int r;
    cin >> r;
    cout << (float)PI*2*r;
}


Measured memory_bytes: 3784
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll  long long
#define ull unsigned long long
#define IO ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#define main() int main()
#define ff1(i,n) for(int i=1;i<=n;++i)
#define ff0(i,n) for(int i=0;i<n;++i)
#define pi acos(-1.0)
#define ms(a, x) memset(a, x, sizeof(a))
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define binarycount __builtin_popcount(x)
#define tr t[root]
#define lson t[root << 1]
#define rson t[root << 1 | 1]
#define fir first
#define sec second
#define debug(x) cout<<x<<'\n'
#define sa(a) scanf("%d", &a)
#define sab(a, b) scanf("%d%d", &a, &b)
#define pa(a) printf("%d",a)
#define pab(a,b) printf("%d%d",a,b)
#define pii pair<int,int>
using namespace std;

#define maxn 10000005
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-8;
ll gcd(ll a, ll b) {return b==0?a:gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b)*b;}
ll powmod(ll a,ll b){
    ll ans = 1, pow = a%mod;
    while(b) { if(b&1) ans = (ans*pow)%mod; pow = (pow*pow)%mod; b >>= 1; }
    return ans%mod;
}
map<int,int> mp;
main(){
	
	string s;
	cin>>s;
	if(s=="ABC")cout<<"ARC"<<endl;
	else cout<<"ABC"<<endl;
}

Measured memory_bytes: 3636
#[doc = " https://github.com/hatoo/competitive-rust-snippets"]
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;
mod util {
    use std::fmt::Debug;
    use std::io::{stdin, stdout, BufWriter, StdoutLock};
    use std::str::FromStr;
    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }
    #[allow(dead_code)]
    pub fn chars() -> Vec<char> {
        line().chars().collect()
    }
    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
    #[allow(dead_code)]
    pub fn with_bufwriter<F: FnOnce(BufWriter<StdoutLock>) -> ()>(f: F) {
        let out = stdout();
        let writer = BufWriter::new(out.lock());
        f(writer)
    }
}
#[allow(unused_macros)]
macro_rules ! get { ( [ $ t : ty ] ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . split_whitespace ( ) . map ( | t | t . parse ::<$ t > ( ) . unwrap ( ) ) . collect ::< Vec < _ >> ( ) } } ; ( [ $ t : ty ] ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( [ $ t ] ) ) . collect ::< Vec < _ >> ( ) } ; ( $ t : ty ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; line . trim ( ) . parse ::<$ t > ( ) . unwrap ( ) } } ; ( $ ( $ t : ty ) ,* ) => { { let mut line : String = String :: new ( ) ; stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; let mut iter = line . split_whitespace ( ) ; ( $ ( iter . next ( ) . unwrap ( ) . parse ::<$ t > ( ) . unwrap ( ) , ) * ) } } ; ( $ t : ty ; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ ( $ t : ty ) ,*; $ n : expr ) => { ( 0 ..$ n ) . map ( | _ | get ! ( $ ( $ t ) ,* ) ) . collect ::< Vec < _ >> ( ) } ; }
#[allow(unused_macros)]
macro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , " = {:?}, " ) ,* ) , $ ( $ a ) ,* ) ; } }
const BIG_STACK_SIZE: bool = true;
#[allow(dead_code)]
fn main() {
    use std::thread;
    if BIG_STACK_SIZE {
        thread::Builder::new()
            .stack_size(32 * 1024 * 1024)
            .name("solve".into())
            .spawn(solve)
            .unwrap()
            .join()
            .unwrap();
    } else {
        solve();
    }
}
fn solve() {
    let (n, k) = get!(usize, usize);
    let mut s = util::chars();
    s[k - 1] = s[k - 1].to_lowercase().next().unwrap();

    println!("{}", s.into_iter().collect::<String>());
}


Measured memory_bytes: 8572
s = input()
n = len(s)
s1 = s[:(n-1)//2]
s2 = s[(n+3)//2-1:]

ans = 'Yes'

if s != s[::-1]:
    ans = 'No'
if s1 != s1[::-1]:
    ans = 'No'
if s2 != s2[::-1]:
    ans = 'No'

print(ans)


Measured memory_bytes: 3060
# じょえチャンネルおもしろいよ～～～
# https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ

#a,b,c,d=map(int,input().split())
s=input()
if len(set(list(s)))==2:print("Yes")
else:print("No")

Measured memory_bytes: 2940
//													\[T]/ Praise
//													 (*)  The
//													 / \  Sun



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

typedef long long ll;
typedef long double dbl;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<long long> vl;
typedef vector< pair<int, int> > vii;
#define mp make_pair
#define pb push_back
#define prinvec(a, n) for(ll i = 0; i < n; i++) cout << a[i] << " "; cout << "\n";
#define invec(a, n) for(ll i = 0; i < n; i++) {cin >> a[i];}
#define rep(n) for(ll i = 0; i < n; i++)
#define fr(i,j,k) for(ll i = j; i < k; i++)
#define FR(i,j,k) for(ll i = j; i >= 0; i--)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
#define INF 1000000
#define xx first
#define yy second

void fast()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

int main()
{

	#ifndef ONLINE_JUDGE
	freopen("/home/ram/Competitive Programming/IO/in.txt", "r", stdin);
	freopen("/home/ram/Competitive Programming/IO/out.txt", "w", stdout);
	#endif


	int n;
	cin >> n;

	ll sum = 0;

	for(int i = 1; i <= n; i++)
	{
		if(i % 3 == 0 || i % 5 == 0)
		{

		}
		else
			sum += i;
	}

	cout << sum;
}

Measured memory_bytes: 3592
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<int, int> P;
int main(){
    ll n,d;
    cin >> n>> d;
    ll ans=0;
    rep(i,n){
        ll x,y;
        cin >> x>>y;
        if(x*x+y*y<=d*d){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3632
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  str s;
  cin >> s;
  ll k;
  cin >> k;
  REP(i,s.length()){
    if(s[i]!='1'&&k>i){
      cout << s[i] << endl;
      return 0;
    }
  }
  cout << 1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <map>
using namespace std;
long long C(long long n){
    long long S = 1;
    for(long long i = n; i > n - 2; i--){
        S *= i;
    }
    return S / 2;
}
int main(void){
    long long N;
    cin >> N;
    vector<long long> A(N);
    for(long long i = 0; i < N; i++) cin >> A[i];
    map<long long,long long> mp;
    for(long long i = 0; i < N; i++){
        if(mp.count(A[i])){
            mp[A[i]]++;
        }
        else mp[A[i]] = 1;
    }
    long long S = 0;
    for(auto p : mp){
        S += C(p.second);
    }
    for(long long i = 0; i < N; i++){
        cout << S - C(mp[A[i]]) + C(mp[A[i]]-1) << endl;
    }
}    

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

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(b/a < c) cout << b/a << endl;
  else cout << c << endl;
}

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

#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define FOR(i,l,r) for(long long i=l; i<r; i++)
#define FOR_REV(i,r,l) for(long long i=r; i>=l; i--)
#define pb push_back
#define mp make_pair

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

    string s;
    int max = INT_MIN;
    map <string, int> m;
    FOR(i,0,n)
    {
        cin>>s;
        m[s]++;

        if (m[s] > max)
        {
            max = m[s];
        }
    }

    // sort(m.begin(), m.end());

    for (auto it=m.begin(); it!=m.end(); it++)
    {
        if (it->second == max)
        {
            cout<<it->first<<endl;
        }
    }
}


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

int main() {
	char S[200001], T[200001], flg = 1, word;
	int i, j, soeji[200001], k, soeji2[200001], k2;

	scanf("%s", S);
	scanf("%s", T);

	for (word = 'a'; word <= 'z' && flg == 1; word++) {
		k = 0;
		k2 = 0;
		for (i = 0; i < strlen(S); i++) {
			if (S[i] == word) {
				soeji[k] = i;
				k++;
			}
			if (T[i] == word) {
				soeji2[k2] = i;
				k2++;
			}
		}
		if (k >= 2) {
			for (j = 1; j < k && flg == 1; j++) {
				if (T[soeji[j - 1]] != T[soeji[j]]) {
					flg = 0;
				}
			}
		}
		if (k2 >= 2) {
			for (j = 1; j < k2 && flg == 1; j++) {
				if (S[soeji2[j - 1]] != S[soeji2[j]]) {
					flg = 0;
				}
			}
		}
	}

	if (flg == 1) {
		printf("Yes");
	}
	else {
		printf("No");
	}

	return 0;
}

Measured memory_bytes: 1280
#include <stdio.h>

int main(void)
{
	int m, f, r;
	
	while (1) {

		scanf("%d %d %d", &m, &f , &r);

		if (m == -1 && f == -1 && r == -1) {
			break;
		}

		if (m == -1 || f == -1) {
			puts("F");
		}
		else if (m + f >= 80) {
			puts("A");
		}
		else if (m + f >= 65 && m + f < 80) {
			puts("B");
		}
		else if (m + f >= 50 && m + f < 65) {
			puts("C");
		}
		else if (m + f >= 30 && m + f < 50) {
			if (r >= 50) {
				puts("C");
			}
			else {
				puts("D");
			}
		}
		else {
			puts("F");
		}
		
	}

	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
long long x[maxn+5],a[maxn+5];
long long sum[maxn+5],ans;
int n;
long long c;
multiset<long long> s;
int main()
{
    scanf("%d%lld",&n,&c);
    for(int i=1;i<=n;++i) scanf("%lld%lld",&x[i],&a[i]);
    ans=0;
    for(int i=1;i<=n;++i)
    {
        sum[i]=sum[i-1]+a[i];
        ans=max(ans,sum[i]-x[i]);
    }
    for(int i=1;i<=n;++i) ans=max(ans,sum[n]-sum[i-1]-(c-x[i]));
    //printf("%lld\n",ans);
    for(int i=1;i<=n;++i)
        s.insert(sum[n]-sum[i-1]-(c-x[i]));
    for(int i=1;i<n;++i)
    {
        long long now=sum[i]-2*x[i];
        s.erase(s.find(sum[n]-sum[i-1]-(c-x[i])));
        ans=max(ans,now+*s.rbegin());
        //printf("%lld %lld\n",now,*s.rbegin());
    }
    s.clear();
    for(int i=1;i<=n;++i) s.insert(sum[i]-x[i]);
    for(int i=n;i>1;--i)
    {
        long long now=sum[n]-sum[i-1]-2*(c-x[i]);
        s.erase(s.find(sum[i]-x[i]));
        ans=max(ans,now+*s.rbegin());
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 7296
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
s = [int(i) for i in STR()]
flag = False
cnt = 0
for i in range(n + 1):
    if s[i] == 1:
        cnt += 1
    else:
        cnt = 0
    if cnt >= m:
        print(-1)
        exit()
ans = []
hr = n
while hr > 0:
    for i in reversed(range(1, m + 1)):
        if 0 <= hr - i <= n and s[hr - i] == 0:
            ans.append(i)
            hr -= i
            break
ans = list(reversed(ans))
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(' '.join(ans))


Measured memory_bytes: 71256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	long long int n,initial=100,year=0;
	cin>>n;
	while(1){
		initial=initial*1.01;
		year++;
		if(initial>=n){
			cout<<year;
			return 0;
		}
	}
    return 0;
}

Measured memory_bytes: 3636
import sys
n = int(input())
a = [int(input()) for _ in range(n)]
i = 0
count = 1
x = [0]*n
while True:
    if a[i] == 2:
        print(count)
        sys.exit()
    if x[i] == 0:
        x[i] = 1
        i = a[i]-1
        count += 1
    else:
        print(-1)
        sys.exit()

Measured memory_bytes: 7852
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;

ll divisor(ll n)
{
    ll i,cnt=0,lim=sqrt(n);
    for(i=1; i<=lim; i++)
    {
        if(n%i==0)
        {
            if(n/i==i)
                cnt++;
            else
                cnt+=2;
        }
    }
    return cnt;
}

int main()
{
    fast_io
    ll i,j,n,ans=0;
    cin>>n;
    for(i=1; i<=n; i+=2)
    {
        ll x=divisor(i);
        if(x==8){
           // cout<<i<<" "<<x<<endl;
            ans++;
        }
    }

    cout<<ans<<endl;




    return 0;
}





Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
int main()
{
    unsigned long long n,i,j,k,a,b,c,d,e;
    cin>>n;
    unsigned long long arr[n],ans=0;
    for(i=0; i<n; i++)
        cin>>arr[i];
    for(i=0; i<60; i++)
    {
        k=0;
        for(j=0; j<n; j++)
        {
            c=arr[j];
            for(int p=0;p<i;p++)c/=2;
            if(c%2)
                k++;
        }
        d=1;
        for(int p=0;p<i;p++)d*=2;
        d%=mod;
        e=((k)*(n-k));
        e%=mod;
        ans+=d*e;
        ans%=mod;
    }
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 2560
a,b,k = map(int,input().split())
def cf(x1,x2):
    cf = []
    for i in range(1,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf
print(cf(a,b)[-k])

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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define foreach(it, v) for(typeof(v.begin()) it=v.begin(); it!=v.end(); ++it)
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second

typedef unsigned int uint;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef set<int> si;

//MOD//
const ll MOD = 1000000007;
struct big;
big ex(big a, ll tms);
typedef struct big{
  ll val;
  big():val(0){}
  big(ll val):val((val%MOD+MOD)%MOD){}
  big& operator += (const big& obj){ (val+=obj.val)%=MOD; return *this;}
  big& operator -= (const big& obj){ (val+=MOD-obj.val)%=MOD; return *this;}
  big& operator *= (const big& obj){ (val*=obj.val)%=MOD; return *this;}
  big& operator /= (const big& obj){ (val*=ex(obj,MOD-2).val)%=MOD; return *this;}
  big operator + (const big& obj)const{ return big(*this) += obj;}
  big operator - (const big& obj)const{ return big(*this) -= obj;}
  big operator * (const big& obj)const{ return big(*this) *= obj;}
  big operator / (const big& obj)const{ return big(*this) /= obj;}
  bool operator < (const big& obj)const{ return val < obj.val;}
  bool operator == (const big& obj)const{ return val == obj.val;}
} big;
istream& operator >> (istream& i, big& obj){ i>>obj.val; return i;}
ostream& operator << (ostream& o, const big& obj){ o<<obj.val; return o;}
big ex(big obj, ll tms){
  if(!tms) return 1;
  big ret = ex(obj, tms/2);
  ret *= ret;
  return (tms&1) ? ret*obj : ret;
}
//MOD//

ll pow(ll n, int m){
  if(!m) return 1;
  ll ret = pow(n, m/2);
  ret *= ret;
  return (m&1) ? ret*n : ret;
}

template <class F, class T>
void convert(const F &f, T &t){
  stringstream ss;
  ss << f;
  ss >> t;
}

int N;
ll A, B;

ll ma[5010];

int main(){
  scanf("%d%lld%lld",&N,&A,&B);
  vi p(N);
  rep (i, N) scanf("%d", &p[i]);
  rep (i, N) ma[i+1] = 999999999999999;
  rep (i, N) {
    int x = p[i];
    ll mai = 999999999999999;
    for (int j=0; j<x; ++j) {
      mai = min(mai, ma[j]);
      ma[j] = ma[j]+A;
    }
    for (int j=x+1; j<=N; ++j) ma[j] = ma[j]+B;
    ma[x] = mai;
  }
  ll ans = 999999999999999;
  rep (i, N+1) ans = min(ans, ma[i]);
  cout << ans << endl;

  return 0;
}



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

typedef long long ll;

const int N = 2010;
int n, m;
int a[N], b[N], c[N];
ll d1, d2;
vector<ll> d(N, -0x3f3f3f3f3f3f3f3f);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        --a[i];
        --b[i];
    }
    d[0] = 0;
    for (int i = 0; i < n * 2; ++i) {
        for (int j = 0; j < m; ++j) {
            d[b[j]] = max(d[b[j]], d[a[j]] + c[j]);
        }
        if (i == n - 1)
            d1 = d[n - 1];
        else if (i == n * 2 - 1)
            d2 = d[n - 1];
    }
    if (d1 == d2)
        cout << d1 << endl;
    else
        cout << "inf" << endl;

    return 0;
}



Measured memory_bytes: 3640
N = int(input())
R = [_ for _ in range(N)]
for i in range(N):
    x, y, h = [int(_) for _ in input().split()]
    R[i] = (h, x, y)

R.sort(reverse=True)

def solve():
    for cx in range(101):
        for cy in range(101):
            h, x, y = R[0]
            H = h + abs(x - cx) + abs(y - cy)
            for i in range(1, N):
                h, x, y = R[i]
                if h == 0 and H < abs(x - cx) + abs(y - cy):
                    continue

                tempH = h + abs(x - cx) + abs(y - cy)
                if tempH != H:
                    break
            else:
                print(cx, cy, H)
                return

solve()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std ; 
# define pb push_back
# define ll long long 
# define endl "\n"

void solve() {
	int n ; 
  	cin >> n ; 
  	
  	int r=  n  % 1000 ;	
  	if(r == 0)
  		cout << 0 ; 
  	else 
  		cout << 1000 - r ;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; 
   	int t; 
   	t=1; 
   	while(t--) {
   		//cout << "ANS : " ;
   		solve() ; 
   	}
    return 0; 
}

 

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


int main(int argc, char const *argv[]){
    int N;
    cin>>N;
    int ans=0;
    for(int i = 1; i <= N; i++)
    {
        ans=ans+i;
    }
        cout<<ans<<endl;
        
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		long ans = 0;
		int a[] = new int[100000];
		for(int i=0;i<n;i++) {
			int now = scan.nextInt();
			a[now-1] += 1;
			ans += now;
			
		}
		
		int q = scan.nextInt();
		
		for(int i=0;i<q;i++) {
			int b = scan.nextInt();
			int c = scan.nextInt();
			
			ans = ans+(c-b)*a[b-1];
			System.out.println(ans);
			
			a[c-1] += a[b-1];
			a[b-1] = 0;
			
			
		}
		
		
	}
}
 


Measured memory_bytes: 61264
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;


public class Main {
	
	public static final int[][] move_dir = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	
	public static boolean is_ok(int x, int y, int w, int h){
		if(x < 0 || x >= w || y < 0 || y >= h){
			return false;
		}else{
			return true;
		}
	}
	
	public static void change(int x, int y, int prev_color, int next_color, int[][] map, int h, int w){
		if(map[y][x] != prev_color){
			return;
		}
		map[y][x] = next_color;
		
		for(int[] move : move_dir){
			final int nx = x + move[0];
			final int ny = y + move[1];
			
			if(!is_ok(nx, ny, w, h)){
				continue;
			}else if(map[ny][nx] != prev_color){
				continue;
			}
			
			change(nx, ny, prev_color, next_color, map, h, w);
		}
	}
	
	public static int count(int x, int y, int[][] map, int h, int w){
		int ret = 0;
		
		final int color = map[y][x];
		map[y][x] = Integer.MAX_VALUE;
		
		for(int[] move : move_dir){
			final int nx = x + move[0];
			final int ny = y + move[1];
			
			if(!is_ok(nx, ny, w, h)){
				continue;
			}else if(map[ny][nx] != color){
				continue;
			}
			
			ret += count(nx, ny, map, h, w);
		}
		
		return ret + 1;
	}
	
	public static int[][] clone(int[][] array, int h, int w){
		int[][] ret = new int[h][w];
		
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				ret[i][j] = array[i][j];
			}
		}
		
		return ret;
	}
	
	public static void copy(int[][] dst, int[][] src, int h, int w){
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				dst[i][j] = src[i][j];
			}
		}
	}
	
	public static int dfs(int[][] map, int pur_color, int deep, int h, int w){
		if(deep == 0){
			if(map[0][0] != pur_color){
				return 0;
			}else{
				return count(0, 0, map, h, w);
			}
		}
		
		int[][] prev = clone(map, h, w);
		int ret = 0;
		
		for(int color = 1; color < 7; color++){
			if(color == map[0][0]){
				continue;
			}
			
			change(0, 0, map[0][0], color, map, h, w);
			
			ret = Math.max(ret, dfs(map, pur_color, deep - 1, h, w));
			
			copy(map, prev, h, w);
		}
		
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			final int h = sc.nextInt();
			final int w = sc.nextInt();
			final int c = sc.nextInt();
			
			if(h == 0){
				break;
			}
			
			int[][] map = new int[h][w];
			
			for(int i = 0; i < h; i++){
				for(int j = 0; j < w; j++){
					map[i][j] = sc.nextInt();
				}
			}
			
			System.out.println(dfs(map, c, 5, h, w));
		}
	}
}

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

using namespace std;

typedef long long ll;

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORd(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second

const int N=2e5;

map <ll,ll> dd;

int main()
{
    int n,a[N];
    cin >> n;
    ll ans=0;
    FOR(i,1,n) {
        cin >> a[i];
        dd[a[i]]++;
    }
    FOR(i,1,N) if (dd[i]!=0) ans+=dd[i]*(dd[i]-1)/2;
    FOR(i,1,n) cout << ans-dd[a[i]]+1 << endl;
}


Measured memory_bytes: 15872
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,i,j,x,num[105],ans,mi=1ll<<55;
int main()
{
	cin>>n;
	for (i=1;i<=n;i++) cin>>num[i];
	for (i=-100;i<=100;i++)
	{
		ans=0;
		for (j=1;j<=n;j++) ans+=sqr(i-num[j]);
		mi=min(mi,ans);
	}
	cout<<mi;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int D = sc.nextInt();
    int[][] points = new int[N][D];
    for (int i = 0; i < N; i++) for (int j = 0; j < D; j++) points[i][j] = sc.nextInt();
    int ans = 0;
    for (int i = 0; i < N; i++) {
      for (int j = i+1; j < N; j++) {
        double d = getDistance(points[i], points[j]);
        if (d == Math.ceil(d)) ans++;
      }
    }
    System.out.println(ans);
  }
  static double getDistance(int[] p1, int[] p2) {
    double ret = 0;
    for (int i = 0; i < p1.length; i++) {
      ret += Math.pow(p1[i]-p2[i],2);
    }
    return Math.sqrt(ret);
  }
}

Measured memory_bytes: 35624
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#define rep(i,l,n) for(lint i=l;i<n;i++)
#define rer(i,l,n) for(lint i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;


int main(){
	int q,c,a,n;
	cin>>q;
	rep(i,0,q){
		cin>>c>>a>>n;
		int res=0;
		int b=min(n,min(a,c));
		n-=b;
		c-=b;
		a-=b;
		res+=b;
		//o(" "<<res);
		b=min(a,c/2);
		a-=b;
		c-=2*b;
		res+=b;
		//o(" "<<res);
		res+=c/3;
		o(res);
	}
}

Measured memory_bytes: 1160
#include<cstdio>
using namespace std;
int main()
{
	int n;
	bool ans=false;
	scanf("%d",&n);
	if(n%10==9)ans=true;
	if(n/10%10==9)ans=true;
	if(ans)printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <stack>
#define Max 100000
using namespace std;
int n,x;
vector<int>G[Max];
int flag[Max];
int color[Max];

int dfs(int s)
{
    stack<int>S;
    int i;
    S.push(s);
    color[s]=x;
    while(!S.empty()){
        int u=S.top();
        for(i=0;i<G[u].size();i++)
        {
            if(!flag[G[u][i]])
            {
                //if(G[u][i]==t)return 1;
                flag[G[u][i]]=1;
                color[G[u][i]]=x;
                S.push(G[u][i]);
                break;
            }
        }
        if(i>=G[u].size())
            S.pop();
    }
    return 0;
}
int main()
{
    int m,u,v,q;
    cin>>n>>m;
    x=0;
    for(int i=0;i<n;i++)
        color[i]=x;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=0;i<n;i++)
    {
        if(!flag[i])
        {
            x++;
            dfs(i);
        }
    }
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>u>>v;
        if(color[u]==color[v])cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}


Measured memory_bytes: 9684
import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    FastScanner fs = new FastScanner();
    long A = fs.nextLong(), B = fs.nextLong(), K = fs.nextLong();
    System.out.print(Math.max(0, A - K) + " " + Math.max(0, B + Math.min(0, A - K)));
  }
}

class FastScanner {
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;

  private boolean hasNextByte() {
    if (ptr < buflen) {
      return true;
    } else {
      ptr = 0;
      try {
        buflen = in.read(buffer);
      } catch (IOException e) {
        e.printStackTrace();
      }
      if (buflen <= 0) {
        return false;
      }
    }
    return true;
  }

  private int readByte() {
    if (hasNextByte())
    return buffer[ptr++];
    else
    return -1;
  }

  private static boolean isPrintableChar(int c) {
    return 33 <= c && c <= 126;
  }

  public boolean hasNext() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr]))
    ptr++;
    return hasNextByte();
  }

  public String next() {
    if (!hasNext())
    throw new NoSuchElementException();
    StringBuilder sb = new StringBuilder();
    int b = readByte();
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  public long nextLong() {
    if (!hasNext())
    throw new NoSuchElementException();
    long n = 0;
    boolean minus = false;
    int b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b) {
      throw new NumberFormatException();
    }
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
      throw new NumberFormatException();
      }
      b = readByte();
    }
  }

  public int nextInt() {
    long nl = nextLong();
    if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
    throw new NumberFormatException();
    return (int) nl;
  }

  public double nextDouble() {
    return Double.parseDouble(next());
  }
}

Measured memory_bytes: 22612
// #include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;

#define all(x) begin(x), end(x)
#define rep(i,n) for(int i=0; i<n; i++)

struct UnionFind {
    vector<int> par, rank, _size;
    
    UnionFind(int n) : par(n), rank(n, 1), _size(n, 1) {
        for (int i=0; i<n; i++) par[i] = i;
    }
    
    int find(int x) {
        if (par[x]==x) return x;
        else return par[x] = find(par[x]);
    }

    bool same(int x, int y) {
        x = find(x); y = find(y);
        return x == y;
    }

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) return;

        _size[x] = _size[y] = _size[x] + _size[y];
        if(rank[x] == rank[y]) rank[y]++;

        if(rank[x] > rank[y]) par[y] = x;
        else par[x] = y;
    }

    int size(int x) {
        return _size[find(x)];
    }
};


int main() {
    // int n, m;
    ll n;
    int m;
    cin >> n >> m;

    int a[m], b[m];
    rep(i, m) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    ll ans[m];
    UnionFind island(n);
    ans[m-1] = n*(n-1)/2;

    for (int i=m-1; i>=0; i--) {
        ll size_a = island.size(a[i]);
        ll size_b = island.size(b[i]);
        if (island.same(a[i], b[i])) ans[i-1] = ans[i];
        else ans[i-1] = ans[i] - size_a*size_b;
        island.unite(a[i], b[i]);
    }

    rep(i, m) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 4096
import java.util.Scanner;

public class Main
{

	public static void main(String args[])
	{

		int count = 0;
		int temp = 0;

		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();
		int n = sc.nextInt();

		int [] p = new int[n];

		for(int i = 0; i < n; i++)
		{
			p[i] = sc.nextInt();
		}
		sc.close();

		for(int i = 0; i < n; i++)
		{
			if(x == p[i])
			{

				count++;

				temp = count;

				for(int j = 0; j < count; j++)
				{
					temp *= -1;
				}

				x += temp;

				i = -1;

			}
		}

		System.out.println(x);
	}

}


Measured memory_bytes: 27220
#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))
//-------------------------------------------------------

ll N,M,L,R;
ll mo=1000000007;
ll ret;

ll comb(ll N_, ll C_) {
	const int NUM_=700001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);}


ll pat(int a,int b,int ma) {
	ll tot=0;
	for(int over=0;over*b+M*a<=ma && over<=N-M;over++) {
		ll pat=comb(N-M,over)%mo*hcomb(N+1,ma-(over*b+M*a))%mo;
		if(over%2==0) {
			tot+=pat;
		}
		else {
			tot+=mo-pat;
		}
	}
	return (tot%mo+mo)%mo*comb(N,M)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>L>>R;
	
	for(i=L;i<=R;i++) ret+=hcomb(N,i);
	for(int la=1;la<=R;la++) {
		ret-=(pat(la,la,R)-pat(la+1,la,R))-(pat(la,la,L-1)-pat(la+1,la,L-1));
	}
	
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}


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: 16640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define pp pair<int,int>
#define ll long long
#define ld long double
int inf=100000000;
ll INF=4000000000000000000;
ll MOD=1000000007;


int main() {
   int a,b,c,d;
   cin >> a >> b >> c >> d;
   rep(i,d-b){
      cout << "U";
   }
   rep(i,c-a){
      cout << "R";
   }
   rep(i,d-b) cout << "D";
   rep(i,c-a) cout << "L";
   cout << "L";
   rep(i,d-b+1) cout << "U";
   rep(i,c-a+1) cout << "R";
   cout << "D";
   cout << "R";
   rep(i,d-b+1) cout << "D";
   rep(i,c-a+1) cout << "L";
   cout << "U" << endl;
  }

Measured memory_bytes: 256
N = int(input())
a_list = list(map(int, input().split()))

ans_list = [0]
for i in range(1, N):
    d = a_list[i-1] + ans_list[i-1] - a_list[i]
    if d > 0:
        ans_list.append(d)
    else:
        ans_list.append(0)
print(sum(ans_list))


Measured memory_bytes: 32220
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int c[3][3];
	int a[3];
	int b[3];
	rep(i,3)rep(j,3)cin >> c[i][j];
	a[0] = 0;
	b[0] = c[0][0] - a[0];
	b[1] = c[0][1] - a[0];
	b[2] = c[0][2] - a[0];
	a[1] = c[1][0] - b[0];
	a[2] = c[2][0] - b[0];
	rep(i,3)rep(j,3){
		if(c[i][j] == a[i]+b[j])continue;
		else {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}

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

int n,m;
int a[51],b[51];
int graph[51][51];
int visited[51];

void dfs(int v){
        visited[v] = true;
        for(int v2=0;v2<n;v2++){
                if(visited[v2]==true)    continue;
                if(graph[v][v2]==false) continue;
                dfs(v2);
        }
}

int main(){
        int ans = 0;
        cin >> n >> m;
        for(int i=0;i<m;i++){
                 cin >> a[i] >> b[i];
                 a[i]--,b[i]--;
                 graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
        }
        for(int i=0;i<m;i++){
                graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
                for(int j=0;j<n;j++)    visited[j] = false;
                dfs(0);
                bool bridge=false;
                for(int j=0;j<n;j++)    if(visited[j]==false) bridge = true;
                if(bridge)      ans++;
                 graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
        }
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 768
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                cnt = 0
                if 0 <= i - 1 < h and a[i-1][j] == "#":
                    cnt += 1
                if 0 <= i + 1 < h and a[i+1][j] == "#":
                    cnt += 1
                if 0 <= j - 1 < w and a[i][j-1] == "#":
                    cnt += 1
                if 0 <= j + 1 < w and a[i][j+1] == "#":
                    cnt += 1
                if cnt == 0:
                    print("No")
                    exit()
    print("Yes")


if __name__ == '__main__':
    slove()


Measured memory_bytes: 39024
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[200],ans[200];
char b[200];
int main(){
    int n;
    while(~scanf("%d",&n)){
        int p=0;
        while(p++<n){
            scanf("%s",b);
            //printf("%d\n",p);
            int len=strlen(b);
            memset(a,0,sizeof(a));
            for(int i=0;i<len;i++){
                a[b[i]]++;
            }
            //printf("%d %d\n",a['a'],'a');
            if(p==1){
                for(int i=0;i<200;i++){
                    ans[i]=a[i];
                }
            }
            else{
                for(int i=0;i<200;i++){
                    if(a[i]<ans[i]){
                        ans[i]=a[i];
                    }
                }
            }
        }
        for(int i=0;i<200;i++){

            if(ans[i]>0){

                for(int j=0;j<ans[i];j++){
                    printf("%c",i);
                }
            }
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 128