akhauriyash/Code-Regression huggingface dataset:
/*{{{*/
//#define HOME
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define F first
#define S second

template<class T> void _R(T &_x) { cin >> _x; }
void _R(int &_x) { scanf("%d", &_x); }
void _R(int64_t &_x) { scanf("%" SCNd64, &_x); }
void _R(double &_x) { scanf("%lf", &_x); }
void _R(char &_x) { scanf(" %c", &_x); }
void _R(char *_x) { scanf("%s", _x); }
template<class T, class U> void _R(pair<T, U> &_x) {_R(_x.F); _R(_x.S);}
void R() {}
template<class T, class... U> void R(T &_head, U &... _tail) { _R(_head); R(_tail...); }

template<class T> void _W(const T &_x) { cout << _x; }
void _W(const int &_x) { printf("%d", _x); }
void _W(const int64_t &_x) { printf("%" PRId64, _x); }
void _W(const double &_x) { printf("%.16f", _x); }
void _W(const char &_x) { putchar(_x); }
void _W(const char *_x) { printf("%s", _x); }
template<class T, class U> void _W(const pair<T, U> &_x) {_W(_x.F); putchar(' '); _W(_x.S);}
template<class T> void _W(const vector<T> &_x) { for (auto i = _x.begin(); i != _x.end(); _W(*i++)) if (i != _x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &_head, const U &... _tail) { _W(_head); putchar(sizeof...(_tail) ? ' ' : '\n'); W(_tail...); }
template<class T, class... U> void DB(const T &_head, const U &... _tail) {
#ifdef HOME
    W('#', _head, _tail...);
#endif
}

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define RAN(x,n) (x).begin(), (x).begin()+(n)
#define UNIQUE(x) {sort(ALL(x)); (x).erase(unique(ALL(x)), (x).end());}

#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
//#define ITER(i,t) for (auto i = t.begin(); i != t.end(); ++i)
#define IT3(i,st,ed) for (auto i = st; i != ed; ++i)
#define IT2(i,range) IT3(i,range)

#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define MS(X, v) memset((X), (v), sizeof((X)))

template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

inline int LG (const unsigned int &_x) { return 31-__builtin_clz(_x); }  // floor: LG(x), ceil: LG(x-1)+1
/*}}}*/

int n;
string s;

set<tuple<int, int, int>> ans;

int main(){
    R(n, s);

    vi pre(n), post(n);
    int t = 0;
    FOR(i, n){
        pre[i] = t;
        t |= (1 << (s[i] - '0'));
    }
    t = 0;
    REPD(i, n-1, 0){
        post[i] = t;
        t |= (1 << (s[i] - '0'));
    }

    FOR(i, n){
        FOR(b1, 10) if(pre[i] & (1 << b1))
            FOR(b2, 10) if(post[i] & (1 << b2)) {
                ans.emplace(b1, s[i]-'0', b2);
            }
    }

    W(SZ(ans));

    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    long long max, min, ans = 0;
    for(int i=k; i<=n+1; i++){
        min = ((long long)i*(long long)(i-1))/(long long)2;
        max = ((long long)(2*n-i+1)*(long long)i)/(long long)2;
        ans += max - min;
        ans++;
    }

    ans %=(long long)(1000000007);

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<stack>
#include<list>
#include<unordered_map>
#include<unordered_set>
#include<cctype>
#include<iomanip>

using namespace std;
typedef long long int ll;typedef pair<int, int> P;
const long long mod = 1e9 + 7;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(a) (a).begin(),(a).end()
#define allg(a) (a).begin(),(a).end(),greater<>()
#define SUM(a) accumulate((a).begin(),(a).end(),0)
const double PI = 3.14159265359;

int main(void) {
	vector<int> v(3);
	rep(i, 3)cin >> v[i];
	sort(allg(v));
	int k; cin >> k;
	rep(i, k) {
		v[0] *= 2;
	}
	ll sum = SUM(v);
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
N,M=map(int, input().split())
PY=[list(map(int, input().split()))+[i] for i in range(M)]
PY=list(sorted(PY))
ls=[]
current=0
ct=1
for i in range(M):
    s1=str(PY[i][0])
    s2=''
    for j in range(6-len(s1)):
        s2+='0'
    s3=s2+s1

    if current==PY[i][0]:
        ct+=1
    else:
        ct=1
        current=PY[i][0]

    s4=str(ct)
    s5=''
    for j in range(6-len(s4)):
        s5+='0'
    s6=s5+s4
    s7=s3+s6

    ls.append([s7,PY[i][2]])

ls=sorted(ls, key=lambda x :x[1])
for i in ls:
    print(i[0])


Measured memory_bytes: 43880
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007

using namespace std;

int h, w, n, c, a[101][101];

int main() {
	cin >> h >> w;
	cin >> n;
	int x = 1, y = 1, f = 1;
	for (int i = 1; i <= n; i++) {
		cin >> c;
		while(c--) {
			a[x][y] = i;
			y += f;
			if (y > w) y = w, x++, f = -1;
			else if (!y) y = 1, x++, f = 1;
		}
	}
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
	
	return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <algorithm>	
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
typedef unsigned int uii;
typedef pair<int,int> pii;
typedef unsigned long long uLL; 
typedef vector<int> vi; 



int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	unsigned long long n;
	cin >> n;
	unsigned long long t = 10, res = 0;
	if(n & 1) {
		cout << 0 << endl;
		return 0;
	}
	while(t <= n) {
		res += n / t;
		t *= 5;
	}
	cout << res << endl;
	return 0;
}

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

using namespace std;

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<(b);i++)
#define repr(i,b,a) for(int i=int(b);i>=(a);i--)
#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool valid(int lx,int ux,int ly,int uy,int x,int y){
	return lx<=x&&x<ux&&ly<=y&&y<uy; 
}
ll power(ll x,ll p){
	if(p==0)return 1;
	ll res=power(x*x%mod,p/2);
	if(p%2==1)res=res*x%mod;
	return res;
}

int main()
{
	int n,k;
	cin>>n>>k;
	int cnt=0;
	while(n>0){
		cnt++;
		n/=k;
	}
	cout<<cnt<<endl;
	return 0;
}

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

#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define ldb long double 
#define db double
#define int long long

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >

#define mi map<int,int>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

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

const int md = 1e9+7;
const int MX = 2e5+5;
const int INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

int power_md(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res=(res%md*a%md)%md;
  a=(a%md*a%md)%md;
  n/=2;
}
res%=md;
return res;
}

