akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int i, j, k, x, tmp;
	cin >> x;
	set<int> s;
	s.insert(1);
	for (i=2; i<=32; i++)
	{
		tmp=i;
		j=1;
		while(tmp<=1000)
		{
			tmp=i;
			for (k=j; k>=1; k--)
			{
				tmp*=i;
				
			}//cout << "j = " << j << endl;
			s.insert(tmp);
			j++;
			
		}
		//cout << "i=" << i << endl;
	}
	tmp=*s.begin();
	while (1)
	{
		if (*s.begin()>x)
		{
			cout << tmp << endl;
			return 0;
		}
		else if (*s.begin()==x)
		{
			cout << *s.begin() << endl;
			return 0;
		}
		else
		{
			tmp=*s.begin();
			s.erase(*s.begin()); 
		}
	}
	return 0;
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define minch(x,y) x=min(x,y)
#define dbg(x) cerr<<#x<<"="<<x<<endl

#define INF 5e18

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n,-1){}
  int find(int x){ return v[x] < 0 ? x : v[x]=find(v[x]); }
  bool unite(int x,int y){
    x=find(x); y=find(y);
    if(x==y)return false;
    if(-v[x] < -v[y])swap(x,y);
    v[x]+=v[y]; v[y]=x;
    return true;
  }
};

int N,M;
vector<int> g[100010];
vector<P> t[100010];
ll vw[100010];
map<P,ll> w;
ll ord[100010],low[100010];
ll cnt;
vector<P> es;
map<P,bool> isbridge;
ll res=INF,tot=0;
P resv;
map<P,P> redge;

void dfs(int v,int prev){
  ord[v]=low[v]=++cnt;
  for(int nv : g[v]){
    if(ord[nv]==-1){
      dfs(nv,v);
      low[v]=min(low[v],low[nv]);
      if(ord[v]<low[nv]){
        isbridge[P(min(v,nv),max(v,nv))]=true;
      }
    }else if(nv!=prev){
      low[v]=min(low[v],ord[nv]);
    }
  }
}

ll dfs2(int v,int pre){
  ll sum=vw[v];
  for(P e : t[v]){
    if(e.fi==pre)continue;
    sum+=dfs2(e.fi,v)+e.se;
  }
  for(P e : t[v]){
    if(e.fi==pre){
      tot-=e.se;
      if(res>=llabs(tot-sum-sum)){
        if(res==llabs(tot-sum-sum))minch(resv,redge[P(v,e.fi)]);
        else resv=redge[P(v,e.fi)];
        res=llabs(tot-sum-sum);
      }
      tot+=e.se;
      break;
    }
  }
  return sum;
}

int main(){
  cin>>N>>M;
  rep(i,M){
    ll a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    g[a].push_back(b);
    g[b].push_back(a);
    w[P(a,b)]=c;
    tot+=c;
    es.push_back(P(a,b));
  }
  rep(i,M){
    if(res>=tot-w[es[i]]){
      if(res==tot-w[es[i]])minch(resv,es[i]);
      else resv=es[i];
      res=tot-w[es[i]];
    }
  }
  memset(ord,-1,sizeof(ord));
  cnt=0;
  dfs(0,-1);

  UnionFind uf(N);
  rep(i,M){
    if(isbridge[es[i]])continue;
    uf.unite(es[i].fi,es[i].se);
  }
  rep(i,M){
    int u=uf.find(es[i].fi);
    int v=uf.find(es[i].se);
    if(u!=v){
      t[u].push_back(P(v,w[es[i]]));
      t[v].push_back(P(u,w[es[i]]));
      redge[P(u,v)]=redge[P(v,u)]=es[i];
    }else{
      vw[u]+=w[es[i]];
    }
  }

  dfs2(uf.find(0),-1);
  cout<<resv.fi+1<<" "<<resv.se+1<<endl;

  return 0;
}



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

#define ll long long int
ll mod=1e9+7;

int main()
{
    /* Faster input ouput */
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    /* To read input from a file and output to a file */
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    
    ll t = 1;
    // cin >> t;
    while(t--)
    {        
        ll n,i,j,x,t;
        cin >> n >> x >> t;
        // ll arr[n];

        ll times = ceil((double)n / (double)x);

        cout << t*times << '\n';

        // for(i=0;i<n;i++)
        // {
        //     cin >> arr[i];
        // }
    }
    
    return 0;
}

Measured memory_bytes: 3764
M = 1000000007

def main():
    n = int(input())
    print(solve(n))

def solve(n):
    d = dict()
    for i in range(2, n + 1):
        for f, c in factors(i):
            d[f] = d.get(f, 0) + c
    
    r = 1
    for c in d.values():
        r = (r * (c + 1)) % M
    
    return r

def factors(n):
    i = 2
    
    while i * i <= n:
        c = 0
        while n % i == 0:
            c += 1
            n //= i
        if c != 0:
            yield (i, c)
        
        i += 1
    
    if n != 1:
        yield (n, 1)

main()


Measured memory_bytes: 3064
#include <stdio.h>

int main(void){
	int s;
	scanf("%d",&s);
	
	int hour,min,sec;
	hour=s/(60*60);
	min=(s%(60*60))/60;
	sec=(s%(60*60))%60;
	
	printf("%d:%d:%d\n",hour,min,sec);
	return 0;
	
	
	
	}

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

template<typename T>
istream &operator>>(istream &is, vector<T> &v) {
	for (auto &x : v) is >> x;
	return is;
}

