akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline int rd(char c[]){
  int i, sz=0;
  for(;;){
    i = getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N;
int K;
char S[100002];
int len[100003];
int s[100003];
int sz;
int main(){
  int c, i, j, k, res;
  rd(N);
  rd(K);
  rd(S);
  c = '1';
  sz++;
  for(i=0;i<N;i++){
    if(c==S[i]){
      len[sz-1]++;
    }
    else{
      c=S[i];
      len[sz++]++;
    }
  }
  if(c != '1'){
    sz++;
  }
  for(i=0;i<sz;i++){
    s[i+1] = s[i] + len[i];
  }
  res = 0;
  K = 2*K+1;
  if(K >= sz){
    res = N;
  }
  else{
    for(i=K;i<=sz;i+=2){
      chmax(res, s[i] - s[i-K]);
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190608-2

// --- original code ---
// int N, K; char S[100002];
// 
// int len[100003], s[100003], sz;
// {
//   int i, j, k;
//   int c, res;
//   
//   rd(N,K,S);
// 
//   c = '1';
//   sz++;
//   rep(i,N){
//     if(c==S[i]) len[sz-1]++;
//     else        c=S[i], len[sz++]++;
//   }
//   if(c != '1') sz++;
//   rep(i,sz) s[i+1] = s[i] + len[i];
// 
//   res = 0;
//   K = 2K+1;
//   if(K >= sz){
//     res = N;
//   } else {
//     for(i=K;i<=sz;i+=2) res >?= s[i] - s[i-K];
//   }
// 
//   wt(res);
// }


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main(){
    int K,S;
    cin >> K >> S;
    int answer = 0;;
    for(int i=0;i<=K;i++){
        for(int j=0;j<=K;j++){
            int k = S-i-j;
            if(k>=0 && k<=K)answer+=1;
        }
    }
    cout << answer << endl;
}

Measured memory_bytes: 256
public class Main {

  private static void solve() {
    int n = ni();
    int m = ni();
    int q = ni();

    int[][] p = ntable(q, 4);

    int ret = dfs(0, new int[n], m, p);
    System.out.println(ret);

  }

  private static int dfs(int i, int[] a, int m, int[][] p) {
    int n = a.length;
    if (i == n) {
      int score = 0;
      for (int[] q : p) {
        if (a[q[1] - 1] - a[q[0] - 1] == q[2]) {
          score += q[3];
        }
      }
      return score;
    }

    int ret = 0;
    int s = i == 0 ? 1 : a[i - 1];
    for (int k = s; k <= m; k++) {
      a[i] = k;

      int v = dfs(i + 1, a, m, p);
      ret = Math.max(v, ret);
    }
    return ret;
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}



Measured memory_bytes: 36836
#include <stdio.h>
int main()
{
    int L, R, d;
	scanf("%d%d%d", &L, &R, &d);
	if(L == R)
	{
	    if(L%d == 0)
	        printf("1\n");
	    else
	        printf("0\n");
	}
	else if(L % d == 0 && R % d == 0)
		printf("%d\n", 2 + (R - L - 1)/ d);
	else if(L % d == 0 || R % d == 0)
	    printf("%d\n", 1 + (R - L)/ d);
	else
	    printf("%d\n", (R - L)/ d);
	return 0;
}

Measured memory_bytes: 1708
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll S;
    cin >> S;

    vector<vector<ll> > dp(1000, vector<ll>(S+1));
    rep(n, S+1) {
        if (n >= 3) {
            dp[1][n] = 1;
        }
    }

    ll mod = 7LL + 1e9;
    for (int i = 2; i < dp.size(); i++) {
        vector<ll> Sum(S+1);
        repi(n, S+1) {
            Sum[n] = (Sum[n-1] + dp[i-1][n]) % mod;
        }

        rep(n, S+1) {
            if (n < 3) {
                continue;
            }
            ll v = Sum[n - 3];
            // // dp[i-1][0] ~ dp[i-1][n-3]のワ
            // for (int m = 3; 0 <= n - m; m++) {
            //     v += dp[i-1][n-m];
            //     v %= mod;
            // }
            dp[i][n] = v;
        }
    }

    ll res = 0;
    rep(i, dp.size()) {
        res += dp[i][S];
        res %= mod;
    }

    put(res);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 18620
#include <bits/stdc++.h>
#define pb push_back
#define tam 120004
#define offset 320000
#define se second
#define fi first
#define pitem item*
#define ptr tre*
#define forr(i,p,n) for(ll i=p;i<n;i++)
using namespace std;
typedef long long ll;
const ll MOD=1000000007 ;
ll mult(ll a,ll b, ll p=MOD){return ((a%p)*(b%p))%p;}
ll add(ll a, ll b, ll p=MOD){return (a%p + b%p)%p;}
typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
vector<int> grafo[tam];
bool vis[tam];
int c=0;
int resp[tam],val[tam];
int n;

void dfs(int num)
{
    vis[num]=1;
    resp[num]=val[c++];
    int hijo;
    forr(i,0,grafo[num].size())
    {
        hijo=grafo[num][i];
        if (vis[hijo]==false)
            dfs(hijo);
    }
}
int main()
{
   
   int iz,der;
   cin>>n;
   forr(i,0,n-1)
   {
    cin>>iz>>der;
    grafo[iz].pb(der);
    grafo[der].pb(iz);
   }
   forr(i,0,n)
    cin>>val[i];
   sort(val,val+n);
   reverse(val,val+n);
   int tot=0;
   forr(i,1,n+1)
   tot+=val[i];
   int num=1;
   memset(vis,0,sizeof vis);
   forr(i,1,n+1)
   {
        if (grafo[i].size()>1)
        num=i;
   }
   //cout<<num<<endl;
   cout<<tot<<endl;
   dfs(num);
   forr(i,1,n+1)
   cout<<resp[i]<<" ";

}

Measured memory_bytes: 3840
//*************************************JAI SAI RAM*************************************//
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
ll a[300001],q[300001];
ll P=998244353;
void solve()
{
    ll i,j,k,l,m,n,o,r;
    ll ans=0;
    set<ll> se;
    vector<ll> v;
    map<ll,ll> mp;   
    //cin>>i>>j>>k;
    //cout<<((i+j-1)/j)*k<<endl; 
    cin>>n;
    m=-1;
    for(i=0;i<n;i++)
    {
        cin>>j;
        if(j<m)
        {
            ans+=m-j;
        }
       m=max(m,j);
    }
    cout<<ans<<endl;
}
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
     ll t=1;
   // cin>>t;
    ll o=1;
    while(t--)
    {

        solve();
        o++;
    }
     return 0;
}












































//manpreet.singh orz
//humane orz
//arnavvats orz
//leoamish300 orz
//cipher76 orz
//aug16arpit orz
//aayushindwan orz
//ig_monkey orz
//DeadlyCritic orz
//lucky_21 orz
//sak23 orz
//spookywooky orz
//supahotfire orz
//__FAILURE_orz
//Errichto orz
//tourist orz
//Um_nik orz
//300iq orz
//antontrygub_Oo orz
//boboniu orz
//MikeMirzayanov orz
//MiFaFaOvO orz
// Benq orz
//Radewoosh orz
//AshishGup orz
//Ashishchup orz
//aryanc403 orz
//ma_da_fa_ka orz
// Striver_79 orz
//Love babbar orz
// My Life of ultimate patience and hard work orz!!!!!!!


Measured memory_bytes: 3656
N,T = list(map(int, input().split()))
t = list(map(int, input().split()))

ans = T
for i in range(1, N):
    ans += T
    if t[i]-t[i-1] < T:
        # 稼働中にスイッチが押されたらオーバーラップ分を引く
        ans -= (t[i-1] + T - t[i])
print(ans)

Measured memory_bytes: 25200
#include <iostream>

using namespace std;

int main()	{
  long long n;
  cin >> n;
  long long a[n] = {0};
  long long max = -1;
  long long min = 1000000;
  for (int i = 0; i < n; i++)	{
    cin >> a[i];
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }
  cout << max - min << endl;
  return 0;
}

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

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    string ans = "Balanced";
    if (a + b > c + d)
        ans = "Left";
    if (a + b < c + d)
        ans = "Right";
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long ll;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};
bool isprime(int x){
  int i;
  if(x==2){
    return true;
  }

  if(x<2 ||x%2==0){
    return false;
  }
  i=3;
  while (i<=sqrt(x)) {
    if(x%i==0){
      return false;
    }
    i=i+2;
  }
  return true;
}
int main(int argc, char const *argv[]) {
  int n,a,cnt=0;
  cin>>n;
  REP(i,n){
    cin>>a;
    if(isprime(a)){
      cnt++;
    }
  }
  cout <<cnt << '\n';
  return 0;
}



Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,V,ans=0;
  cin>>n>>V;
  int a[1000],b[1000],c[1000],d[1000];
  for(int i=0;i<n;i++)cin>>a[i];
  for(int i=0;i<n;i++)cin>>b[i];
  for(int i=0;i<n;i++)cin>>c[i];
  for(int i=0;i<n;i++)cin>>d[i];
  vector<int> v;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      v.push_back(c[i]+d[j]);
  sort(v.begin(),v.end());
  
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
      int t=V-(a[i]+b[j]);
      int l=-1,m,r=v.size();
      while(r-l>1){
	m=(r+l)/2;
	if(v[m]>=t)r=m;
	else l=m;
      }
      int tr=r;
      t++;
      l=-1,r=v.size();
      while(r-l>1){
	m=(r+l)/2;
	if(v[m]>=t)r=m;
	else l=m;
      }
      ans+=r-tr;
    }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 11304
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

var hopes [2][2001][2001]int

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	k := getNextInt(scanner)

	cmap := map[string]int{
		"W": 0,
		"B": 1,
	}

	for i := 0; i < n; i++ {
		x := getNextInt(scanner) % (k << 1)
		y := getNextInt(scanner) % (k << 1)
		c := getNextString(scanner)
		hopes[cmap[c]][y+1][x+1]++
	}

	for i := 0; i < 2; i++ {
		for y := 0; y <= k<<1; y++ {
			for x := 0; x < k<<1; x++ {
				hopes[i][y][x+1] += hopes[i][y][x]
			}
		}
	}
	for i := 0; i < 2; i++ {
		for x := 0; x <= k<<1; x++ {
			for y := 0; y < k<<1; y++ {
				hopes[i][y+1][x] += hopes[i][y][x]
			}
		}
	}

	ans := 0
	var wb [2][3][3]int

	for y := 0; y < k; y++ {
		for x := 0; x < k; x++ {
			for i := 0; i < 2; i++ {
				wb[i][0][0] = count(i, 0, 0, y, x)
				wb[i][0][1] = count(i, 0, x, y, x+k)
				wb[i][0][2] = count(i, 0, x+k, y, k*2)
				wb[i][1][0] = count(i, y, 0, y+k, x)
				wb[i][1][1] = count(i, y, x, y+k, x+k)
				wb[i][1][2] = count(i, y, x+k, y+k, k*2)
				wb[i][2][0] = count(i, y+k, 0, k*2, x)
				wb[i][2][1] = count(i, y+k, x, k*2, x+k)
				wb[i][2][2] = count(i, y+k, x+k, k*2, k*2)
			}

			for i := 0; i < 2; i++ {
				done := 0
				for yy := 0; yy < 3; yy++ {
					for xx := 0; xx < 3; xx++ {
						done += wb[i^((yy+xx)%2)][yy][xx]
					}
				}

				if ans < done {
					ans = done
				}
			}
		}
	}

	fmt.Fprintln(writer, ans)
	writer.Flush()
}

func count(i, y1, x1, y2, x2 int) int {
	return hopes[i][y2][x2] - hopes[i][y1][x2] - hopes[i][y2][x1] + hopes[i][y1][x1]
}


Measured memory_bytes: 66944
S = input()
T = input()
s = 'T'
for i in range(len(S)-len(T)+1):
    for j in range(len(T)):
        if S[i+j] != T[j] and S[i+j] != '?':
            break
    
    else:
            s = S[:i]+T+S[i+len(T):]
            s = s.replace('?', 'a')
if s == 'T':
    print('UNRESTORABLE')
else:
    print(s)

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

typedef long long LL;
typedef pair<int, int> II;

const int N = 1000 + 10;
int n, c[N];

void Factorize(int n) {
    for (int i = 2; i * i <= n; ++i) if (n % i == 0) {
        while (n % i == 0) {
            n /= i;
            c[i]++;
        }
    }
    if (n > 1) c[n]++;
}

int main() {
    #ifdef LOCAL
        freopen("Data.inp", "r", stdin);
        freopen("Data.out", "w", stdout);
    #endif

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) Factorize(i);

    int ans = 1;
    for (int i = 1; i <= n; ++i) ans = ans * (c[i] + 1ll) % 1000000007;

    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define freop freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define st string
typedef long long ll;

void solve(){
     int a, b, c;
     cin >> a >> b >> c;
     int ans = 0;
     while(a > 0){
         a -= b;
         ans += c;
     }
     cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3608
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
for i,b in enumerate(B):
    if A[i]>=b:
        ans+=b
    else:
        ans+=A[i]
        b-=A[i]
        if A[i+1]>=b:
            ans+=b
            A[i+1]-=b
        else:
            ans+=A[i+1]
            A[i+1]=0
print(ans)

Measured memory_bytes: 81892
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first first
#define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

signed main(){
    int n, t;
    cin >> n >> t;
    int d[100010] = {};
    rep(i, 0, n){
        int l, r;
        cin >> l >> r;
        d[l]++;
        d[r]--;
    }
    int MAX = d[0];
    rep(i, 1, t + 1){
        d[i] += d[i - 1];
        MAX = max(MAX, d[i]);
    }
    o(MAX);
}

Measured memory_bytes: 3888
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N,A,B,C;
    cin>>N>>A>>B>>C;
    vint l(N);
    REP(i,N) cin>>l[i];

    int ans=1e18;
    REP(i,1<<2*N){
        int S=i;
        int lA=0,lB=0,lC=0;
        int cost=0;
        REP(j,N){
            if(S%4==0){
                if(lA>0) cost+=10;
                lA+=l[j];
            }
            if(S%4==1){
                if(lB>0) cost+=10;
                lB+=l[j];
            }
            if(S%4==2){
                if(lC>0) cost+=10;
                lC+=l[j];
            }
            S/=4;
        }
        if(lA>0 and lB>0 and lC>0){
            cost+=abs(lA-A)+abs(lB-B)+abs(lC-C);
            ans=min(ans,cost);
        }
        
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 256
#include<stdio.h>

int  main()
{
    int sec,h,m,s;
    scanf("%d",&sec);

    h = sec/3600;
    m = (sec-(h*3600))/60;
    s = sec - (h*3600) - m*60;

    printf("%d:%d:%d\n",h,m,s);
    return 0;
}



Measured memory_bytes: 2132
#include <iostream>
#include <algorithm>

void calc_profit(int n, int** ppfx);

int main()
{
    int n = 0;
    int* pfx;

    std::cin >> n;
    calc_profit(n, &pfx);
    delete[] pfx;
}

void calc_profit(int n, int** ppfx)
{
    int idx = 0;
    int maxv = -2000000000, minv = 0;

    *ppfx = new int[n];

    for (int i = 0; i < n; i++) {
        std::cin >> *(*ppfx + i);
    }

    minv = **ppfx;

    for (int i = 1; i < n; i++) {
        maxv = std::max(maxv, *(*ppfx + i) - minv);
        minv = std::min(minv, *(*ppfx + i));
    }
    std::cout << maxv << std::endl;
}

Measured memory_bytes: 3552
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;


class Solution{

public:
    int minRoads(const vector<vector<int>>& g){

        vector<bool> visited(g.size(), false);
        int res = 0;
        for(int i = 0; i < g.size(); i ++)
            if(!visited[i]){
                dfs(g, i, visited);
                res ++;
            }
        return res - 1;
    }

private:
    void dfs(const vector<vector<int>>& g, int v, vector<bool>& visited){

        visited[v] = true;
        for(int w: g[v])
            if(!visited[w]) dfs(g, w, visited);
    }
};

int main() {

    int N, M; scanf("%d%d", &N, &M);
    vector<vector<int>> g(N);

    int a, b;
    while(M --){
        scanf("%d%d", &a, &b);
        a --, b --;
        g[a].push_back(b), g[b].push_back(a);
    }
    printf("%d\n", Solution().minRoads(g));
    
    return 0;
}


Measured memory_bytes: 9196
using System;
class Program{
	const int mod=1000000007;
	static void Main(){
		int n=int.Parse(Console.ReadLine());
		long[] s=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
		long ans=0,h=1;
		long[] d=new long[n];
		for(int i=1;i<n;i++){
			d[i]=(d[i-1]+1*mi(i+1))%mod;
			h=((i+1)*h)%mod;
		}
		for(int i=0;i<n;i++){ans+=((((d[n-i-1]+d[i]+1)*h)%mod)*s[i])%mod;}
		Console.WriteLine(ans%mod);
	}
	static long mi(long a){
		long b=mod,u=1,v=0;
		while(b>0){
			long t=a/b;
			a-=t*b;a^=b;b^=a;a^=b;
			u-=t*v;u^=v;v^=u;u^=v;
		}
		u%=mod;
		if(u<0){u+=mod;}
		return u%mod;
	}
}

Measured memory_bytes: 21984
// package Contest#176;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int si = Integer.parseInt(st1.nextToken());
        int sj = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int ei = Integer.parseInt(st2.nextToken());
        int ej = Integer.parseInt(st2.nextToken());

        char[][] a = new char[h][w];
        
        for(int i=0; i<h; i++){
            String str = br.readLine();
            for(int j=0; j<w; j++){
                a[i][j] = str.charAt(j);
            }
        }

        bfs(a, si-1, sj-1, ei-1, ej-1, h, w);
        out.close();
    }

    static class Pair{
        int x; int y; int cst;
        Pair(int x, int y, int cst){
            this.x = x;
            this.y = y;
            this.cst = cst;
        }
    }
    
        static int[] walkH = {0,1,0,-1};
        static int[] walkW = {1,0,-1,0};
        static int[] warpH = {1,1,-1,-1,0,1,2,2,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1};
        static int[] warpW = {1,-1,1,-1,2,2,2,1,0,-1,-2,-2,-2,-2,-2,-1,0,1,2,2};

    static void bfs(char[][] a, int si, int sj, int ei, int ej, int h, int w){
        LinkedList<Pair> q = new LinkedList<>();
        q.add(new Pair(si, sj, 0));

        boolean[][] vis = new boolean[h][w];

        while(!q.isEmpty()){
            Pair rem = q.poll();

            if(rem.x == ei && rem.y == ej){
                System.out.println(rem.cst);
                return;
            }

            if(vis[rem.x][rem.y]){
                continue;
            }

            vis[rem.x][rem.y] = true;

            //todo

            for(int k=0; k<4; k++){
                int nx = walkH[k] + rem.x;
                int ny = walkW[k] + rem.y;
                if(nx>=0 && ny>=0 && nx<h && ny<w && a[nx][ny]=='.' && !vis[nx][ny]){
                    q.addFirst(new Pair(nx, ny, rem.cst));
                }
            }

            for(int k=0; k<warpH.length; k++){
                int nx = warpH[k] + rem.x;
                int ny = warpW[k] + rem.y;
                if(nx>=0 && ny>=0 && nx<h && ny<w && a[nx][ny]=='.' && !vis[nx][ny]){
                    q.addLast(new Pair(nx, ny, rem.cst+1));
                }
            }
        }

        System.out.println(-1);
    }
}

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

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))