int power(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res*=a;
  a=a*a;
  n/=2;
}
return res;
}

int abst(int a)
{
 return ((a<0)?(-1*a):(a));
}

class cmp_set{
public:
	bool operator() (int a, int b){
		return a > b;
	}
};

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

int32_t main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int res=min((b/a),c);
    cout<<res<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
string S, T;

int main(){
	cin >> S;
	cin >> T;
	int N = S.size();

	map<char, char> m_st, m_ts;
	for(int i=0; i<N; i++){
		if(m_st.find(S[i])==m_st.end()){
			m_st[S[i]] = T[i];
		} else if(m_st[S[i]]!=T[i]){
			cout << "No" << endl;
			return 0;
		}
		if(m_ts.find(T[i])==m_ts.end()){
			m_ts[T[i]] = S[i];
		} else if(m_ts[T[i]]!=S[i]){
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}


Measured memory_bytes: 776
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

auto fft(vector<complex<double>> f, int n, int sign) {
    if (n == 1) return f;
    vector<complex<double>> f0(n/2), f1(n/2);
    for(int i = 0; i < n/2; i++) {
        f0[i] = f[2*i];
        f1[i] = f[2*i+1];
    }
    f0 = fft(f0, n/2, sign);
    f1 = fft(f1, n/2, sign);
    complex<double> zeta(cos(M_PI*2/n), sin(M_PI*2/n)*sign);
    complex<double> pow_zeta = 1;
    for (int i = 0; i < n; i++) {
        f[i] = f0[i%(n/2)] + pow_zeta*f1[i%(n/2)];
        pow_zeta *= zeta;
    }
    return f;
}

auto inv_fft(vector<complex<double>> f, int n) {
    f = fft(f, n, -1);
    for(auto& ff : f) {
        ff /= n;
    }
    return f;
}

auto multiply(vector<complex<double>> g, vector<complex<double>> h) {
    int n = 1;
    while( n <= g.size() + h.size()) {
        n *= 2;
    }
    g.resize(n);
    h.resize(n);
    auto gg = fft(g, n, 1);
    auto hh = fft(h, n, 1);
    vector<complex<double>> ff(n);
    for (int i = 0; i < n; i++) {
        ff[i] = gg[i] * hh[i];
    }
    return inv_fft(ff, n);
}

int main() {
    ll N, M;
    cin >> N >> M;
    vector<int> A(N+1);
    vector<complex<double>> B(100005, 0), C(100005, 0);
    rep(i, N) {
        cin >> A[i];
        B[A[i]] += 1;
        C[A[i]] += 1;
    }



    auto cnv = multiply(B, C);
    ll cou = M;
    ll s = cnv.size();
    ll ans = 0;

    rep(i, s){
        if (cou == 0) break;
        ll tmp = (cnv[s-i-1].real() + 0.5);
        if (tmp != 0) {
            if (cou - tmp >= 0) {
                ans += (s-i-1)*tmp;
                cou -= tmp;
            } else {
                ans += (s-i-1)*cou;
                cou = 0;
            }


        }
    }

    cout << ans  << endl;

    return 0;
}

Measured memory_bytes: 44732
const A: [u64; 32] = [
    1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1,
    51,
];
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let k: usize = sc.read();
    println!("{}", A[k - 1]);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
fun main(args: Array<String>) {
    readLine()
    val readInts = { readLine()!!.split(" ").map { it.toInt() } }
    val al = readInts()
    val bl = readInts()
    val cl = readInts()
    val sum = bl.sum()
    var bonus = 0
    for (a in al.withIndex()) {
        val b = al.getOrNull(a.index + 1)
        if (b != null && a.value + 1 == b) {
            bonus += cl[a.value - 1]
        }
    }
    print(sum + bonus)
}

Measured memory_bytes: 37988
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
const int inf = 1e9+7;
const int INF = 1e18+7;
const int mod = 1e9+7;

P a[100010];
int dp1[100010], dp2[100010];
signed main(){
	int n, r;
  scanf("%lld%lld", &n, &r);
  rrep(i,n){
    int x, y;
    scanf("%lld%lld", &x, &y);
    a[i] = P(x, y);
  }
  
  a[n+1].fi = r;
  int v = 0;
  rrep(i,n){
    v += a[i].se-(a[i].fi-a[i-1].fi);
    dp1[i] = max(dp1[i-1], v);
  }
  v = 0;
  drep(i,n,1){
    v += a[i].se-(a[i+1].fi-a[i].fi);
    dp2[i] = max(dp2[i+1], v);
  }
  
  int ans = max(dp1[n], dp2[1]);
  rrep(i,n)ans = max(ans, dp2[i]+dp1[i-1]-min((r-a[i].fi), a[i-1].fi));
  /*rrep(i,n)printf("%lld ", dp1[i]);
  printf("\n");
  rrep(i,n)printf("%lld ", dp2[i]);
  printf("\n");*/
  printf("%lld\n", ans);
	return 0;
}




Measured memory_bytes: 3328
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int A = sc.nextInt();
        int B = sc.nextInt();

        if(1 <= A && A <= 9 && 1 <= B && B <= 9){
            System.out.println(A*B);
        } else
            System.out.println(-1);
    }
}