int n, m;
vector<int> c(2), f(2);
vector<vector<char>> a;

int bfs() {
	deque<pair<int, pair<int, int>>> d;
	vector<vector<int>> vis(n, vector<int>(m));
	d.push_front({c[0], {c[1], 0}});
	while (d.size()) {
		int x = d.front().first;
		int y = d.front().second.first;
		int z = d.front().second.second;
		d.pop_front();
		//cerr << "x: " << x << " y: " << y << '\n';
		if (x < 0 || y < 0 || x >= n || y >= m || vis[x][y] || a[x][y] == '#') continue;
		if (x == f[0] && y == f[1]) {
			return z;
		}
		//cerr << "x: " << x << " y: " << y << '\n';
		vis[x][y] = 1;
		d.push_front({x - 1, {y, z}});
		d.push_front({x + 1, {y, z}});
		d.push_front({x, {y - 1, z}});
		d.push_front({x, {y + 1, z}});
		for (int i = x - 2; i <= x + 2; i++) {
			for (int j = y - 2; j <= y + 2; j++) {
				d.push_back({i, {j, z + 1}});
			}
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n >> m >> c >> f;
	c[0]--, c[1]--, f[0]--, f[1]--;
	a = vector<vector<char>>(n, vector<char>(m)); cin >> a;
	cout << bfs() << '\n';
	return 0;
}


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

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 

#define MOD 1000000007

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

    cout << N+N*N+N*N*N << endl;

    return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
    using namespace std;
    #define ll long long
    #define ld long double
    #define vll vector<ll>
    #define mll map<ll,ll>
    #define pll pair<ll,ll>
    #define ff first
    #define ss second
    #define pb push_back
    #define deb(x) cout<<#x<<" : "<<x<<endl;
    #define deb2(x,y) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<endl;
    #define deb3(x,y,z) cout<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
    #define deb4(w,x,y,z) cout<<#w<<" : "<<w<<"\t"<<#x<<" : "<<x<<"\t"<<#y<<" : "<<y<<"\t"<<#z<<" : "<<z<<endl;
    #define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define printv(a)  for(ll i=0;i<a.size();i++)  cout<<a[i]<<" ";
   
   
    const int mod=998244353.;
    const int N=1e6+5; 
   
    bool sortbysec(const pair<pair<ll,ll>,ll> &a, 
                      const pair<pair<ll,ll>,ll> &b) 
        { 
            return (a.second > b.second); 
        } 
        ll powermod(ll x, ll y, ll p)
        {
            ll res = 1;
            x = x % p;
            while (y > 0)
            {
                if (y & 1) res = (res*x) % p;
                y = y>>1;
                x = (x*x) % p;
            }
            return res;
        }
       
        bool isprime(int n) 
        { 
            if (n <= 1)  return false; 
            if (n <= 3)  return true; 
            if (n%2 == 0 || n%3 == 0) return false; 
            for (int i=5; i*i<=n; i=i+6) 
                if (n%i == 0 || n%(i+2) == 0) 
                   return false; 
           return true; 
        }
        
      vector<ll> adj[N];
      vll dist(N,0);
      vll vis(N,0);
      vll in_deg(N,0);
      void dfs(ll x)
      {
          if(vis[x])
          return;
          vis[x]=1;
          for(ll i=0;i<adj[x].size();i++)
          {
              dist[adj[x][i]]=max(dist[adj[x][i]],dist[x]+1);
              in_deg[adj[x][i]]--;
              if(in_deg[adj[x][i]]==0)
              dfs(adj[x][i]);
              
              
          }
      }
        int main()
    {
        FAST;
    ll n,m;
    cin>>n>>m;
    dist.resize(n+1);
    vis.resize(n+1);
    in_deg.resize(n+1);
    for(ll i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
        in_deg[y]++;
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        if(!vis[i] && in_deg[i]==0)
        dfs(i);
        
    }
    for(ll i=1;i<=n;i++)
    ans=max(ans,dist[i]);
    
    cout<<ans<<"\n";
    
   
    
        return 0;
    }

Measured memory_bytes: 54912
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
X = I()
shop = [100,101,102,103,104,105]
dp = [False] * (X+1) #全部の値段を探索する10**5なので
dp[0] = True
for i in range(X+1):
    for s in shop:
        if i - s >= 0:
            dp[i] = dp[i - s] | dp[i]
print('1' if dp[X] else '0')


Measured memory_bytes: 5728
# import sympy

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
count = 0
for i in range(1, n+1):
    if i % 2 == 1:
        # if len(sympy.divisors(i)) == 8:
        if len(make_divisors(i)) == 8:
            count += 1
print(count)



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

using namespace std;

int main ()
{
    int n, a, sum = 0, rem;
    cin >> n;
    a = n;
    while(n)
    {
        rem = n % 10;
        sum += rem;
        n /= 10;
    }
    a % sum == 0?
    cout << "Yes" << '\n':
    cout << "No" << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int num2(int);

int main(){
  int N;
  int a[10000];
  scanf("%d", &N);
  for(int i=0; i<N; i++){
    scanf("%d", &a[i]);
  }

  int cnt=0;
  for(int i=0; i<N; i++){
    cnt+=num2(a[i]);
  }

  printf("%d\n",cnt);
  
  return 0;
}

int num2(int n){
  int cnt=0;
  for(int i=0; i<30; i++){
    if(n%2==1){
      break;
    }else{
      cnt++;
      n/=2;
    }
  }

  return cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOREACH(element, vec_name) for (auto &(element) : (vec_name))
#define VECCIN(vec_name) for (auto &element : (vec_name)) cin >> element
typedef long long ll;
const int INF = 1e9;
typedef pair<int,int> P;
P f(int x){
    int a = x%10;
    int b = 0;
    while(x){
        b = x;
        x /= 10;
    }
    return P(a,b);
}
int main()
{
    int n;
    cin >> n;
    map<P,int> mp;
    for(int i = 1; i <= n; i++){
        P p = f(i);
        mp[p]++;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        P p = f(i);
        P q(p.second, p.first);
        ans += mp[q];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
// C - Walk on Multiplication Table
#include <bits/stdc++.h>
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
const lli INF = 2147483647;
const lli MINF = -2147483648;
const lli LINF = 9223372036854775807;
const lli MOD = 1000000007; //10^9+7
const long double PI = acos(-1);
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define Vec(K, L, N, S) vector<L> K(N, S)
#define rt sqrt
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("Ofast")
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using P = pair<lli, lli>;
// vector<P> vp;
// vp.emplace_back(a[i], b[i]);
using vs = vector<string>;
using ll = long long;
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}
vector<pair<long long, long long>> prime_factorize(long long N)
{
  vector<pair<long long, long long>> res;
  for (long long a = 2; a * a <= N; ++a)
  {
    if (N % a != 0)
      continue;
    long long ex = 0; // 指数

    // 割れる限り割り続ける
    while (N % a == 0)
    {
      ++ex;
      N /= a;
    }

    // その結果を push
    res.push_back({a, ex});
  }

  // 最後に残った数について
  if (N != 1)
    res.push_back({N, 1});
  return res;
}
bool is_prime(long long N)
{
  if (N == 1)
    return false;
  for (long long i = 2; i * i <= N; ++i)
  {
    if (N % i == 0)
      return false;
  }
  return true;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli a, b, c, h, k, n, w, ans = LINF, count = 0;
  string s, t;
  cin >> n;
  // vi d;
  if (is_prime(n))
  {
    cout << n - 1 << "\n";
    return 0;
  }
  // const auto &res = prime_factorize(n);
  // for (auto p : res)
  // {
  //   for (int i = 0; i < p.second; ++i)
  //     d.eb(p.first);
  // }

  // do
  // {
  //   rep(i, 0, d.size() - 1)
  //   {
  //     rep(j, 0, d.size() - 1)
  //     {
  //       ans = min(ans, d[])
  //     }
  //   }
  // } while (next_permutation(ALL(d)));
  repe(i, 1, sqrt(n))
  {
    if (n % i == 0)
    {
      a = i;
      b = n / i;
      ans = min(ans, a + b - 2);
    }
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <limits.h>	
using namespace std;
int in(void){
	int i;scanf("%d",&i);
	return i;
}
int main(void){
	int a=in(),b=in();
	if(a%3==0||b%3==0||(a+b)%3==0){
		puts("Possible");
	}
	else{
		puts("Impossible");
	}
	return 0;
}

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

#define all(v)			((v).begin()), ((v).end())
#define SIZE(v)			((int)((v).size()))
#define LOG(x)			log((double)x)
#define TOLOWER(x)          transform(all(x),x.begin(),::tolower)
#define TOUPPER(x)          transform(all(x),x.begin(),::toupper)
#define ROUND(x,m)			(round((double)x/m)*m)
#define DIGITS(x)			(floor(log10((double)x))+1)
#define READSTR(x)			getline(cin,x)
#define sort_g(a,b)              sort(a, b, greater<int>());
#define IOS() ios_base::sync_with_stdio(0);cin.tie(NULL);
#define REP(i, n) for (int i = 0; i < n; i++)
#define FILE_INPUT() 	freopen( "input.txt", "r", stdin)
#define FILE_OUTPUT()   freopen( "output.txt", "w", stdout)

typedef long long ll;

bool myCmp(pair<int,int> &p1 , pair<int,int>&p2)
{
    return p1.first > p2.first;
}
unsigned long long
choose(unsigned long long n, unsigned long long k) {
    if (k > n) {
        return 0;
    }
    unsigned long long r = 1;
    for (unsigned long long d = 1; d <= k; ++d) {
        r *= n--;
        r /= d;
    }
    return r;
}
int toInt(string str)
{
    int num;
    std::istringstream iss(str); //put string in input stream
    iss >> num; return num; //read from stream as integer
}
ll  OO = 10e9;

const int MAXN = 2*10e3 + 1;
int X[MAXN];
ll cnt = 0;
int main() {
    IOS();
    int n;
    cin>>n;
    REP(i,n) cin>>X[i];

    if(n <= 2)
    {
        cout<<0<<endl;
        return 0;
    }
    //we need to form acute angle triange
    sort(X,X+n);
    //get a and b and check if exits
    for(int i = 0; i < n ; ++i)
    {
        for(int j=i+1 ; j < n ; ++j)
        {
            if(i == j) continue;
            auto mn = X[j] - X[i];
            int ub =  upper_bound(X,X+n,mn) - X;
            if(ub == n) continue;
            int lb = lower_bound(X,X+n,X[i]+X[j]) - X;
            if(lb == 0) continue;
            lb--;
            cnt+= (lb-ub + 1);
            if( (i <= lb) && (i >= ub)) cnt--;
            if( (j <= lb) && (j >= ub)) cnt--;
        }
    }
    cout<<cnt/3<<endl;
    return 0;
}



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

int main(){
    int a,b;
    char p;
    cin>>a>>p>>b;
    switch(p){
        case '+': 
            cout<<a+b<<endl;
            return 0;
        case '-':
            cout<<a-b<<endl;
            return 0;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;
using namespace std;
 
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair <long long,long long> ii;
typedef complex<long double> point;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
	cin >> s;
	if (s == "Sunny") cout << "Cloudy" << endl;
	else if (s == "Cloudy") cout << "Rainy" << endl;
	else cout << "Sunny" << endl;
}

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

main()
{
  int a,b;
  cin >> a >> b;
  
  if(a>0)
    cout << "Positive" << endl;
  if(a<=0&&b>=0)
    cout << "Zero" << endl;
  if(a<0&&b<0){
    if((a-b)%2!=0)
      cout << "Positive" << endl;
    else
      cout << "Negative" << endl;
  }
  
  return (0);
}
    


Measured memory_bytes: 256
/*
    ThunderClap and Flash.
    Raunaq Singh
*/
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define ThunderClap ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define debugg(something)   cout<<#something<<" - "<<something<<"\n";
#define vi vector
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define LB lower_bound
#define UB upper_bound
#define mp make_pair
#define pb push_back
#define in insert
#define s second
#define f first
#define pQueue priority_queue
#define maxElement *max_element
#define minElement *min_element
#define MAX 100000LL
#define mod 1000000007LL
#define inf 1000000000000000000LL
#define mI2 500000004LL
inline ll add(ll a, ll b){ return ((a%mod)+(b%mod))%mod;}
inline ll mul(ll a, ll b){ return ((a%mod)*(b%mod))%mod;}
inline ll sub(ll a, ll b){ return ((a%mod)-(b%mod)+mod)%mod;}

void Flash(){
    string s;
    cin>>s;
    ll n=s.size();
    if(n&1){
        cout<<"No\n";
    }else{
        for(ll i=0;i<n;i+=2){
            if(s[i]!='h' || s[i+1]!='i'){
                cout<<"No\n";
                return;
            }
        }
        cout<<"Yes\n";
    }
}

int main(int argc, char const *argv[]){
    ThunderClap;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        Flash();
    }
    return 0;
}

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

const ll mod = 1e9 + 7;

int main() {
  string S; cin >> S;
  int N = S.length();
  auto dp = vector<vector<ll>>(N + 1, vector<ll>(4, 0));
  dp[0][0] = 1;
  for (int i = 0; i < N; ++i) {
    if (S[i] == 'A' || S[i] == '?') {
      dp[i + 1][0] += dp[i][0];
      dp[i + 1][1] += dp[i][1];
      dp[i + 1][2] += dp[i][2];
      dp[i + 1][3] += dp[i][3];
      dp[i + 1][1] += dp[i][0];
    }
    if (S[i] == 'B' || S[i] == '?') {
      dp[i + 1][0] += dp[i][0];
      dp[i + 1][1] += dp[i][1];
      dp[i + 1][2] += dp[i][2];
      dp[i + 1][3] += dp[i][3];
      dp[i + 1][2] += dp[i][1];
    }
    if (S[i] == 'C' || S[i] == '?') {
      dp[i + 1][0] += dp[i][0];
      dp[i + 1][1] += dp[i][1];
      dp[i + 1][2] += dp[i][2];
      dp[i + 1][3] += dp[i][3];
      dp[i + 1][3] += dp[i][2];
    }
    dp[i + 1][0] %= mod;
    dp[i + 1][1] %= mod;
    dp[i + 1][2] %= mod;
    dp[i + 1][3] %= mod;
  }
  cout << dp[N][3] << endl;
  return 0;
}


Measured memory_bytes: 7424
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<numeric>
#include<stdio.h>

using std::cout;
using std::cout;
using std::cin;
using std::setw;
using std::setfill;
using std::string;
using std::pair;
using std::make_pair;
using std::vector;
using std::queue;
using std::deque;
using std::priority_queue;
using std::next_permutation;
using std::iota;
using std::sort;
using std::greater;
using std::max;
using std::min;

#define INF 999999999;
#define MOD 1000000007

using ulli = unsigned long long int;

#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

int abc[27];
int N;
string S;
int cnt, ans=0;

int main(){
	cin.tie(0);
	std::ios::sync_with_stdio(false);
    
    cin >> N;
    cin >> S;
    for(int i = 0; i < 26; i++) abc[i]=0;
    for(int i = 0; i < N-1; i++){
        for(int j = 0; j < N; j++){
            if(j <= i){
                abc[ S[j] - 'a' ] = 1;
            }else{
                if(abc[ S[j] - 'a' ] == 1){
                    cnt++;
                    abc[ S[j] - 'a' ] = 2;
                }
            }
        }
        ans = max(cnt, ans);
        for(int i = 0; i < 26; i++) abc[i]=0;
        cnt = 0; 
    }

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll, ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vvi vector<vi>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define pqueue priority_queue
#define si(a) scanf("%d", &a)
#define sll(a) scanf("%lld", &a)
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
#define MOD 1000000007
#define N 300005
using namespace std;

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;

//All indexing is 0-based
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
       tree_order_statistics_node_update> ordered_set;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar.

//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c;}
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}

int n, m;
string s;
vi adj[N];
int ar[N][2];
bitset<N> exists;

int main()
{ 
  #ifdef CP
    freopen("/home/tarun/Desktop/input.txt", "r", stdin);
    //freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  #endif
  sync;
  clock_t clk = clock();
  cerr << "I will return...\n";

  cin >> n >> m >> s;
  for(char &c : s) c = tolower(c);
  rep(i, 0, n) exists[i] = 1;
  rep(i, 0, m) {
    int u, v; cin >> u >> v;
    u--, v--;
    adj[u].pb(v);
    adj[v].pb(u);
    ar[u][s[v] - 'a']++;
    ar[v][s[u] - 'a']++;
  }

  vi q;

  rep(i, 0, n) {
    if(ar[i][0] == 0 || ar[i][1] == 0) {
      q.push_back(i);
      exists[i] = 0;
    }
  }

  rep(oo, 0, q.sz) {
    int i = q[oo];
    //q.pop();

    for(int j : adj[i]) {
      ar[j][s[i] - 'a']--;
      if(ar[j][s[i] - 'a'] == 0) {
        if(exists[j]) {
          exists[j] = 0;
          q.push_back(j);
        }
      }
    }
  }

  cout << (q.sz == n ? "No\n" : "Yes\n");
 
  cerr << "...don't you ever hang your head.\n";
  cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
}

//Compile using:
//g++ -o filename.exe --std=c++11 filename.cpp
//Use -D CP for defining a macro CP in the local environment







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

int n, m, k;
int a[20000];
int dp[20000];

int dfs(int id) {
	if (id >= n) return 0;
	if (dp[id] != 0) return dp[id];

	int ret = 2000000000000000000;
	int maxi = -1145141919;
	int mini = 1145141919;
	for (int s = 1; s <= m; s++) {
		if (id + s > n) { continue; }
		maxi = max(maxi, a[id + s - 1]);
		mini = min(mini, a[id + s - 1]);
		ret = min(ret, dfs(id + s) + k + s * (maxi - mini));
	}
	return (dp[id] = ret);
}

signed main() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	cout << dfs(0) << endl;
	return 0;
}

Measured memory_bytes: 2404
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    long a,b,t,s=0;
    cin>>t;
    while(t--){
        cin>>a>>b;
        s=s+(b-a)+1;
    }
    cout<<s;
    return 0;
}
  

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <string>
#include <numeric>
#include <math.h>
#include <set>
#include <map>
#include <fstream>
#include <sstream>
#include <iterator>
#include <complex>
using namespace std;

int main()
{
	int N,K;
	cin>>N>>K;
	vector<int> V(N);
	for(int i=0; i<N; i++)
	{
		cin>>V[i];
	}
	//4つの累積和で出す
	vector<int> L(N+1);
	vector<int> R(N+1);
	vector<vector<int>> L_Minus(N+1);
	vector<vector<int>> R_Minus(N+1);

	for(int i=0; i<N; i++)
	{
		L[i+1] = L[i] + V[i];
		L_Minus[i+1] = L_Minus[i];
		if(V[i]<0)
		{
			L_Minus[i+1].push_back(V[i]);
			sort(L_Minus[i+1].begin(),L_Minus[i+1].end());
		}
	}

	for(int i=0; i<N; i++)
	{
		R[i+1] += R[i] + V[N-1-i];
		R_Minus[i+1] = R_Minus[i];
		if(V[N-1-i]<0)
		{
			R_Minus[i+1].push_back(V[N-1-i]);
			sort(R_Minus[i+1].begin(),R_Minus[i+1].end());
		}

	}
	int result = 0;
	
	if(K>=L_Minus[N].size()+N)
	{
		result = L[N] - accumulate(L_Minus[N].begin(),L_Minus[N].end(),0);
		cout<<result<<endl;
		return 0;
	}

	for(int i=0; i<=K; i++)
	{
		int time = i;
		for(int j=0; j<=time; j++)
		{
			int l = j;
			int r = time - j;

			int L_side = 0;
			int R_side = 0;
			
			for(int k=l; k>=0; k--)
			{
				if(L_Minus[k].size()+k<l)
				{
					break;
				}

				L_side = max(L_side,L[k] - accumulate(L_Minus[k].begin(),L_Minus[k].begin()+(l-k),0));

			}
			for(int k=r; k>=0; k--)
			{
				if(R_Minus[k].size()+k<r)
				{
					break;
				}

				R_side = max(R_side,R[k] - accumulate(R_Minus[k].begin(),R_Minus[k].begin()+(r-k),0));
			}
			result = max(result,L_side+R_side);
		}
	}

	cout<<result<<endl;
	return 0;
}

Measured memory_bytes: 256
#if 1
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <set>
#include <map>
#include <numeric>
#include <cassert>

using namespace std;
#define int long long
#define uint unsigned long long
constexpr int MOD = 1000000007;
constexpr int INF = 1145141919810;

#define LOADVEC(type,name,N) std::vector<type>name(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name[nnn]; \
}

#define LOADVEC2(type,name0,name1,N) std::vector<type>name0(N),name1(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn]; \
}

#define LOADVEC3(type,name0,name1,name2,N) std::vector<type>name0(N),name1(N),name2(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn];cin >> name2[nnn]; \
}

#define LOAD(type,name) type name; \
cin >> name;


void proc();

signed main() {
	ios::sync_with_stdio(false);
	proc();
	return 0;
}

/*
--------------------------------------------------------
--------------------------------------------------------
---------------    template      ----------------------
--------------------------------------------------------
--------------------------------------------------------
*/

void proc() {
	LOAD(int, N);
	LOAD(int, M);
	std::vector<int>A(M), B(M);
	std::unordered_map<int, std::set<int>> link;
	for (int i = 0; i < M; ++i) {
		cin >> A[i];
		cin >> B[i];
		link[A[i]].insert(B[i]);
		link[B[i]].insert(A[i]);
	}
	//
	std::vector<int> path0, path1;
	unordered_set<int> vertexes = { A[0] ,B[0] };
	path0.push_back(A[0]);
	path1.push_back(B[0]);
	//
	while (true) {
	a:
		for (auto next : link[path0.back()]) {
			auto itr = vertexes.find(next);
			if (itr == vertexes.end()) {
				path0.push_back(next);
				vertexes.insert(next);
				goto a;
			}
		}
		break;
	}


	while (true) {
	b:
		for (auto next : link[path1.back()]) {
			auto itr = vertexes.find(next);
			if (itr == vertexes.end()) {
				path1.push_back(next);
				vertexes.insert(next);
				goto b;
			}
		}
		break;
	}
	//
	cout << path0.size() + path1.size() << endl;
	std::vector<int> path2(path0.size());
	for (int i = 0; i < path0.size(); ++i) {
		path2[path0.size() - 1 - i] = path0[i];
	}
	//
	for (int i = 0; i < path2.size(); ++i) {
		cout << path2[i] << " ";
	}
	for (int i = 0; i < path1.size(); ++i) {
		cout << path1[i];
		if (i != path1.size() - 1) {
			cout << " ";
		}
	}
}


#endif


Measured memory_bytes: 26144
#[allow(unused_imports)]
use {
    itertools::Itertools,
    proconio::{fastout, input, marker::*},
    std::cmp::*,
    std::collections::*,
    std::io::Write,
    std::ops::*,
};

#[allow(unused_macros)]
macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; }

struct UnionFind {
    n: usize,
    par: Vec<usize>,
    rank: Vec<usize>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            n,
            par: (0..n).collect(),
            rank: vec![1; n],
        }
    }
    fn unite(&mut self, x: usize, y: usize) {
        if self.same(x, y) {
            return;
        }
        let rx = self.par[x];
        let ry = self.par[y];
        if self.rank[rx] > self.rank[ry] {
            self.par[ry] = rx;
            self.rank[rx] += self.rank[ry];
        } else {
            self.par[rx] = ry;
            self.rank[ry] += self.rank[rx];
        }
    }
    fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }
    fn root(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            x
        } else {
            self.par[x] = self.root(self.par[x]);
            self.par[x]
        }
    }
    #[allow(dead_code)]
    fn size(&mut self, x: usize) -> usize {
        let r = self.root(x);
        self.rank[r]
    }
    #[allow(dead_code)]
    fn sizes(&mut self) -> Vec<usize> {
        let mut s = vec![];
        for x in 0..self.n {
            if x == self.root(x) {
                s.push(self.rank[x]);
            }
        }
        s
    }
    #[allow(dead_code)]
    fn groups(&mut self) -> Vec<Vec<usize>> {
        let mut g = vec![vec![]; self.n];
        for i in 0..self.n {
            g[self.root(i)].push(i);
        }
        g.iter()
            .filter(|v| !v.is_empty())
            .map(|v| v.clone())
            .collect()
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(Usize1, Usize1); m]
    }
    let mut uf = UnionFind::new(n);
    for (a, b) in ab {
        uf.unite(a, b);
    }
    println!("{}", uf.groups().len() - 1);
}