using namespace std;

typedef long long ll;

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; }

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s,t; cin>>s>>t;
  
  rep(i, s.size()) {
   
   if(s==t) {
     cout<<"Yes";
     return 0;
   }
   
   s = s.back() + s.substr(0, s.size()-1);
  }
  
  cout<<"No";
  return 0;
}

Measured memory_bytes: 3668
#include <iostream>
#include <set>

int main() {
    int q;
    std::cin >> q;

    std::multiset<int> S;
    for (int i = 0; i < q; i++) {
        int op;
        std::cin >> op;
        if (op == 0) {
            int x;
            std::cin >> x;
            S.insert(x);
            std::cout << S.size() << std::endl;
        } else if (op == 1) {
            int x;
            std::cin >> x;
            std::cout << S.count(x) << std::endl;
        } else if (op == 2) {
            int x;
            std::cin >> x;
            S.erase(x);
        } else if (op == 3) {
            int L, R;
            std::cin >> L >> R;
            auto begin = S.lower_bound(L);
            auto end = S.upper_bound(R);
            for (auto it = begin; it != end; it++) {
                std::cout << *it << std::endl;
            }
        }
    }
}



Measured memory_bytes: 12292
#include <iostream>
#include <cmath>

using namespace std;

int main(void){
    int x1,x2,y1,y2;

    cin >> x1 >> y1 >> x2 >> y2;

    int dx = x1-x2;
    int dy = y1-y2;

    cout << x2 + dy <<" "<< y2 - dx <<" "<< x1 + dy <<" "<< y1 - dx << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll a,b,c;
    cin >> a >> b >> c;
    ll judge=a*a+b*b+c*c-2*a*b-2*b*c-2*c*a;
    if(judge>0&&c>a+b){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#define N 1005
using namespace std;
typedef long long ll;
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",n/3);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <climits>
#include <iomanip>
#include <deque>

using namespace std;

int main()
{
  int64_t N;
  int64_t A, B;

  cin >> N >> A >> B;

  cout << (N / (A + B)) * A + min(A, N % (A + B));

  return 0;
}


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

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

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

struct Edge {
	Edge(){}
	Edge(int src, int dst, int cost): src(src), dst(dst), cost(cost){}
	bool operator < (const Edge &rhs) const { return cost > rhs.cost; }
	bool operator > (const Edge &rhs) const { return cost < rhs.cost; }
	int src, dst, cost;
};

const int log_n = 20;
int dep[100010];
int par[log_n + 1][100010], cst[log_n + 1][100010];

int buildTree(const vector<vector<Edge>> &g, int v, int p, int d)
{
	par[0][v] = p;
	dep[v] = d;
	for (auto e : g[v]){
		if (e.dst != p){
			cst[0][e.dst] = e.cost;
			buildTree(g, e.dst, v, d + 1);
		}
	}
}

int lca(int u, int v)
{
	if (dep[u] > dep[v]) swap(u, v);
	int res = 1 << 28;
	for (int i = 0; i < log_n; i++){
		if (((dep[v] - dep[u]) >> i) & 1){
			res = min(res, cst[i][v]);
			v = par[i][v];
		}
	}
	if (u == v) return res;
	for (int i = log_n - 1; i >= 0; i--){
		if (par[i][u] != par[i][v]){
			res = min(res, cst[i][u]);
			res = min(res, cst[i][v]);
			u = par[i][u];
			v = par[i][v];
		}
	}
	return min({res, cst[0][u], cst[0][v]});
}

int main()
{
	int n, m, k, q;
	cin >> n >> m >> k >> q;
	
	vector<vector<Edge>> g(n);
	rep(i, m){
		int a, b, l;
		cin >> a >> b >> l, a--, b--;
		g[a].emplace_back(a, b, l);
		g[b].emplace_back(b, a, l);
	}

	vector<int> fs(k);
	rep(i, k) cin >> fs[i], fs[i]--;

	vector<int> dist = [&](){
		vector<int> d(n, 1 << 28);
		priority_queue<Edge> pq;
		for (int f : fs){
			d[f] = 0;
			pq.emplace(f, -1, 0);
		}
		while (pq.size()){
			auto c = pq.top(); pq.pop();
			if (d[c.src] < c.cost) continue;
			for (auto e : g[c.src]){
				if (d[e.dst] > c.cost + e.cost){
					d[e.dst] = c.cost + e.cost;
					pq.emplace(e.dst, -1, c.cost + e.cost);
				}
			}
		}
		return d;
	}();
	
	g = [&](){
		vector<vector<Edge>> t(n);
		priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
		rep(i, n) for (auto e : g[i]){
			pq.emplace(e.src, e.dst, min(dist[e.src], dist[e.dst]));
		}
		UnionFind uf(n);
		while (pq.size()){
			auto e = pq.top(); pq.pop();
			if (uf.unite(e.src, e.dst)){
				t[e.src].emplace_back(e.src, e.dst, e.cost);
				t[e.dst].emplace_back(e.dst, e.src, e.cost);
			}
		}
		return t;
	}();

	buildTree(g, 0, -1, 0);

	rep(i, log_n) rep(v, n){
		if (par[i][v] < 0) par[i + 1][v] = -1;
		else {
			par[i + 1][v] = par[i][par[i][v]];
			cst[i + 1][v] = min(cst[i][v], cst[i][par[i][v]]);
		}
	}
	
	/*
	rep(i, n) for (auto e : g[i]){
		printf("%d -> %d, %d\n", e.src + 1, e.dst + 1, e.cost);
	}
	*/

	rep(i, q){
		int s, t;
		cin >> s >> t, s--, t--;
		cout << lca(s, t) << endl;
	}
}

Measured memory_bytes: 30268
def main():
    # a = input()
    # n = int(input())
    # a = list(map(int, input().split()))
    l, r, d = map(int, input().split())

    ret = 0
    for i in range(l, r+1):
        if i % d == 0:
            ret += 1
    print(ret)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9096
#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	string s;
	cin >> n;
	cin >> s;
	vector<vector<int>> acc;
	for(char c : {'R', 'G', 'B'}){
		vector<int> cur;
		int sum = 0;
		for(int i = 0; i < n; i++){
			sum += s[i] == c;
			cur.push_back(sum);
		}
		acc.push_back(cur);
	}
	long long ans = 0;
	for(int i = 1; i < n - 1; i++){
		int ie = 0;
		for(char e : {'R', 'G', 'B'}){
			int ib = 0;
			for(char d : {'R', 'G', 'B'}){
				if(e != d && e != s[i] && d != s[i]){
					ans += acc[ie][i - 1] * (acc[ib][n - 1] - acc[ib][i]);
				}
				ib++;
			}
			ie++;
		}
		for(int d = 1; i - d >= 0 && i + d < n; d++){
			ans -= s[i - d] != s[i] && s[i + d] != s[i] && s[i - d] != s[i + d];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

struct UnionFind {
    vector<ll> parent;

    UnionFind(ll n) {
        parent.resize(n, -1);
    }

    ll find(ll x) {
        // 自身が根っこの場合
        if (parent[x] == -1) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    void unite(ll x, ll y) {
        ll root_x = find(x);
        ll root_y = find(y);
        // 同じ素集合にいたら何もしない
        if (root_x == root_y) return;
        parent[root_x] = root_y;
    }
};

int main() {
    ll n, m; cin >> n >> m;
    vector<vector<ll>> G(n);
    ll a, b;

    UnionFind uf(n);

    for (int i = 0; i < m; ++i) {
        cin >> a >> b; a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
        uf.unite(a, b);
    }

    map<ll, ll> mp;
    for (int i = 0; i < n; ++i) {
        ll parent = uf.find(i);
        if (mp.count(parent) == 0) mp[parent] = 0;
        mp[parent]++;
    }

    ll ans = 0;
    for (auto i: mp) {
        ans = max(ans, i.second);
    }
    cout << ans << endl;
}

Measured memory_bytes: 22004
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func intMin(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func main() {
	sc.Split(bufio.ScanWords)

	N, T := scanInt(), scanInt()
	t := make([]int, N)
	for i := range t {
		t[i] = scanInt()
	}

	ans := T
	for i := 1; i < N; i++ {
		ans += intMin(t[i]-t[i-1], T)
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5844
package main

import (
	"fmt"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	ans := 0
	for i := k; i <= n + 1; i++ {
		// [n - i + 1, ... n]
		smax := i * (n - i + 1 + n) / 2
		// [0, ... i - 1]
		smin := i * (i - 1) / 2
		// fmt.Println(smax, smin)
		ans += smax - smin + 1
		ans %= int(1e9) + 7
	}

	fmt.Println(ans);
}


Measured memory_bytes: 1768
#include <bits/stdc++.h>
#define ri register
#define int long long
#define E (n+1)
using namespace std; const int N=200010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
int n,A;
signed main()
{
    n=read(), A=read();
    n%=500;
    if(A>=n) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 3576
using System;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] In = Console.ReadLine().Split(' ');
            int a = int.Parse(In[0]);
            int p = int.Parse(In[1]);
            Console.WriteLine((3 * a + p) / 2);
        }
    }
}


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

int main(){
    int n,v[25],c,ans=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }for(int i=0;i<n;i++){
        cin>>c;
        v[i]-=c;
        if(v[i]>0) ans+=v[i];
    }
    cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <vector>
#include <string>
//#include <algorithm>

using namespace std;

int main(){

	string in;
	int cnt[26];

	for (int i = 0; i < 26; i++){
		cnt[i] = 0;
	}

	while (1){
		getline(cin, in);
		if (in.empty()) break;

		for (int i = 0; i < in.size(); i++){
			for (int j = 0; j < 26; j++){
				if (in[i] == 'A' + j || in[i] == 'a' + j){
					cnt[j]++;
				}
			}
		}
	}

	for (int i = 0; i < 26; i++){
		cout << (char)('a' + i) << " : " << cnt[i] << endl;
	}


	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <string>
std::string S;
int x;
int main()
{
    std::cin >> S;
    x = std::stoi(S);
    if ((x / 10) % 111 == 0 || (x % 1000) % 111 == 0)
        std::cout << "Yes" << std::endl;
    else {
        std::cout << "No" << std::endl;
    }
    return 0;
}


Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        n: usize,
        m: usize,
        q: usize,
        abcd: [(Usize1, Usize1, usize, i64); q],
    }
    // abcd.sort_by_key(|x| -x.3);
    let mut s = vec![0; n];
    fn next(a: &mut [usize], m: usize) -> bool {
        let n = a.len();
        if n == 1 {
            if a[0] + 1 == m {
                false
            } else {
                a[0] += 1;
                true
            }
        } else {
            if a[n - 1] + 1 == m {
                if next(&mut a[0..n - 1], m) {
                    a[n - 1] = a[n - 2];
                    true
                } else {
                    false
                }
            } else {
                a[n - 1] += 1;
                true
            }
        }
    }
    let mut res = 0;
    loop {
        let mut r = 0;
        for &(a, b, c, d) in &abcd {
            if s[b] - s[a] == c {
                r += d;
            }
        }
        res = std::cmp::max(res, r);
        if !next(&mut s, m) {
            break;
        }
    }

    println!("{}", res);
}


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

using namespace std;

int main()
{
    int h,n,sum=0,cnt=0;
    cin>>h>>n;
    while(sum<=h)
    {
        sum=sum+n;
        cnt++;
        if(sum>=h)
            break;
    }
    cout<<cnt;
    cout<<"\n";
    return 0;

}


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

#define mod 1000000007

int main(){
    int64_t n;
    cin >> n;
    int64_t count[1010]={};
    int64_t ans = 1;
    for(int64_t i=2; i<=n; i++){
        int64_t tmp = i;
        for(int64_t j=2; j<=n; j++){
            while(tmp%j==0){
                count[j]++;
                tmp/=j;
            }
        }
    }
    for(int64_t i=2; i<=n; i++){
        ans = ans * (count[i]+1) % mod;
    }
    cout << ans%mod << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct _I { _I() {cin.tie(0);ios::sync_with_stdio(false);}} __I;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
template<class T> void cout_h(const vector<T>& c, int n=INT_MAX)
{ rep(i, min(n, (int)c.size())) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
#define D1(a) cout<<#a<<":"<<a<<"\n"
#define D2(a,b) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<endl 
#define D3(a,b,c) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl 
#define INF 1000000000

int main()
{
    int H, N; cin >> H >> N;
    vi dp(H+1, INF);
    dp[0] = 0;
    rep(i, N) {
        int A, B; cin >> A >> B;
        rep(j, H) chmin(dp[min(H, j + A)], dp[j] + B);
    }
    cout << dp.back() << endl;
}


Measured memory_bytes: 256
import java.lang.Math.abs
import java.lang.Math.min
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)

    val n = sc.nextInt()

    var array = ArrayList<Long>()

    for (i in 0..n-1) {
        array.add(sc.nextInt().toLong())
    }

    var minv = solveC(array)

    println(minv)
}

fun solveC(array: ArrayList<Long>): Long {
    val n = array.size
    val sum = array.sum()
    var minv = Long.MAX_VALUE
    var x = 0L
    for (i in 0..n - 2) {
        x += array[i]
        minv = min(minv, abs(sum - 2 * x))
    }
    return minv
}

Measured memory_bytes: 77028
#include<stdio.h>

int main(){

    char s[3];

    scanf("%s",s);

    if(s[0]=='S'&&s[1]=='U'&&s[2]=='N')
    {
        printf("7");
    }
    if(s[0]=='M'&&s[1]=='O'&&s[2]=='N')
    {printf("6");
    }
    if(s[0]=='T'&&s[1]=='U'&&s[2]=='E')
    {printf("5");
    }
    if(s[0]=='W'&&s[1]=='E'&&s[2]=='D'){
        printf("4");
    }
    if(s[0]=='T'&&s[1]=='H'&&s[2]=='U')
    {printf("3");
    }
    if(s[0]=='F'&&s[1]=='R'&&s[2]=='I')
    {printf("2");
    }
    if(s[0]=='S'&&s[1]=='A'&&s[2]=='T'){
        printf("1");
    }


    return 0;
}

Measured memory_bytes: 1616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,arr[200005],ans=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    for(int i=1;i<n;i++)
    {
        if(arr[i]<arr[i-1])
        {
            ans+=(arr[i-1]-arr[i]);
            arr[i]=arr[i-1];
        }
    }
    cout<<ans<<'\n';
    return 0;
}

Measured memory_bytes: 5128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        long k = sc.nextLong();
        
        char ans = '1';
        long oneIdx = 0;
        for(char str : s) {
            if(str != '1') {
                ans = str;
                break;
            }
            oneIdx++;
        }
        
        if(k <= oneIdx) ans = '1';
        System.out.println(ans);
    }
}


Measured memory_bytes: 23252
# -*- coding: utf-8 -*-

N = int(input())
aN = list(map(int, input().split()))

aN2 = sorted(aN)

if aN2[N//2-1] == aN2[N//2]:
	for i in range(N):
		print(aN2[N//2])
else:
	for i in range(N):
		if aN[i] < aN2[N//2]:
			print(aN2[N//2])
		else:
			print(aN2[N//2-1])


Measured memory_bytes: 25620
#include <iostream>
#include <cmath>
#include <string>

int main(int argc, char *argv[])
{
    int a, b, c;
    std::cin >> a >> b >> c;
    int count = 0;
    for(int i = a; i <= b ; ++i){
        if(c%i == 0)++count;
    }
    std::cout << count << std::endl;
    return 0;
}

Measured memory_bytes: 3068
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
//rows indicate maximum weight - row 0 means 0 max weight...
//column j indicates maximum possible value for items [0,j]
vvi max_value_for_weight;
vi weights, values;

ll find_max_value(int last_item_index, ll max_weight)
{
	if (max_value_for_weight[max_weight][last_item_index] > -1)
		return max_value_for_weight[max_weight][last_item_index];
	
	ll value_without_item = find_max_value(last_item_index - 1, max_weight);
	if (weights[last_item_index] > max_weight) //Item doesn't fit in the knapsack
	{
		max_value_for_weight[max_weight][last_item_index] = value_without_item;
		return value_without_item;
	}
	ll value_with_item = find_max_value(last_item_index - 1, max_weight - weights[last_item_index])+values[last_item_index];
	max_value_for_weight[max_weight][last_item_index] = max(value_without_item, value_with_item);
	return max(value_without_item, value_with_item);
}

int main()
{
	ios::sync_with_stdio(false);
	int no_items, max_weight; cin >> no_items >> max_weight;
	weights = vi(no_items); values = vi(no_items);
	for (size_t i = 0; i < no_items; i++)
	{
		cin >> weights[i] >> values[i];
	}
	max_value_for_weight = vvi(max_weight+1);
	for (size_t i = 0; i <= max_weight; i++)
	{
		max_value_for_weight[i] = vi(no_items);
		for (size_t j = 0; j < no_items; j++)
		{
			if (i == 0)
				max_value_for_weight[i][j] = 0;
			else if (j == 0)
			{
				if (i >= weights[0])
					max_value_for_weight[i][0] = values[0];
				else
					max_value_for_weight[i][0] = 0;
			}
			else
				max_value_for_weight[i][j] = -1;
		}
	}
	cout << find_max_value(no_items-1, max_weight);
	return 0;
}

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

using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define inf 1000000100

int main()
{
    string a, b;
    cin >> a >> b;

    if(a.size() > b.size())
    {
        cout << "GREATER" << endl;
    }
    else if (a.size() < b.size())
    {
        cout << "LESS" << endl;
    }
    else
    {
        if(a > b)
        {
            cout << "GREATER" << endl;
        }
        else if (a < b)
        {
            cout << "LESS" << endl;
        }
        else
        {
            cout << "EQUAL" << endl;
        }
    }

}

Measured memory_bytes: 256
MOD = 10 ** 9 + 7
# fac = [1] * 10 ** 5
# for i in range(len(fac) - 1):
#     fac[i + 1] = fac[i] * (i + 1)
#     fac[i + 1] %= MOD


# def comb(n, k):
#     return fac[n] * pow(fac[k], MOD - 2, MOD) * pow(fac[n - k], MOD - 2, MOD) % MOD


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n - 1):
    ans += (n - i + 1) * pow(2, n - 2, MOD) * a[i] % MOD
ans += pow(2, n - 1, MOD) * a[n - 1]
print(ans * pow(2, n, MOD) % MOD)

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

int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  ll tmp = min(a, k);
  a  -= tmp;
  k  -= tmp;
  tmp = min(b, k);
  b  -= tmp;
  cout << a << " " << b << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int h,w;
  cin>>h>>w;
  vector<int> a,b;
  int ans=0;
  rep(i,h){
    rep(j,w){
      char c;
      cin>>c;
      if(c=='B'){
	a.push_back(i+j);
	b.push_back(i+w-j-1);
	//cout<<i+j<<endl;
      }
    }
  }
  sort(a.begin(),a.end() );
  ans=max(ans,a[a.size()-1]-a[0]);
  sort(b.begin(),b.end() );
  ans=max(ans,b[b.size()-1]-b[0]);
  cout<<ans<<endl;

  return 0;
}



Measured memory_bytes: 3244
N, M = map(int, input().split())
XYZ = [tuple(map(int, input().split())) for _ in range(N)]


def score(x, y, z, bit):
    s = 0
    s += x if (bit >> 0) & 1 else -x
    s += y if (bit >> 1) & 1 else -y
    s += z if (bit >> 2) & 1 else -z
    return s


ans = 0
for i in range(2 ** 3):
    XYZ.sort(key=lambda xyz: score(xyz[0], xyz[1], xyz[2], i), reverse=True)
    x_sum, y_xum, z_sum = 0, 0, 0
    for x, y, z in XYZ[:M]:
        x_sum += x
        y_xum += y
        z_sum += z
    ans = max(ans, abs(x_sum) + abs(y_xum) + abs(z_sum))

print(ans)


Measured memory_bytes: 3300
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	N := ReadInt()
	A := ReadInts(N)
	left := make([]int, N)
	left[0] = -1
	for i := 1; i < N; i++ {
		left[i] = Max(left[i-1], A[i-1])
	}
	right := make([]int, N)
	right[N-1] = -1
	for i := N - 2; i >= 0; i-- {
		right[i] = Max(right[i+1], A[i+1])
	}
	for i := 0; i < N; i++ {
		fmt.Println(Max(left[i], right[i]))
	}
}

func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 9108
#include <stdio.h>
int main()
{
   int x,sum = 0, n;
   scanf("%d", &x);
   n = x;
   while (x!= 0)
    {
        sum += x%10;
        x /=10;
    }
    if ((n%sum) == 0)
    printf("Yes\n");
    else
    printf("No\n");
   return 0;
}

Measured memory_bytes: 128
N=int(input())

A =  list(map(int, input().split()))

B =   list(map(int, input().split()))

C =  list(map(int, input().split()))

ans = 0
ans += sum(B)

# print(ans)
for i in range(1,N):
    if A[i] - A[i-1] == 1:
        # print(i)
        ans += C[A[i-1]-1]

print(ans)
    

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
	int a,b,c,k,i,j;
	int max;
	scanf("%d %d %d",&a,&b,&c);
	scanf("%d",&k);
	if(a>b&&a>c)max=a;
	else if(b>c)max=b;
	else max=c;
	j=max;
	for(i=0;i<k;i++)max*=2;
	printf("%d\n",a+b+c+max-j);
	return 0;	
}

Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#define IL inline
#define N 200010
#define S 524291
#define REP(a,b,c) for(a=b;a<=c;a++)
#define PER(a,b,c) for(a=b;a>=c;a--)
using namespace std;
const int mod=924844033;
int head[N],lt[N<<1],nt[N<<1],ap=1,q[N],fa[N],sz[N];
int n,L,R[S],G[S],F[S],inv[N];
IL int rd(){
	int res=0;char c;while((c=getchar())<'0'||c>'9');
	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();return res;
}
IL int qpow(int a,int b){
	int res=1;while(b){if(b&1)res=1LL*res*a%mod;a=1LL*a*a%mod,b>>=1;}return res;
}
IL void link(int a,int b){
	lt[++ap]=b,nt[ap]=head[a],head[a]=ap;
	lt[++ap]=a,nt[ap]=head[b],head[b]=ap;
}
IL void bfs(){
	int fr=1,tp=1,u,x,v;q[1]=1;
	while(fr<=tp){
		for(x=head[u=q[fr++]];x;x=nt[x])
			if((v=lt[x])!=fa[u])q[++tp]=v,fa[v]=u;
	}
	for(fr--;fr;fr--,G[n-sz[u]]--)
		for(x=head[u=q[fr]],sz[u]++;x;x=nt[x])
			if((v=lt[x])!=fa[u])sz[u]+=sz[v],G[sz[v]]--;
	G[n]+=n;
	REP(u,0,n)if(G[u]<0)G[u]+=mod;
}
IL void NTT(int *a,int f){
	int i,j,k,gn,g,x,y;
	REP(i,0,n)if(R[i]>i)swap(a[i],a[R[i]]);
	for(i=1;i<n;i<<=1){
		gn=qpow(5,(mod-1)/(i<<1));
		for(j=0;j<n;j+=i<<1){
			g=1;
			for(k=0;k<i;k++,g=1LL*g*gn%mod){
				x=a[j+k],y=1LL*g*a[j+k+i]%mod;
				a[j+k]=(x+y)%mod,a[j+k+i]=(x-y+mod)%mod;
			}
		}
	}
	if(f==-1){
		reverse(a+1,a+n);g=qpow(n,mod-2);
		REP(i,0,n-1)a[i]=1LL*a[i]*g%mod;
	}
}
int main(){
  n=rd();int i,j=1;REP(i,2,n)link(rd(),rd());bfs();
	REP(i,1,n)G[i]=1LL*G[i]*(j=1LL*j*i%mod)%mod;
	inv[n]=j=qpow(j,mod-2);PER(i,n,1)inv[i-1]=F[n-i+1]=j=1LL*j*i%mod;
	j=n;
	for(n=1;n<=j<<1;n<<=1)L++;
	REP(i,0,n-1)R[i]=(R[i>>1]>>1|(i&1)<<(L-1));
	NTT(F,1),NTT(G,1);
	REP(i,0,n-1)F[i]=1LL*F[i]*G[i]%mod;
	NTT(F,-1);
	REP(i,1,j)printf("%lld\n",1LL*F[j+i]*inv[i]%mod);
  return 0;
}

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

vector<pair<int, int> > v;
int a[101];

int main(){
  int n, s;
  while(true){
    scanf("%d,%d", &n, &s);
    if(n==0 && s==0)break;
    v.push_back(make_pair(s, n));
  }
  sort(v.begin(), v.end(), greater<pair<int, int> >());
  int t=1;
  a[v[0].second]=t;
  for(int i=1; i<v.size(); i++){
    if(v[i].first!=v[i-1].first)t++;
    a[v[i].second]=t;
  }
  while(cin>>n){
    cout<<a[n]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1248
n=int(input())
max=-1
a=[0]*n
a[0]=1
s =list()
for _ in range(n):
    s.append(input().split())
s.sort()
for i in range(1,n):
    if(s[i-1]==s[i]):
        a[i]=a[i-1]+1
    else:
        a[i]=1
        if max<a[i-1]:
            max=a[i-1]
if max<a[n-1]:
    max=a[n-1]
for i in range(n):
    if(max==a[i]):
        print(*s[i])

Measured memory_bytes: 59540