Measured memory_bytes: 21844
N, K = list(map(int, input().split()))
A = list(map(lambda x: int(x) - 1, input().split()))

v = [A[:]]
now = 0
for i in range(60):
    v.append([v[i][v[i][j]] for j in range(N)])
    if K>>i & 1:
        now = v[i][now]
print(now + 1)

Measured memory_bytes: 218992
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))

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


#define rep(i, n) for(int i = 0; i < (n); i++)
using ULL = unsigned long long;

void solve() {
	string s; cin >> s;
	int k; cin >> k;
	size_t l = s.size();
	vector<int> same = { 1 };
	long long ans = 0;
	for (int i = 1; i < l; i++) {
		if (s[i] == s[i - 1]) same.back()++;
		else same.push_back(1);
	}

	if (same.size() == 1) { cout << (long long)same[0] * k / 2 << endl; return; }

	for (int a : same) { ans += a / 2; }
	ans *= k;
	if (s[0] == s[l - 1]) {
		if (same.back() % 2 == 1 && same.front() % 2 == 1) {
			ans += k - 1;
		}
	}

	cout << ans << endl;
}

int main() {

	solve();

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int n;
char s[1010];
vector<PII> ans,c,trash;
vector<PII> build(VI w) {
	if (SZ(w)==1) return vector<PII>{{w[0],0}};
	vector<PII> z{{w[0],0},{w[1],0},{w[0],1},{w[1],1}};
	rep(i,2,SZ(w)) {
		vector<PII> nz=z; 
		z.pb({w[i],0});
		reverse(all(nz));
		for (auto p:nz) z.pb({p.fi,p.se^1});
		z.pb({w[i],1});
	}
	return z;
}
int zz;
int main() {
	scanf("%d",&n);
	scanf("%s",s);
	//rep(i,0,(1<<n)) s[i]=(__builtin_popcount(i)<5)+'0';
	rep(i,0,(1<<n)) rep(j,0,(1<<n)) if ((j&i)==i&&s[i]=='0'&&s[j]=='1') {
		puts("Impossible");
		return 0;
	}
	rep(i,0,(1<<n)) if (s[i]=='0') {
		bool cc=0;
		rep(j,0,(1<<n)) if ((i&j)==j&&i!=j&&s[j]=='0') cc=1;
		if (cc) continue;
		VI w;
		fprintf(stderr,"%d\n",i);
		rep(j,0,n) if (i&(1<<j)) w.pb(j);
		auto x=build(w);
		for (auto p:x) ans.pb(p);
		rep(i,0,100) {
			int x=rnd(n);
			ans.pb(mp(x,0)),trash.pb(mp(x,0));
		}
	}
	//fprintf(stderr,"%d\n",zz);
	reverse(all(trash));
	for (auto p:trash) ans.pb(mp(p.fi,p.se^1));
	puts("Possible");
	int pos=0;
	c.pb(mp(0,0));
	for (auto p:ans) {
		//printf("pp %d %d\n",p.fi,p.se);
		if (p.se==0) {
			while (pos<p.fi) {
				pos+=1;
				c.pb(mp(pos,0));
			}
			while (pos>p.fi) {
				pos-=1;
				c.pb(mp(pos,0));
			}
			c.pb(mp(pos,1));
			c.pb(mp(pos+1,1));
			c.pb(mp(pos+1,0));
			pos+=1;
		} else {
			while (pos<p.fi+1) {
				pos+=1;
				c.pb(mp(pos,0));
			}
			while (pos>p.fi+1) {
				pos-=1;
				c.pb(mp(pos,0));
			}
			c.pb(mp(pos,1));
			c.pb(mp(pos-1,1));
			c.pb(mp(pos-1,0));
			pos-=1;
		}
	}
	while (pos>0) {
		pos--;
		c.pb(mp(pos,0));
	}
	assert(SZ(c)<=250000);
	printf("%d\n",SZ(c)-1);
	for (auto x:c) printf("%d %d\n",x.fi,x.se);
}

Measured memory_bytes: 1724
import qualified Data.ByteString.Char8 as B
import Data.Array
import Data.Array.IO
import Control.Monad

type Grid = IOUArray (Int, Int) Char
type DP = IOUArray (Int, Int) Int


main = do
  [h,w] <- map read . words <$> getLine :: IO [Int]
  xss <- replicateM h B.getLine
  grid <- thaw $ listArray ((1,1),(h,w)) $ B.unpack $ B.concat xss :: IO Grid
  dp <- newArray ((1,1),(h,w)) 0 :: IO DP
  writeArray dp (1,1) 1 
  let m = 10^9 + 7
  forM_ [1..h] $ \i -> 
    forM_ [1..w] $ \j -> do
      d <- readArray dp (i,j)
      g <- readArray grid (i,j)
      forM_ [(i+1,j),(i,j+1)] $ \n@(i',j') -> do
        unless (i' > h || j' > w) $ do
          d' <- readArray dp n
          g' <- readArray grid n
          unless (g' == '#') $ do
            writeArray dp n $ ((d+d') `mod` m)
  
  readArray dp (h,w) >>= print


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

int main(){
  int N;
  cin >> N;
  vector<int> L(N);
  for(int i=0;i<N;i++){
    cin >> L.at(i);
  }
  
  sort(L.begin(),L.end());
  
  int S=0;
  for(int i=0;i<N-1;i++){
    S = S + L.at(i);
  }
  if(S > L.at(N-1)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
signed main()
{
	int A, B, K;
	cin >> A >> B >> K;
	vector<int>a, b;
	int cnt = 0;
	for (int i = max(A,B); i >= 1; i--)
	{
		if (A % i == 0 && B % i == 0)cnt++;
		if (cnt == K)
		{
			cout << i;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;

const ll maxn=2e5+500;
const ll mod=1e9+7;
const ll inf=1e9+500;


long long dp[41][1<<18];
ll n,X,Y,Z,S,CV;

ll add(ll c,ll k){
    if(c&CV){
        return c;
    }
    ll ans=0;
    for(char i=0;i<X;i++){
        if(i+1==k){
            ans|=(1<<i);
        }
        if(i+1>k && ((c>>(i-k))&1)){
            ans|=(1<<i);
        }
    }
    c=((c>>(X-1))<<(X-1));
    for(char i=X;i<X+Y;i++){
        if(i+1>k && ((c>>(i-k))&1)){
            ans|=(1<<i);
        }
    }
    c=((c>>(X+Y-1))<<(X+Y-1));
    for(char i=X+Y;i<S;i++){
        if(i+1>k && ((c>>(i-k))&1)){
            ans|=(1<<i);
        }
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


    cin>>n>>X>>Y>>Z;
    S=X+Y+Z;
    CV=(1<<(S-1));

    dp[0][0]=1;
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<(1<<S);j++){
            for(ll k=1;k<=10;k++){
                dp[i][add(j,k)]+=dp[i-1][j];
            }
        }
        for(ll j=0;j<(1<<S);j++){
            dp[i][j]%=mod;
        }
    }
    long long ans=0;
    for(ll j=(1<<(S-1));j<(1<<S);j++){
        ans+=dp[n][j];
        ans%=mod;
    }
    cout<<ans;
}


Measured memory_bytes: 82176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 1e2 + 10;

int n, m;
int w[maxN], v[maxN];
ll dp[maxN][100005];

int main(){
//  freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> w[i] >> v[i];
  }
  int total;
  total = accumulate(v + 1, v + n + 1, 0);
  ll inf = 1LL << 62;
  for (int i = 0; i < maxN; ++i)
    for (int j = 0; j < 100005; ++j)
      dp[i][j] = inf;
  dp[1][v[1]] = w[1]; dp[1][0] = 0;
  for (int i = 2; i <= n; ++i) {
    for (int pri = 0; pri <= total; ++pri) {
      dp[i][pri] = dp[i-1][pri];
      if (pri >= v[i]) dp[i][pri] = min(dp[i][pri], dp[i-1][pri-v[i]] + w[i]);
    }
  }
  for (int pri = total; pri >= 0; --pri) {
    if (dp[n][pri] <= m) return cout << pri, 0;
  }
return 0;
}


Measured memory_bytes: 89496
//c++ テンプレ
#include<bits/stdc++.h>
using namespace std;

typedef long long llint;
typedef long double ld;

#define inf 1e18
#define mod 1000000007
priority_queue<llint,vector<llint>,greater<llint> > que;
priority_queue<llint> Que;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve(){
    int n;
    cin >> n;
    if(n%10==3)cout << "bon" << endl;
    else if(n%10==0 || n%10==1 || n%10==6 || n%10==8)cout << "pon" << endl;
    else cout << "hon" << endl;
}

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


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

int main(){
	string ori, t; cin>>ori>>t;
	string s = ori;
	for(int tt = 0; tt < 100; tt++){
		char last = s[int(s.size()) - 1];
		s = s.substr(0, s.size() - 1);
		s = last + s;
		//cout<<s<<endl;
		if(s == t){
			cout<<"Yes\n";
			return 0;
		}
	}
	puts("No");
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;
const ll INF = 1e9;
 
#define rep(i, n) for(ll i = 0; i < n ; i++ )
#define For(i, a, b) for(ll i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define tolower(c) char(c+0x20)
#define toupper(c) char(c-0x20)

const ll MAX_N = 100000;
 
int main(void){
    ll a,b,c,d;
    string s,t,u;
 
    cin >> a >> b>> c;// >> d;
    //cin >> s >> t >> u;
    if (b-a==c-b) cout << "YES";
    else cout << "NO";

    return 0;
}

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

const int MAX = 50;
const long long INF = 1e9;

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

        long long stu_x[MAX];
        long long stu_y[MAX];
        for (int i=0; i<n; ++i) {
                cin >> stu_x[i] >> stu_y[i];
        }

        long long chk_x[MAX];
        long long chk_y[MAX];
        for (int i=0; i<m; ++i) {
                cin >> chk_x[i] >> chk_y[i];
        }

        for (int i=0; i<n; ++i) {
                long long dis = INF;
                int index = -1;
                for (int j=0; j<m; ++j) {
                        long long tmp = abs(stu_x[i]-chk_x[j])+abs(stu_y[i]-chk_y[j]);
                        if (dis>tmp) {
                                dis = tmp;
                                index = j+1;
                        }
                }
                cout << index << endl;
        }
        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  
  int count = 0;
  for(int i = 0; i < 3; i++){
  	if(S.at(i) == 'o'){
    	count++;
    }
  }
  
  cout << 700 + count*100 << endl;
}


Measured memory_bytes: 256
n, x = gets.chomp.split(" ").map(&:to_i)

$layer = {}
def burger_layer(level)
  return $layer[level] if $layer[level]
  return $layer[level] = 1 if level.zero?
  $layer[level] = 2 * burger_layer(level - 1) + 3
end

$p_count = {}
def p_count(level)
  return $p_count[level] if $p_count[level]
  return $p_count[level] = 1 if level.zero?
  $p_count[level] = 2 * p_count(level - 1) + 1
end

def ans(n, x)
  if x <= 1
    return n.zero? ? 1 : 0
  elsif x == burger_layer(n)
    return p_count(n)
  elsif x == burger_layer(n - 1)
    return p_count(n - 1)
  elsif x <= 1 + burger_layer(n - 1)
    return ans(n-1, x-1)
  elsif x == 2 + burger_layer(n - 1)
    return p_count(n - 1) + 1
  elsif x > 2 + burger_layer(n - 1)
    return ans(n-1, burger_layer(n-1)) + 1 + ans(n-1, x-burger_layer(n-1)-2)
  end
end

puts ans(n, x)

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

signed main(void){
  int s; cin >> s;
  int ans = 0;
  
  ans += (s/500)*1000;
  s %= 500;
  
  ans += (s/5)*5;
  
  cout << ans << endl;
  
  return 0;
} 

Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n - 1];
		int answer = 0;

		Map<Integer, Integer> m = new HashMap<>();
		a[0] = sc.nextInt();

		for (int i = 1; i < n; i++) {
			a[i] = sc.nextInt();
			m.put(a[i - 1], a[i]);
		}
		for (int i = 0; i < n; i++) {
			b[i] = sc.nextInt();
			answer += b[i];
		}

		for (int i = 0; i < n - 1; i++) {
			c[i] = sc.nextInt();
			if (!m.containsKey(i + 1)) continue;
			if (m.get(i + 1) == i + 2) {
				answer += c[i];
			}
		}

		System.out.println(answer);
	}
}


Measured memory_bytes: 21716
//競技プログラミング　テンプレ
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

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

const int max_v = 300;
const int INF = 1000000;



int main() {
	int a,b,n=0;
  int ans;
	cin >> a >> b;
	//vector <int> A(n);
	//string str;
  if(a%2==1 && b %2 ==0 || a%2==0 && b %2 ==1) n=1;
  ans = (a+b)/2;
  ans +=n;
  

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

	cout << ans << endl;
	return 0;
}


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

static const int MAX_R = 13;
static const int MAX_N = 52;

int main()
{

	int  N, num;
	char card;
	bool S[MAX_R], H[MAX_R], C[MAX_R], D[MAX_R];

	for( int i = 0; i < MAX_R; i++ ) {

		S[i] = false;
		H[i] = false;
		C[i] = false;
		D[i] = false;

	}

	cin >> N;
	for( int i = 0; i < N; i++ ) {

		cin >> card >> num;
		if( card == 'S' ) S[num - 1] = true;
		else if( card == 'H' ) H[num - 1] = true;
		else if( card == 'C' ) C[num - 1] = true;
		else D[num - 1] = true;

	}

	for( int i = 0; i < 4; i++ ) {
		for( int j = 0; j < MAX_R; j++ ) {

			if( i == 0 ) {
				if( !S[j] ) cout << "S " << j + 1 << endl;
			}
			else if( i == 1 ) {
				if( !H[j] ) cout << "H " << j + 1 << endl;
			}
			else if( i == 2 ) {
				if( !C[j] ) cout << "C " << j + 1 << endl;
			}
			else if( i == 3 ) {
				if( !D[j] ) cout << "D " << j + 1 << endl;
			}

		}
	}

	return 0;

}

Measured memory_bytes: 1164
/*
P135
AOJ 0525 Osenbei
*/

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <functional>
#include <string.h>
using namespace std;



int R, C;
int num[10][10000];
int isFlipped[10];
int count0[10000];

bool read()
{
    scanf("%d%d", &R, &C);
    if(R==0 && C==0) return false;
    memset(count0, 0, sizeof(count0));
    memset(isFlipped, 0, sizeof(isFlipped));
    for(int i=0; i<R; ++i)
    for(int j=0; j<C; ++j){
        scanf("%d", &num[i][j]);
        if(!num[i][j])count0[j]++;
    }
    return true;
}


void FlipRow(int r)
{
    isFlipped[r] ^= 1;
    for(int j=0; j<C; ++j){
        num[r][j]^=1;
        if(!num[r][j]) count0[j]++;
        else count0[j]--;
    }
}

void FlipRows(int i)
{
    for(int r=0; r<R; ++r)
    {
        if(  ((i>>r)&1) ^ (isFlipped[r])  ) FlipRow(r);
    }
}

int countNum()
{
    int ans = 0;
    for(int j=0; j<C; ++j){
        ans += max(count0[j], R-count0[j]);
    }
    return ans;
}

void solve()
{
    int ans = 0;
    for(int i=0; i<(1<<R); i++)
    {
        FlipRows(i);
        ans = max(ans, countNum());
    }
    printf("%d\n", ans);
}

int main()
{
    while(read())
        solve();
}

Measured memory_bytes: 1624
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> x(N);
  vector<ll> y(N);
  vector<ll> z(N);

  rep(i, N) cin >> x[i] >> y[i] >> z[i];

  ll ans = 0;
  vector<ll> total(N);
  for (int a = -1; a <= 1; a += 2) {
    for (int b = -1; b <= 1; b += 2) {
      for (int c = -1; c <= 1; c += 2) {
        rep(i, N) { total[i] = a * x[i] + b * y[i] + c * z[i]; }
        sort(total.begin(), total.end(), greater<ll>());
        ll tmp = 0;
        rep(i, M) tmp += total[i];
        ans = max(ans, tmp);
      }
    }
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;

#define REP(i,n) for(long long (i)=0;(i)<(long long)(n);(i)++)
#define RREP(i,n) for(long long (i)=(long long)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

template <class T> struct FenwickTree2D {

    vector < vector < T > > node;
    FenwickTree2D (int h, int w) : node(h, vector < T > (w, 0)) {}

    void add(int x, int y, T val) {
        for (int i = x; i < node.size(); i |= i + 1) {
            for (int j = y; j < node[i].size(); j |= j + 1) {
                node[i][j] += val;
            }
        }
    }

    void update(int x, int y, T val) {
        add(x, y, -sum(x, y, x + 1, y + 1));
        add(x, y, val);
    }

    T sum(int x, int y) {
        T ret = 0;
        for (int i = x - 1; i >= 0; i = (i & (i + 1)) - 1) {
            for (int j = y - 1; j >= 0; j = (j & (j + 1)) - 1) {
                ret += node[i][j];
            }
        }
        return ret;
    }

    T sum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x2, y1) - sum(x1, y2) + sum(x1, y1);
    }

};

int main() {

    int H,W,T,Q;
    cin >> H >> W >> T >> Q;

    queue < vector < int > > que;
    FenwickTree2D < int > inst1(2010, 2010);
    FenwickTree2D < int > inst2(2010, 2010);

    REP(kai, Q) {
        int t,c,h,w;
        scanf("%d%d%d%d", &t, &c, &h, &w);
        while (!que.empty()) {
            vector < int > v = que.front();
            if (v[0] <= t) {
                inst1.update(v[1], v[2], 0);
                inst2.update(v[1], v[2], 1);
                que.pop();
            } else {
                break;
            }
        }
        if (c == 0) {
            que.push({t + T, h, w});
            inst1.update(h, w, 1);
        } else if (c == 1) {
            inst2.update(h, w, 0);
        } else {
            int h2, w2;
            scanf("%d%d", &h2, &w2);
            h2++, w2++;
            cout << inst2.sum(h, w, h2, w2) << " " << inst1.sum(h, w, h2, w2) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 40136
h,w=map(int,input().split())
S=[]
for i in range(h):
    s=input()
    S.append(s)
for i in range(1,h-1):
    for j in range(1,w-1):
        if S[i+1][j]==S[i][j+1]==S[i-1][j]==S[i][j-1]=="." and S[i][j]=="#":
            print("No")
            quit()
print("Yes")

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <sstream>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;

const int N_MAX = 200005;
int N, K;
int A[N_MAX];
map<int, int> m;

struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};

int main() {
    int a;
    int k = 0;
    cin >> N;
    cin >> K;
    for (int i = 0; i < N; ++i) {
        cin >> a;
        A[i] = a;
        if(m.find(A[i]) == m.end()) {
            m[A[i]] = 1;
            k++;
        } else {
            m[A[i]] += 1;
        }
    }

    vector<pair<int, int> > v;
    for(pair<int, int> p:m) {
        v.push_back(p);
    }

    sort(v.begin(), v.end(), sort_pred());

    int count = 0;
    for(pair<int, int> p:v) {
        if (k <= K) break;

        count += p.second;
        k--;
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 12536
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cstdio>
using namespace std;
int main(){
    int N, D, X;
    int total = 0;
    int tmp = 0;
    cin >> N >> D >> X;
    int A[100];
    for(int i = 0; i < N; i++)
        cin >> A[i];
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= D; j++){
            tmp = A[i] * j + 1;
            if(tmp <= D)
                total++;
        }
    }
    cout << total + X << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]"):

    dp = [[0]*N for _ in range(N)]
    for sub in range(N):
        turn = sub % 2
        for i in range(N-sub):
            j = i+sub
            # i ~ jの数列に対して操作
            if i == j:
                if (N-sub+1) % 2 == 0:
                    dp[i][i] = a[i]
                else:
                    dp[i][i] = -a[i]
                continue

            if (N-sub+1) % 2 == 0:    # 先手番
                dp[i][j] = max(a[i] + dp[i+1][j], a[j]+dp[i][j-1])
            else:               # 後手番
                dp[i][j] = min(-a[i] + dp[i+1][j], -a[j]+dp[i][j-1])
    print(dp[0][N-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 115548
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve() {
	int n, l; cin >> n >> l;
    vector<int> a(n);
    rep(i, n) {
        cin >> a[i];
    }
    int id = -1;
    rep(i, n - 1) {
        if(a[i] + a[i + 1] >= l) {
            id = i;
            break;
        }
    }
    if(id == -1) {
        cout << "Impossible" << endl;
        return;
    }
    cout << "Possible" << endl;
    rep(i, id) {
        cout << i + 1 << endl;
    }
    per(i, n - 1) {
        cout << i + 1 << endl;
        if(i == id) break;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/
 
 
 
 
 
 
int N, M, K;
int P[101010], C[101010], J[101010];
vector<pair<int, int>> E[101010];
//---------------------------------------------------------------------------------------------------
ll D[101010];
void dijk1() {
	rep(i, 0, N) D[i] = infl;
	
	vector<bool> vis(N);

	min_priority_queue<pair<ll, int>> que;

	D[0] = 0;
	que.push({ 0, 0 });

	while (!que.empty()) {
		auto q = que.top(); que.pop();

		ll cst = q.first;
		int cu = q.second;

		if (vis[cu]) continue;
		vis[cu] = 1;

		fore(p, E[cu]) {
			ll cst2 = cst + p.second;
			int to = p.first;

			if (chmin(D[to], cst2)) que.push({ D[to], to });
		}
	}
}
//---------------------------------------------------------------------------------------------------
ll ans[101010];
void dijk2() {
	rep(i, 0, N) ans[i] = -infl;

	vector<bool> vis(N);
	priority_queue<pair<ll, int>> que;

	rep(i, 0, N) que.push({ P[i] - D[i], i });

	while (!que.empty()) {
		auto q = que.top(); que.pop();

		ll cst = q.first;
		int cu = q.second;

		if (vis[cu]) continue;
		vis[cu] = true;

		chmax(ans[C[cu]], cst + J[cu] - D[cu]);

		fore(p, E[cu]) {
			int to = p.first;
			if (vis[to]) continue;
			que.push({ cst - p.second, to });
		}
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> K;
	rep(i, 0, N) cin >> P[i];
	rep(i, 0, N) cin >> C[i]; rep(i, 0, N) C[i]--;
	rep(i, 0, N) cin >> J[i];
	rep(i, 0, M) {
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
		E[a].push_back({ b, c });
		E[b].push_back({ a, c });
	}

	dijk1();
	dijk2();

	rep(i, 0, K) printf("%lld\n", ans[i]);
}
 


Measured memory_bytes: 18204
/*
.....   .   .   .   .
  .    . .   . .   . .
  .   .....   .   .....
  .  .     .  .  .     .
*/
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <cassert>
#include <iomanip>
#include <random>
#include <sstream>
 
using namespace std;

#define int long long
#define double long double
#define time time228
#define left left228
#define right right228

template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}

template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int maxn = 200 * 1000 + 228, MOD = 1e9 + 7;

int n;
int a[maxn], dp[maxn];
vector<int> g[maxn], rr[maxn];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int mx = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        uax(mx, a[i]);
        g[a[i]].push_back(i);
    }
    for (int c = 1; c <= mx; ++c) {
        for (int i = 0; i < (int)g[c].size() - 1; ++i) {
            if (g[c][i] + 1 < g[c][i + 1]) {
                int l = g[c][i], r = g[c][i + 1];
                rr[r].push_back(l);
            }
        }
    }
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        for (int l : rr[i]) {
            dp[i] += dp[l];
            dp[i] %= MOD;
        }
    }
    cout << dp[n] << '\n';
    return 0;
}


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

using namespace std;

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

    int n, w;
    cin >> n >> w;
    vector<pair<int, int>> items(n);

    int weight, val;
    for (int i = 0; i < n; ++i) {
        cin >> weight >> val;
        items[i] = {weight, val};
    }

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

    for (int i = 0; i <= w; ++i) {
        i < items[0].first ? dp[0][i] = 0 : dp[0][i] = items[0].second;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= w; ++j) {
            if (items[i].first <= j) {
                dp[i][j] = max(dp[i - 1][j], items[i].second + dp[i - 1][j - items[i].first]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    cout << dp[n][w] << '\n';

    return 0;
}


Measured memory_bytes: 79104
#18:20
n = int(input())
mod = 10 ** 9 + 7
now = [[[[0 for _ in range(4)]
            for _ in range(4)]
            for _ in range(4)]
            for _ in range(4)]
now[3][3][3][3] = 1
for _ in range(n):
  last = now
  now = [[[[0 for _ in range(4)]
              for _ in range(4)]
              for _ in range(4)]
              for _ in range(4)]
  for i in range(4):
    for j in range(4):
      for k in range(4):
        for l in range(4):
          for m in range(4):
            now[j][k][l][m] += last[i][j][k][l]
            now[j][k][l][m] %= mod
  for j in range(4):
    now[j][0][1][2] = 0
    now[j][1][0][2] = 0
    now[j][0][2][1] = 0
  for k in range(4):
    now[0][k][1][2] = 0
  for l in range(4):
    now[0][1][l][2] = 0
ans = 0
for i in range(4):
  for j in range(4):
    for k in range(4):
      for l in range(4):
        ans += now[i][j][k][l]
print(ans % mod)

Measured memory_bytes: 3188
import copy
H, W, K = map(int, input().split())
li = []
black = 0
result = 0

for i in range(H):
    li.append(list(input()))
    black += li[i].count("#")

for j in range(2 ** H):
    sum_h = 0
    li_a = copy.copy(li)
    for k in range(H):
        if j & (1 << k):
            sum_h += li[k].count("#")
            li_a[k] = ["r"]*len(li_a[k])
    for l in range(2 ** W):
        sum_w = 0
        for m in range(W):
            if (1 << m) & l:
                for n in range(H):
                    if li_a[n][m] == "#": 
                        sum_w += 1
        if sum_h + sum_w == black - K:
            result += 1

print(result)

Measured memory_bytes: 9260
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#ifndef null
#define null -1
#endif
using namespace std;

const int MAXN = 2e5 + 10;
const int INF = 1e5 + 10;
const int MOD = 1e9 + 7;
typedef long long ll;

char s[INF];
int num[27] = { 0 };
string s1="0";
ll solve(int L, int R)
{
	if (L == R)
		return num[s1[L] - 'a'];
	int mid = (L + R) >> 1;
	ll nL = solve(L, mid), nR = solve(mid + 1, R);
	return (nL%MOD + nR%MOD + (nL%MOD * nR%MOD)%MOD)%MOD;
}
int main()
{
	int n;
	cin >> n;
	cin >> s;
	for (int i = 0; i < n; i++) {
		if (!num[s[i] - 'a'])
			s1 = s1 + s[i];
		num[s[i] - 'a']++;
	}

	cout << solve(1, s1.length() - 1)<<endl;

	return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string n;
  cin>>n;
  bool ok=false;
  for(int i=0; i<3; i++){
    if(n[i]=='7'){
      ok=true;
    }
  }
  if(ok){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

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

#define int long long

using namespace std;

#ifdef LOCAL 
#include "/media/brayand/BrayanD/debugger.h"
#else
#define db(...) false
#define dbl(...) false
#define dbg(...) false
#endif

const int MAXN = 2e5 + 100;

int dp[MAXN*2];

const int MOD = 998244353;

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

    int N, K;
    cin >> N >> K;

    vector<pair<int,int>> vect;

    vector<int> sum;

    for(int i = 1 ; i <= K ; i++)
    {
    	int a, b;
    	cin >> a >> b;
    	vect.push_back({MAXN-b, MAXN-a});
    	sum.push_back(0);
    }

    dp[MAXN] = 1;

    for(int i = MAXN+1 ; i <= MAXN+N-1 ; i++)
    {
    	for(int x = 0 ; x < K ; x++)
    	{
    		sum[x] = (sum[x] + dp[vect[x].second+1]) % MOD;
    		sum[x] = (sum[x] + MOD - dp[vect[x].first]) % MOD;
    		vect[x].first++;
    		vect[x].second++;

    		dp[i] = (dp[i] + sum[x]) % MOD;
    	}
    }

    cout << dp[MAXN+N-1] << '\n';

    return 0;
}

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

int main()
{
    int a,b;
    cin>>a>>b;
    if(a==1 || b==1)
    {
        if(a==1 && b!=1)
            cout<<"Alice"<<endl;
        else if(a!=1 && b==1)
            cout<<"Bob"<<endl;
        else if(a==1 && b==1)
            cout<<"Draw"<<endl;
    }
    else
    {
        if(a>b)
            cout<<"Alice"<<endl;
        else if(a==b)
            cout<<"Draw"<<endl;
        else
            cout<<"Bob"<<endl;

    }

}


Measured memory_bytes: 256