Measured memory_bytes: 12740
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

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

	cin >> W >> H >> K;
	vector<long long int>by(220001,1);
	for (int i = 1; i <= 220000; i++) {
		by[i] = by[i - 1] * i;
		by[i] %= MOD;
	}
	long long int ans = 0;
	for (int i = 0; i <= K; i++) {
		long long int bag = 1;
		bag *= by[W + i * 2];
		bag %= MOD;
		bag *= power(by[i], MOD - 2, MOD);
		bag %= MOD;
		bag *= power(by[W + i], MOD - 2, MOD);
		bag %= MOD;
		bag *= W + 1;
		bag %= MOD;
		bag *= power(W + 1 + i, MOD - 2, MOD);
		bag %= MOD;
		int j = K - i;
		bag *= by[H + j * 2];
		bag %= MOD;
		bag *= power(by[j], MOD - 2, MOD);
		bag %= MOD;
		bag *= power(by[H + j], MOD - 2, MOD);
		bag %= MOD;
		bag *= H + 1;
		bag %= MOD;
		bag *= power(H + 1 + j, MOD - 2, MOD);
		bag %= MOD;
	//	cout << bag << endl;
		bag *= by[H + W + 2 * K];
		bag %= MOD;
	//	cout << bag << endl;
		bag *= power(by[W + i * 2], MOD - 2, MOD);
		bag %= MOD;
	//	cout << bag << endl;
		bag *= power(by[H + j * 2], MOD - 2, MOD);
		bag %= MOD;
	//	cout << bag << endl;
		ans += bag;
		ans %= MOD;
	//	cout << ans << endl;
	}
	cout << ans << endl;
	return 0;
} 


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

int main(){
    int N,M;
    cin >> N >> M;
    vector<int> vec(N);
    for(int i=0; i<M; i++){
        int a,b;
        cin >> a >> b;
        vec.at(a-1)++;
        vec.at(b-1)++;
    }
    for(int i=0; i<N; i++){
        cout << vec.at(i) << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e5+10,LN=30,SQ=550;
const ll INF=1e16;
const int MOD=/*1000000007*/ 998244353;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,k,dp[N],f[2*N];
pll p[11];
void add(ll v, ll x){
    v+=N;
    while(v<2*N){
        f[v]+=x;
        v+=v&-v;
    }
}
ll get(ll v){
    v+=N;
    ll ans=0;
    while(v>N){
        ans+=f[v];
        ans%=MOD;
        v-=v&-v;
    }
    return ans;
}
int main(){
    fast_io;
    cin >> n >> k;
    for(ll i=0; i<k; i++) cin >> p[i].F >> p[i].S;
    dp[1]=1;
    add(1,dp[1]);
    for(ll i=2; i<=n; i++){
        for(ll j=0; j<k; j++){
            dp[i]+=(get(i-p[j].F)-get(i-p[j].S-1)+MOD)%MOD;
            dp[i]%=MOD;
        }
        add(i,dp[i]);
    }
    cout << dp[n];
    return 0;
}


Measured memory_bytes: 6748
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100005
using namespace std;
int n, mx, a[N], x[N], y[N];
int main() {
	int i;
	cin>>n;
	for(i=0; i<n; i++) scanf("%d", &a[i]);
	x[0] = a[0];
	y[n-1] = a[n-1];
	for(i=0; i<n; i++) x[i] = __gcd(x[i-1], a[i]);
	for(i=n-2; i>=0; i--) y[i] = __gcd(y[i+1], a[i]);
	mx = max(x[n-2], y[1]);
	for(i=1; i<n-1; i++) mx = max(mx, __gcd(x[i-1], y[i+1]));
	cout<<mx;
	return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const int MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

template<typename T>
struct edge {
    int to;
    T cost;
};

using P = pair<int, int>;

int main() {
    int V, E, r;
    cin >> V >> E >> r;

    vector<edge<int> > G[V];
    int d[V];
    
    rep(i, E){
        int s,t,c;
        cin >> s >> t >> c;
        G[s].push_back({t,c});
        // G[t].push_back({s,c});
    }
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[r] = 0;
    que.push(P(0, r)); // 最短距離、頂点番号
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(auto &e : G[v]){
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    for(const auto &c : d){
        if(c == INF) cout << "INF" << endl;
        else cout << c << endl;
    }
    return 0;
}


Measured memory_bytes: 12972
/*
    Believe!
    @Author : tpriyanshu
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;
typedef unsigned long int uli;
typedef pair<int,int> pi;
typedef pair<lli,lli> plli;
typedef vector<int> vi;
#define mod 1000000007
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define point(n) fixed<<setprecision(n)
#define endl "\n"
#define mem(a,val) memset(a,val,sizeof(a))
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define w(x) lli x; cin>>x; while(x--)
#define forn(i, a, n) for (int i = a; i < int(n); ++i)
#define inf 1e18
#define N int(2*1e5+10)
#define all(v) v.begin(),v.end()
mt19937 rnd(time(NULL));

void out(vi& v) {
	for (lli i = 0; i < v.size(); i++) {
		cout << v[i]  << " ";
	}
	cout << endl;  
}
int main(){
    fastIO
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n,m;
    cin>>n>>m;
    if(m>=n){
        cout<<"unsafe";
    } else{
        cout<<"safe";
    }
    
    return 0;
}

Measured memory_bytes: 3656
#include<iostream>
using namespace std;
static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

void dijkstra() {
	int minv;
	int d[MAX], color[MAX];

	for (int i = 0; i < n; i++ ) {
		d[i] = INFTY;
		color[i] = WHITE;
	}

	d[0] = 0;
	color[0] = GRAY;
	while ( 1 ) {
		minv = INFTY;
		int u = -1;
		for (int i = 0; i < n; i++ ) {
			if ( minv > d[i] && color[i] != BLACK ) {
				u = i;
				minv = d[i];
			}
		}
		if ( u == -1 ) break;
		color[u] = BLACK;
		for (int v = 0; v < n; v++ ) {
			if ( color[v] != BLACK && M[u][v] != INFTY ) {
				if (d[v] > d[u] + M[u][v] ) {
					d[v] = d[u] + M[u][v];
					color[v] = GRAY;
				}
			}
		}
	}
	for ( int i = 0; i < n; i++ ) {
		cout << i << " " << ( d[i] == INFTY ? -1 : d[i] ) << endl;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++ ) {
			M[i][j] = INFTY;
		}
	}

	int k, c, u, v;
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		for (int j = 0; j < k; j++ ) {
			cin >> v >> c;
			M[u][v] = c;
		}
	}

	dijkstra();

	return 0;
}


Measured memory_bytes: 3112
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main{

	/**
	 * List of Top 3 Hills
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		List<Integer> hillList = new ArrayList<Integer>();

		while (scanner.hasNextInt()) {
			hillList.add(scanner.nextInt());
		}

		Comparator<Integer> comparator = new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		};
		Collections.sort(hillList, comparator);

		System.out.println(hillList.get(0));
		System.out.println(hillList.get(1));
		System.out.println(hillList.get(2));
	}
}

Measured memory_bytes: 17184
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>
#include <stack>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << 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; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define sz(x) (ll)(x).size()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

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

  ll n;
  cin >> n;
  ll k = 1;
  while ((k*(k-1)/2) < n) {
    ++k;
  }
  if (k*(k-1)/2 != n) {
    cout << "No" << endl;
    return 0;
  }

  // Here, kC2 == n
  cout << "Yes" << endl;
  cout << k << endl;

  ll c = 0;
  vector<vector<ll>> nums(k);
  rep(i,k)rep(j,i) {
    // assign c to (i,j)
    nums[i].push_back(c);
    nums[j].push_back(c);
    ++c;
  }

  rep(i,k) {
    sort(all(nums[i]));

    cout << nums[i].size();
    for (ll v : nums[i]) {
      cout << " " << v+1;
    }
    cout << endl;
  }
}


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

#define int long long int
#define double long long double
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define endl "\n"

int v[105], w[105];
int W, N;
int cache[105][100005];

int dp(int idx, int wt)
{
	if (wt > W)
		return -2e15;
	if (idx > N)
		return 0;
	int &ans = cache[idx][wt];
	if (ans != -1)
		return ans;
	ans = max(dp(idx + 1, wt), v[idx] + dp(idx + 1, w[idx] + wt));
	return ans;
}

int32_t main()
{
	IOS;
	cin >> N >> W;
	memset(cache, -1, sizeof(cache));
	for (int i = 1; i <= N; i++)
		cin >> w[i] >> v[i];
	int ans = dp(1, 0);
	cout << ans << endl;
	return 0;
}

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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))
#define X first
#define Y second

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vs = vector<string>;

constexpr int MOD = int(1e9 + 7);
constexpr int INF = int(1e9 + 1);
constexpr ll LLINF = ll(4 * 1e18 + 1);
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);
	string s;
	cin >> s;
	ll ans = 0;
	int cnt = 0;
	for(int i = s.size() - 1; i >= 0; --i){
		if(s[i] == 'B') {
			ans += s.size() - i - 1 - cnt;
			cnt++;
		}
	}
	cout << ans << "\n";
	return 0;
}


Measured memory_bytes: 1228
#include <bits/stdc++.h>
#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,b,a) for(int i=(b);i>=(a);i--)
#define len(a) int((a).size())
using namespace std;
using LL = long long;
using PII = pair<int, int>;

int main() {
    string s;
    cin >> s;
    vector<int> A(4);
    FI(i,0,3) A[i] = s[i] - '0';
    FI(mask,0,7) {
        bitset<3> b(mask);
        int result = A[0];
        FI(i,0,2) {
            result += A[i+1] * (b.test(i) ? 1 : -1);
        }
        if (result == 7) {
            printf("%d", A[0]);
            FI(i,0,2) printf("%c%d", b.test(i) ? '+' : '-', A[i+1]);
            printf("=7\n");
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

bool enough(vi &h, ll num, ll a, ll b){
    // a>bであるため、num回bの蓄積ダメージが全体に入り、かつnum回a-bの追加ダメージを与えられる。
    ll sumDamage = num * b;
    ll cnt = 0;
    for(ll i=0; i<h.size(); i++){
        if(h[i] <= sumDamage) continue;
        cnt += (ll)ceil((1.0*(h[i]-sumDamage))/(a-b));
    }
    return (cnt <= num) ? true : false;
}

int main(){
    Init();
    // n; monster, a;centerDamage, b;otherDamage
    ll n, a, b; cin >> n >> a >> b;

    // monster; <hp, number>;
    vi h(n); rep(i, n) cin >> h[i];

    // binary-search
    ll l = 0, r = 10e9;
    while(abs(r-l)>1){
        ll mid = (l+r)/2;
        (enough(h, mid, a, b) ? r : l) = mid;
    }

    // output
    cout << r << endl;
}

Measured memory_bytes: 3996
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define all(x) (x).begin(), (x).end()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end());
const long long INF = 1LL << 60;
// map<int,int> mp;

bool solve(int n) {
  int k = to_string(n).size();
  if (k % 2 == 1) return true;
  return false;
}

int main() {
  int n, ans = 0;
  cin >> n;
  for (int i = 1; i < n + 1; i++) {
    if (solve(i) == true) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3760
n=int(input())
List=(list(map(int,input().split())))
l=len(List)
count=0

for i in range(l):
    if List[i]%2!=0:
        count+=1
    elif List[i]%2==0:
        if List[i]%3==0 or List[i]%5==0:
            count+=1

if count==len(List):
    print("APPROVED")

else:
    print("DENIED")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
map<int,int>ma;
int n,l,r,a[N],b[N],c[N];
bool check(int x){
    int l=0,r=0,tl=0,tr=0;
    for(register int i=1;i<=n;i++) b[i]=(a[i]>x);
    for(register int i=(n+1)>>1;i<=n;i++){
        if(b[i]==b[i+1]){
            tr=b[i];
            break;
        }
        ++r;
    }
    for(register int i=(n+1)>>1;i;i--){
        if(b[i]==b[i-1]){
            tl=b[i];
            break;
        }
        ++l;
    }
    if(l<r) tr=tl;
    if(min(l,r)>=(n+1)/2)    tr=b[(n+1)/2]^(((n+3)/2)%2);
    return tr;
}
int main(){
    scanf("%d",&n),n=n*2-1;
    for(register int i=1;i<=n;i++)
        scanf("%d",&a[i]),c[i]=a[i];
    sort(c+1,c+n+1),b[0]=b[n+1]=-1;
    for(register int i=1;i<=n;i++)   ma[c[i]]=i;
    for(register int i=1;i<=n;i++)   a[i]=ma[a[i]];
    register int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid))  l=++mid;
        else    r=mid;
    }
    printf("%d\n",c[l]);
    return 0;
}

Measured memory_bytes: 13184