akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int recursive(int *a,int n,int *dp){
    dp[1]=0;
    dp[2]=abs(a[2]-a[1]);
    for(int i=3;i<=n;i++){
        dp[i]=min(abs(a[i]-a[i-1])+dp[i-1],abs(a[i]-a[i-2])+dp[i-2]);
    }
    return dp[n];
}
int main(){
  int n;
  cin>>n;
  int *a=new int[n+1];
  int *dp=new int[n+1];
  for(int i=1;i<=n;i++) {
      cin>>a[i];
  }
  
  cout<<recursive(a,n,dp)<<endl;
  //cout<<endl;
}

Measured memory_bytes: 1024
a,b,c,d=gets.split.map(&:to_i)
n=gets.to_i
result=0
half=[a*2,b].min
one=[a*4,b*2,c].min
two=[a*8,b*4,c*2,d].min
result+=two*(n/2)
result+=one*(n%2)
             
             
p result

Measured memory_bytes: 3836
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h1 = sc.nextInt();
        int m1 = sc.nextInt();
        int h2 = sc.nextInt();
        int m2 = sc.nextInt();
        int k = sc.nextInt();
        int t1 = h1 * 60 + m1;
        int t2 = h2 * 60 + m2;
        System.out.println(t2-t1-k);

    }


}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

/*
void test_case()
{
  int k;
  cin >> k;
  ull p = 0;
  int i = 1;
  while (true)
  {
    p += 7;

    if (p % k == 0)
    {
      break;
    }
    else
    {
      i++;
      p *= 10;
    }
  }
  cout << i << endl;
}
*/
void test_case()
{
  int n;
  ll d;
  cin >> n >> d;
  int c = 0;
  while (n--)
  {
    ll x, y;
    cin >> x >> y;
    if (x * x + y * y <= d * d)
    {
      c++;
    }
  }
  cout << c << endl;
}

int main(void)
{
  ios::sync_with_stdio(false);
  int t;
  t = 1;
  // cin >> t;
  while (t--)
  {
    test_case();
  }
  return 0;
}


Measured memory_bytes: 3612
#![allow(unused_imports)]

use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::{i32, i64, i128, u32, u64, u128, f64};
use std::io::{stdout, Write, BufWriter};
use std::mem::{swap};
use proconio::{input, marker::{Isize1, Usize1, Bytes, Chars}};

#[proconio::fastout]
fn main() {
    input!(
        n: usize,
        x: i64,
        m: i64,
    );
    let mut hist = HashSet::new();
    let mut mods = Vec::with_capacity(m as usize);
    let mut looped = false;
    let mut i = 1;
    mods.push(x);
    while i < n {
        let r = (mods.last().unwrap()).pow(2) % m;
        if hist.contains(&r) {
            looped = true;
            mods.push(r);
            break;
        }
        else {
            hist.insert(r);
            mods.push(r);
        }
        i += 1;
    }
    if !looped { println!("{}", mods.into_iter().sum::<i64>()); }
    else {
        let start = mods.pop().unwrap();
        let startind = mods.iter().copied().position(|m| m == start).unwrap();
        let looplen = mods.len() - startind;
        let loopsum: i64 = mods[startind..].into_iter().sum();
        let remlen = n - startind;
        let ans = mods[..startind].into_iter().sum::<i64>();
        if remlen % looplen == 0 {
            println!("{}", ans + loopsum * ((remlen / looplen) as i64));
        } else {
            println!("{}", ans + loopsum * ((remlen / looplen) as i64) + mods[startind..(startind + (remlen % looplen))].into_iter().sum::<i64>());

        }
    }
}


Measured memory_bytes: 3176
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {

    int a; cin >>a;
    char op; cin >>op;
    int b; cin >>b;

    if (op == '+') {
        cout << a+b << endl; 
    } else {
        cout << a-b << endl;
    } 
    
    return 0;
}




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

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<string> s(H);
    for (int i = 0; i < H; i++) cin >> s[i];

    vector< vector<int> > U(H, vector<int>(W, 0));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (s[i][j] == '#') continue;
            if (i > 0) U[i][j] = U[i - 1][j] + 1;
            else U[i][j] = 1;
        }
    }

    vector< vector<int> > L(H, vector<int>(W, 0));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (s[i][j] == '#') continue;
            if (j > 0) L[i][j] = L[i][j - 1] + 1;
            else L[i][j] = 1;
        }
    }

    vector< vector<int> > D(H, vector<int>(W, 0));
    for (int i = H - 1; i >= 0; i--) {
        for (int j = W - 1; j >= 0; j--) {
            if (s[i][j] == '#') continue;
            if (i < H - 1) D[i][j] = D[i + 1][j] + 1;
            else D[i][j] = 1;
        }
    }

    vector< vector<int> > R(H, vector<int>(W, 0));
    for (int i = H - 1; i >= 0; i--) {
        for (int j = W - 1; j >= 0; j--) {
            if (s[i][j] == '#') continue;
            if (j < W - 1) R[i][j] = R[i][j + 1] + 1;
            else R[i][j] = 1;
        }
    }

    int ans = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            ans = max(ans, U[i][j] + D[i][j] + R[i][j] + L[i][j] - (s[i][j] == '.') * 3);
            //if (i == 1 && j == 1) cerr << U[i][j] + D[i][j] + R[i][j] + L[i][j] - (s[i][j] == '.') * 3 << endl;
        }
    }

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

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

int main() {
  int n;
  cin >> n;
  int x = n;
  int fx = 0;

  while (n > 0) {
    fx += n % 10;
    n /= 10;
  }

  if (x % fx == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
n = int(input())
dp = [float('Inf')] * (100000 + 1)
dp[0] = 0
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    cnt = 1
    for j in range(0, 7):
        cnt *= 6 
        if i - cnt >= 0:
            dp[i] = min(dp[i], dp[i - cnt] + 1)
    cnt = 1
    for j in range(0, 6):
        cnt *= 9
        if i - cnt >= 0:
            dp[i] = min(dp[i], dp[i - cnt] + 1)
print(dp[n])

Measured memory_bytes: 3828
#include<iostream>
using std::cout;
using std::cin;
using std::endl;

int main()
{
  int64_t a, b, n;
  cin >> a >> b >> n;

  int64_t n_1 = (n / b) * b;
//  int64_t n_diff = n - n_1;
  
  int64_t max = 0;
/*
  for (int64_t x = 0; x <= n_1; x += b)
  {
    int64_t x_floor = (x - 1) / b;
    int64_t ax_floor = (a * (x - 1)) / b;
    int64_t diff = ax_floor - a * x_floor;
    if (diff > max)
    {
      max = diff;
    }
  }
  */
  int64_t diff_a = (a * (n_1 - 1)) / b - a * ((n_1 - 1) / b);
  int64_t diff_b = (a * n) / b - a * (n / b);
  if (diff_a > diff_b) cout << diff_a << endl;
  else cout << diff_b << endl;
  
//  cout << max << endl;
  return 0;
}


Measured memory_bytes: 3624
import Control.Monad
main = do
  n <- readLn
  k <- map (map read . words) <$> replicateM n getLine
  putStrLn .show $ solved k

cho a = a2 - a1 + 1
  where
    [a1, a2] = a

solved:: [[Int]] -> Int
solved n = foldl (+) 0 $ map cho n

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

int n,a,b;
double v[60];

ll comb[60][60];

ll Comb(int n,int k){
    if(k<0||n<k)return 0;
    if(n==0)return 1;
    if(comb[n][k])return comb[n][k];
    if(k<n)comb[n][k]+=Comb(n-1,k);
    if(k)comb[n][k]+=Comb(n-1,k-1);
    return comb[n][k];
}

int main(){
    cin>>n>>a>>b;
    rep(i,n)cin>>v[i];
    sort(v,v+n,greater<double>());
    double ave=0.0;
    rep(i,a)ave+=v[i];
    printf("%.10f\n",ave/a);
    int x=a-1,j=a-1;
    while(x&&v[x-1]==v[x])x--;
    while(j+1<n&&v[j]==v[j+1])j++;
    if(x){
        cout<<Comb(j-x+1,a-x)<<endl;
        return 0;
    }
    ll ans=0;
    for(int i=a;i<=b;i++)ans+=Comb(j+1,i);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;

int N;
vector<pair<int,int>> v[100000];
queue<pair<int,pair<int,int>>> q;
int l[100000];

int main(){
    cin >> N;
    for(int i=0;i<N-1;i++){
        int a,b,c;
        cin >> a >> b >> c;
        v[a-1].push_back(make_pair(b-1,c%2));
        v[b-1].push_back(make_pair(a-1,c%2));
    }
    for(int i=0;i<N;i++) l[i] = -1;
    l[0] = 0;
    for(int i=0;i<v[0].size();i++) q.push(make_pair(0,v[0][i]));
    while(!q.empty()){
        int a = q.front().first;
        int b = q.front().second.first;
        int c = q.front().second.second;
        q.pop();
        if(l[b] != -1) continue;
        if(c == 0) l[b] = l[a];
        else l[b] = 1 - l[a];
        for(int i=0;i<v[b].size();i++) q.push(make_pair(b,v[b][i]));
    }
    for(int i=0;i<N;i++) cout << l[i] << endl;
    return 0;
}

Measured memory_bytes: 6784
n = int(input())
a = list(map(int, input().split()))

s = 0
for i in range(n):
    s += a[i]

tr = 0
for i in range(n):
    tr += a[i] ** 2

a2 = s ** 2 - tr
a = a2 // 2
a %= 10 ** 9 + 7

print(a)

Measured memory_bytes: 105016
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
struct activity{

  int A,B,C;
};
ll vacation(vector<activity> arr,ll n){
  ll dp[n+1][3]={0};
  dp[1][0]=arr[1].A;
  dp[1][1]=arr[1].B;
  dp[1][2]=arr[1].C;
  for(ll i=2;i<=n;i++){
    dp[i][0]=arr[i].A+max(dp[i-1][1],dp[i-1][2]);
    dp[i][1]=arr[i].B+max(dp[i-1][0],dp[i-1][2]);
    dp[i][2]=arr[i].C+max(dp[i-1][1],dp[i-1][0]);
  }
  return max(dp[n][0],max(dp[n][1],dp[n][2]));

}
int main(){
    ll n;
    cin>>n;
    vector<activity> arr(n+1);
    for(ll i=1;i<=n;i++){
      cin>>arr[i].A;
      cin>>arr[i].B;
      cin>>arr[i].C;
    }
    cout<<vacation(arr,n)<<endl;


    


}

Measured memory_bytes: 7940
import math


hour_hand_speed = (2 * math.pi) / (12 * 60)
minute_hand_speed = (2 * math.pi) / 60

hour_hand, minute_hand, hour, minute = list(
    map(int, input().split())
)

elapsed_time = 60 * hour + minute

hour_hand_angle = elapsed_time * hour_hand_speed
minute_hand_angle = minute * minute_hand_speed

angle_btw_hour_minute = abs(hour_hand_angle - minute_hand_angle)

distance = math.sqrt(
    hour_hand**2 + minute_hand**2 - (2 * hour_hand * minute_hand * math.cos(angle_btw_hour_minute))
)

print(distance)


Measured memory_bytes: 9424
using System;
using System.Linq;
using System.Collections.Generic;

public class Program{
    public static void Main(){
        var input = Console.ReadLine().Split().ToArray();
        string a = input[0], b = input[1];
        if(a=="H" && b=="H") Console.WriteLine("H");
        else if(a=="H" && b=="D") Console.WriteLine("D");
        else if(a=="D" && b=="H") Console.WriteLine("D");
        else if(a=="D" && b=="D") Console.WriteLine("H");
    }
}


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

int main(){
  string s,t;
  cin >> s >>t;
  if((s.at(0) == t.at(2)) && (s.at(1) == t.at(1)) && (s.at(2) == t.at(0)))cout << "YES" << endl;
  else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <numeric>
//#include<bits/stdc++.h>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
const ll mod = 1e9 + 7;
ll dx[4] = {1,0,-1,0};
ll dy[4] = {0,1,0,-1};


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, ans = 0;
	cin >> n;
	vll v(n);
	rep(i, n) cin >> v[i];
	ll active = 0;	
	rep(i, n) {
		active = min(active, v[i]);
		ans += v[i] - active;
		active = v[i];

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

Measured memory_bytes: 256
def _max(a,b):
    return max(a,b)

def _min(a,b):
    return min(a,b)

def _sum(a,b):
    return a+b

class SegmentTree:

    def __init__(self, a):
        sz = len(a)
        self.n = int(1)
        while self.n < sz:
            self.n = int(self.n*2)

        self.func = _sum
        self.init = 0

        self.val = [0]*(self.n*2 - 1)
        self.val[self.n-1:self.n-1+sz] = a
        for i in range(self.n-2, -1, -1):
            self.val[i] = self.func(self.val[2*i+1], self.val[2*i+2])

    def update(self, pos, x):
        # 0-indexed
        k = int(pos + self.n-1)
        self.val[k] += x
        while k > 0:
            k = int(k-1) // 2
            self.val[k] = self.func(self.val[2*k+1], self.val[2*k+2])

    def query(self, a, b, k=0, l=0, r=-1):
            # 0-indexed
            # [a,b)に対してquery
            if r < 0:
                r = self.n
            if r <= a or b <= l:
                return self.init
            if a <= l and r <= b:
                return self.val[k]

            lv = self.query(a, b, 2*k+1, l, (l+r)//2)
            rv = self.query(a, b, 2*k+2, (l+r)//2, r)
            return self.func(lv, rv)

    def get(self, pos):
        # 0-indexed
        return self.val[pos + self.n-1]

n,q = map(int, input().split())
a = [0]*n
st = SegmentTree(a)

for _ in range(q):
    t,x,y = map(int, input().split())

    x -= 1
    if t == 0:
        st.update(x,y)
    else:
        ans = st.query(x,y)
        print(int(ans))


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

int main(){
    int h,n;
    std::cin >> h >> n;
    std::vector<int> x;
    int tmp;
    for(int i=0; i<n; i++){
        std::cin >> tmp;
        x.push_back(tmp);
    }
    std::string result;
    if (std::accumulate(x.begin(), x.end(), 0)>=h){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 892
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    Scanner sc = new Scanner(System.in);

    void show(final int[] xs) {
        if (xs != null) {
            String out =
                    Arrays.stream(xs)
                            .mapToObj(Integer::toString)
                            .collect(Collectors.joining(" "));
            System.out.println(out);
        }
    }

    void solve() {
        // Input
        int n = sc.nextInt();
        int[] R = new int[n];
        for (int i = 0; i < n; i++) {
            R[i] = sc.nextInt();
        }

        // Solve
        int swapCount = 0;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i; j < n; j++) {
                if (R[j] < R[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = R[i];
            R[i] = R[minIndex];
            R[minIndex] = tmp;
            if (i != minIndex) {
                swapCount++;
            }
        }
        // Output
        show(R);
        System.out.println(swapCount);
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}



Measured memory_bytes: 32656
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define INF 1200000000



int main(){
    
    string S,T;
    cin>>S>>T;
    string ans=T+S;
    cout<<ans<<endl;
    
}




Measured memory_bytes: 256
import sys
def gcd(x, y):
  if y == 0:
    return x
  else:
    return gcd(y, x%y)

def lcm(x, y):
  return x * y //gcd(x,y)
    

for line in sys.stdin:
  x, y = map(int, line.split())
  print(gcd(x, y), lcm(x,y))

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

int main(){
  long long n, a, b;
  cin >> n >> a >> b;
  if(a > b){
    long long tmp = a;
    a = b;
    b = tmp;
  }
  if((a + b) % 2 == 0){
    cout << (b - a) / 2;
    return 0;
  }
  if(a-1<n-b){
    long long s = a;
    a = 1;
    b = b - s;
    cout << (b - a) / 2 + s;
  }else{
    long long s = n - b + 1;
    b = n;
    a = a + s;
    cout << (b - a) / 2 + s;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
template <class T>
using Vec2 = vector<vector<T>>;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <class T1, class T2>
bool chmax(T1 &a, const T2 b){if(a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool chmin(T1 &a, const T2 b){if(a > b){a = b; return true;} return false;}
ll pow2(const int n){return (1LL << n);}
void co() { cout << endl; }
template <class Head, class... Tail>
void co(Head&& head, Tail&&... tail) {
    cout << head << ' ';
    co(forward<Tail>(tail)...);
}
void ce() { cerr << endl; }
template <class Head, class... Tail>
void ce(Head&& head, Tail&&... tail) {
    cerr << head << ' ';
    ce(forward<Tail>(tail)...);
}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const int n){cout << fixed << setprecision(n);}
constexpr int INF = 1e9+1;
constexpr ll LINF = 1e18L+1;
constexpr ll MOD = 1e9L+7;
constexpr ll MOD_N = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

using Mint = modint998244353;

int main(void){
    ll n, m;
    cin >> n >> m;
    vector<Mint> a(n), b(m);
    rep(i, n){
        ll t;
        cin >> t;
        a[i] = t;
    }
    rep(i, m){
        ll t;
        cin >> t;
        b[i] = t;
    }

    auto ans = convolution(a, b);
    rep(i, n + m - 1) cout << ans[i].val() << ' ';
    cout << endl;

    return 0;
}


Measured memory_bytes: 19064
#include <stdio.h>

int main(){
	
	int N;
	scanf("%d", &N);
	char S[N+1];
	
	scanf("%s", S);
	
	
if(N%2==1){
	puts("No");
}
else{
	int counter=0;

	int x = N/2;
	for(int i=0;i<x;i++){
		if (S[i] == S[x+i]){
		counter++;	
		}
	}
	
	if(counter == x){
		puts("Yes");
	}
	
	else{
		puts("No");
	}
}
	return 0;
}

Measured memory_bytes: 1660
#include "bits/stdc++.h"

using namespace std;
using LL = long long;

constexpr int N = 1e5 + 5;

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

    
    int h, n;
    cin >> h >> n;
    while (n --) {
        int a;
        cin >> a;
        h -= a;
    }
    cout << (h <= 0? "Yes" : "No");
}

Measured memory_bytes: 256
import math

a, b = map(int, input().split())

ans_b_min = b * 10
ans_b_list = []
for i in range(0, 10):
    ans_b_tmp = ans_b_min + i
    ans_b_list.append(ans_b_tmp)
    # print(ans_b_tmp)

for ans_b in ans_b_list:
    if int(math.floor(ans_b * 0.08)) == a:
        print(ans_b)
        exit(0)

print(-1)


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

typedef long long LL;

const int N=100000;

int n,m,v,p,a[N+9];

void into(){
  scanf("%d%d%d%d",&n,&m,&v,&p);
  for (int i=1;i<=n;++i)
	scanf("%d",&a[i]);
}

LL sum[N+9];
int ans;

void Get_ans(){
  sort(a+1,a+n+1,greater<int>());
  for (int i=1;i<=n;++i){
	sum[i]=sum[i-1]+a[i];
	if (i<=p) {ans=i;continue;}
	LL t=max(v-p-n+i,0),now=(LL)(a[i]+m)*(i-p)-sum[i-1]+sum[p-1];
    if (a[p]<=a[i]+m&&t*m<=now) ans=i;
	else break;
  }
}

void work(){
  Get_ans();
}

void outo(){
  printf("%d\n",ans);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 4928
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

trait IteratorExt: Iterator + Sized {
    fn vec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

impl<T: Iterator> IteratorExt for T {}

#[allow(unused)]
use std::cmp::{max, min};
#[allow(unused)]
use std::collections::HashMap;

#[allow(unused)]
fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        x
    } else {
        gcd(y, x % y)
    }
}

#[allow(unused)]
fn lcm(x: i64, y: i64) -> i64 {
    x * y / gcd(x, y)
}

fn main() {
    input! {
        // usize
        // n: usize,
        // vec
        // v: [i64; n],
        a: i64,
        s: String,
    }

    if a >= 3200 {
        println!("{}", s);
    } else {
        println!("{}", "red");
    }
}


Measured memory_bytes: 4352
def check(n, k , a, f, x):
    training_cnt = 0
    for i in range(n):
        t = x // f[i]  #a[i]をこれ以下にしたい。
        d = a[i] - t
        if d > 0:
            training_cnt += d
        if training_cnt > k:
            return False
    else:
        return True

def main():
    N, K = map(int, input().split())
    A = sorted([int(i) for i in input().split()])
    F = sorted([int(i) for i in input().split()], reverse=True)

    if check(N, K, A, F, 0):
        print(0)
        return


    left = 0
    right = 10 ** 12

    while left + 1 < right:
        mid = (left + right) // 2
        if check(N, K, A, F, mid):
            right = mid
        else:
            left = mid

    print(right)

if __name__ == '__main__':
    main()




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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  set<char> se;
  string s;
  cin >> s;
  for (auto c : s) {
    se.insert(c);
  }
  cout << ((se.size() == 2) ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

#define INF -1E9

int n,*sat;
long *dp;

int pos(int i,int j)
{
	return i*3+j;
}

void chMax(long *a,long b)
{
	if (*a<b) *a = b;
	return;
}

int main(void)
{
	int i,j;
	long ans;
	scanf("%d",&n);
	sat = (int *) malloc(sizeof(int) * 3*n);
	for (i=0;i<n;i++) scanf("%d %d %d",&sat[pos(i,0)],&sat[pos(i,1)],&sat[pos(i,2)]);

	dp = (long *)malloc(sizeof(long) * 3*n);
	dp[0] = sat[0];
	dp[1] = sat[1];
	dp[2] = sat[2];
	for (i=3;i<3*n;i++) {
		dp[i] = INF;
	}

	for (i=1;i<n;i++) {
		for (j=0;j<3;j++) {
			chMax(&dp[pos(i,j)] , dp[pos(i-1,(j+1)%3)] + sat[pos(i,j)]);
			chMax(&dp[pos(i,j)] , dp[pos(i-1,(j+2)%3)] + sat[pos(i,j)]);
		}
	}

	ans = INF;
	chMax(&ans , dp[pos(n-1,0)]);
	chMax(&ans , dp[pos(n-1,1)]);
	chMax(&ans , dp[pos(n-1,2)]);

	printf("%ld\n",ans);
	free(sat);
	free(dp);
	return 0;
}


Measured memory_bytes: 3712
def ketanowa(p):
    ans = 0
    p = str(p)
    for i in p:
        ans += int(i)
    return ans


def main():
    temp = input()
    temp = int(temp)
    if temp%2==0:
        print(temp)
    else:
        print(temp*2)

if __name__ == '__main__':
    main()


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

int main() {
  long long n,sum=0, mod=2019;
  cin>>n;
  vector<bool> vec(n+1,0);
  int a[n+1];
  for(int i=1; i<=n; i++){
    cin>>a[i];
  }
  for(int i=n; i>=1; i--){
    int j=i;
    sum=0;
    while(j+i<=n){
      j+=i;
      sum+=vec[j];
    }
    if(sum%2==a[i]){
      vec[i]=0;
    }else vec[i]=1;
  }
  int cnt=0;
  rep(i, n+1){
    if(vec[i]==1) cnt++;
  }
  cout<<cnt<<endl;
  
  rep(i, n+1){
    if(vec[i]==1) cout<<i<<endl;
  }
  
}

Measured memory_bytes: 1792
#include "stdio.h"

int main(){
	char a;
	char b;
	
	scanf("%c %c", &a, &b);
	
	if(a=='H' && b=='H'){
		printf("H\n");
	}
	else if(a=='D' && b=='D'){
		printf("H\n");
	}
	else if(a=='H' && b=='D'){
		printf("D\n");
	}
	else if(a=='D' && b=='H'){
		printf("D\n");
	}
	return (0);
}

Measured memory_bytes: 128
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if sum(a) < sum(b):
	print(-1)
else:
	excess = []
	needed_num = 0
	needed_score = 0
	for i in range(n):
		if a[i] > b[i]:
			excess.append(a[i]-b[i])
		elif a[i] < b[i]:
			needed_num += 1
			needed_score += b[i]-a[i]

	if needed_num == 0:
		print(0)
	else:
		excess.sort(reverse=True)
		e_sum = [excess[0]]
		for i in range(1, len(excess)):
			e_sum.append(e_sum[-1]+excess[i])
		ind = bisect_left(e_sum, needed_score)
		print(needed_num + ind+1)

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

int main() {

  int a,b,c;
  cin >> a >> b >> c;
  
  int count_5 = 0, count_7 = 0;
  
  if ( a == 5 ){
    count_5++;
  }else if ( a == 7 ){
    count_7++;
  }
  
  if ( b == 5 ){
    count_5++;
  }else if ( b == 7 ){
    count_7++;
  }
  
  if ( c == 5 ){
    count_5++;
  }else if ( c == 7 ){
    count_7++;
  }
  
  if ( count_5 == 2 && count_7 == 1 ){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
  
}



Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        n: usize,
        k: usize,
    }
    let m = (n - 1) * (n - 2) / 2;
    if k > m {
        println!("-1");
        return;
    }
    let mut edges = vec![];
    for i in 1..n {
        edges.push((0, i));
    }
    'outer: for i in 2..n {
        for j in 1..i {
            if edges.len() == n * (n - 1) / 2 - k {
                break 'outer;
            }
            edges.push((i, j));
        }
    }
    println!("{}", edges.len());
    for &(i, j) in &edges {
        println!("{} {}", i + 1, j + 1);
    }
}


Measured memory_bytes: 2156
import std.stdio;
import std.algorithm;

struct Lunlun {
	char[] s;

	void init() {
		s = new char[1];
		s[0] = '1';
	}
	
	void popFront() {
		bool countUp(char[] t) {
			if (t.length > 1) {
				if (t[0] < '9' && t[0] <= t[1]) {
					++t[0];
					return true;
				} else {
					if (!countUp(t[1..$])) {
						return false;
					}
					if (t[1] == '0') {
						t[0] = '0';
					} else {
						t[0] = cast(char)(t[1] - 1);
					}
							
					return true;
				}
				assert(false);
			} else {
				if (t[0] < '9') {
					t[0] = cast(char)(t[0] + 1);
					return true;
				}
				return false;
			}
			assert(false);
		}

		if (!countUp(s)) {
			s[] = '0';
			s ~= '1';
		}
	}

	const(char)[] front() {
		auto t = s.dup;

		reverse(t);
		return t;
	}

	bool empty() {
		return false;
	}
}

void main() {
	int k;

	readf(" %s", &k);

	Lunlun l;
	l.init();
	
	foreach (i;1..k) {
		l.popFront();
	}

	writeln(l.front);
}


Measured memory_bytes: 256
import math
N,M=map(int,input().split())
#M=int(input())
#mylist=list(map(int,input().split()))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

if N<=1 and M<=1:
    print(0)
    
elif N>=2 and M<=1:
    N_number=combinations_count(N, 2)
    #M_number=combinations_count(M, 2)

    print(N_number)
    
elif N<=1 and M>=2:
    #N_number=combinations_count(N, 2)
    M_number=combinations_count(M, 2)

    print(M_number)

else:
    N_number=combinations_count(N, 2)
    M_number=combinations_count(M, 2)

    print(N_number+M_number)

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

const int N = 2e5 + 10, mod = 1e9 + 7;



int main() {
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int x, y, z;
    cin >> x >> y >> z;
    cout << z <<' ' << x << ' ' <<  y << '\n';
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def main():
    a,b,c,d = map(int,input().split())
    flg = 0
    while a > 0 and c > 0:
        if flg:a -= d;flg = 0
        else:c -= b;flg = 1
    if flg:print('Yes')
    else:print('No')
if __name__ == "__main__":
    main()

Measured memory_bytes: 9192
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
#define intt long long

int main() {
	std::vector<int> x(5);
	for (auto& r : x)
		std::cin >> r;
	for (int i = 0; i < 5; ++i) {
		if (x[i] == 0) {
			std::cout << i + 1 << std::endl;
			return 0;
		}
	}

}


Measured memory_bytes: 3596
input = gets(nil)

a = []
b = []

input.split("\n").each_with_index do |line, i|
  if i % 2 == 0
    a = line.split(" ").map(&:to_i)
    next
  end

  b = line.split(" ").map(&:to_i)

  s1 = 0
  s2 = 0
  0.upto(3) do |i|
    s1 += 1 if a[i] == b[i]
    s2 += 1 if a.include?(b[i])
  end

  puts "#{s1} #{s2-s1}"
end

Measured memory_bytes: 6108
import java.math.BigInteger
import java.util.*

class D( private val n: Int, var invert: Boolean = false, private val r: ArrayList<String> = ArrayList( 2 * n ) ) {
    fun addLine( x: Int, y: Int ) {
        if ( ! invert ) {
            r.add( "${x + 1} ${y + 1}" )
        } else {
            r.add( "${n - x} ${n - y}" )
        }
    }

    fun print() {
        println( r.size )
        for ( rr in r ) {
            println( rr )
        }
    }

//    fun check( b: IntArray ) {
//
//    }
}

fun main( args: Array<String> ) {
    val sc = Scanner( System.`in` )
    val n = sc.nextInt()
    val d = D( n )
    val a = Array<BigInteger>( n, { sc.nextBigInteger() } )
//    val b = a.clone()
    run {
        val min = a.min()!!
        val max = a.max()!!
        if ( max < BigInteger.ZERO || ( min < BigInteger.ZERO && min.negate() > max ) ) {
            d.invert = true
            a.reverse()
            for ( i in a.indices ) {
                a[i] = a[i].negate()
            }
        }
    }
    for ( i in a.indices ) {
        val maxI = a.indices.maxBy { a[it] }!!
        if ( a[i] < BigInteger.ZERO ) {
            d.addLine( maxI, i )
            a[i] = a[i].add( a[maxI] )
        }
        if ( i > 0 && a[i] < a[i - 1] ) {
            d.addLine( i - 1, i )
            a[i] = a[i].add( a[i - 1] )
        }
    }
//    d.check( b )
    d.print()
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

template<class T>
class SegmentTree {

public:
    /**
     * @param N size
     * @param e identity element
     * @param operation operation for query
     * @param updater operation for update
     */
    SegmentTree(size_t N, T e, function<T(T, T)> operation, function<T(T, T)> updater)
            : e(e), operation(std::move(operation)), updater(move(updater)) {
        n = 1;
        while (n < N) {
            n *= 2;
        }
        data = vector<T>(2 * n - 1, e);
    }

    /**
     * iの値をxに更新
     * @param i index ( 0-indexed )
     * @param x  value
     */
    void update(int i, T x) {
        i += n - 1;
        data[i] = updater(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    /**
     * [a, b)の区間でクエリを実行
     */
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }

    /**
     * 添字でアクセス
     * @param i index ( 0-indexed )
     */
    T operator[](int i) {
        return data[i + n - 1];
    }

private:
    int n;
    vector<T> data;
    T e;
    function<T(T, T)> operation;
    function<T(T, T)> updater;

    T query(int a, int b, int k, int l, int r) {
        // 交差しない
        if (r <= a || b <= l) return e;
        // 区間 [a, b) に l, r が含まれる
        if (a <= l && r <= b) return data[k];
        // 左の子
        T c1 = query(a, b, 2 * k + 1, l, (l + r) / 2);
        // 右の子
        T c2 = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return operation(c1, c2);
    }
};

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

void Main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    SegmentTree<int> segmentTree(N, 0, [](int a, int b) { return gcd(a, b); }, [](int a, int b) { return b; });

    rep(i, N) {
        int a = A[i];
        segmentTree.update(i, a);
    }

    ll ans = -1;
    rep(i, N) {
        ans = max(ans, gcd(segmentTree.query(0, i), segmentTree.query(i + 1, N)));
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
vector<int> dy = {0,0,1,-1};
vector<int> dx = {1,-1,0,0};





int main(void){
    int M;
    ll K;
    cin >> M >> K;
    
    if(M == 1){
        if(K == 0){
            cout << 0 << " " << 0 << " " << 1 << " " << 1 << endl;
        }else{
            cout << -1 << endl;
        }
    }else if(pow(2, M) <= K){
        cout << -1 << endl;
    }else{
        for(int i = 0; i < pow(2, M); i++){
            if(i != K){
                cout << i << " ";
            }
        }
        cout << K << " ";
        for(int i = pow(2, M) - 1; i >= 0; i--){
            if(i != K){
                cout << i << " ";
            }
        }
        cout << K << endl;
    }
    
    
    
}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <functional>
#include <utility>
using namespace std;
typedef long long ll;
int main(){
  int n,m;
  cin >> n >> m;

  vector<int> div;

  for(int i = 1;i * i <= m;i++){
    if(m % i == 0)div.push_back(i),div.push_back(m/i);
  }

  int ans = 1;
  for(int d:div){
    if(m % d == 0 && m / d >= n){
      ans = max(ans,d);
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#![allow(unused_imports, non_snake_case)]
use proconio::{
    input, fastout,
    marker::{Chars, Bytes, Usize1}
};

struct UnionFind {
    size: usize,
    pos: Vec<isize>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        let size = n;
        let pos = vec![-1; n + 1];
        UnionFind { size, pos }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.pos[x] < 0 {
            x
        } else {
            let v = self.pos[x] as usize;
            self.pos[x] = self.find(v) as isize;
            self.pos[x] as usize
        }
    }
    fn unite(&mut self, x: usize, y: usize) -> Result<(), ()> {
        let mut x = self.find(x);
        let mut y = self.find(y);
        if x == y {
            return Err(());
        };
        if self.pos[x] > self.pos[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.pos[x] += self.pos[y];
        self.pos[y] = x as isize;
        Ok(())
    }
    fn same(&mut self, x: usize, y: usize) -> bool {
        self.find(x) == self.find(y)
    }
    fn size(&mut self, x: usize) -> usize {
        let x = self.find(x);
        -self.pos[x] as usize
    }
}


#[fastout]
fn main() {
    input!{
        N: usize,
        l:[(Usize1, Usize1); N]
    }
    let mut g = vec![0; N];
    for &(x, y) in &l {
        g[x] = y;
    }
    let mut stack = vec![];
    let mut uf = UnionFind::new(N);
    for x in 0..N {
        let y = g[x];
        if stack.is_empty() {
            stack.push(x);
            continue;
        } else {
            let m = stack.len();
            if g[stack[m-1]] > y {
                stack.push(x);
                continue;
            }
            for idx in (0..m).rev() {
                if g[stack[idx]] < y {
                    uf.unite(stack[idx], x).ok();
                    if idx < m - 1 {
                        stack[idx] = stack[idx+1];
                        stack.pop();
                    }
                } else {
                    break;
                }
            }
        }
    }
    for &(x, _) in &l {
        println!("{}", uf.size(x));
    }
}


Measured memory_bytes: 10744
import math
N = int(input())

fn = dict([(i, 0) for i in range(1, N+1)])
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            n = pow(x,2)+pow(y,2)+pow(z,2) +x*y +y*z +z*x
            if n <= N:
                fn[n] += 1
for v in fn.values():
    print(v)

Measured memory_bytes: 10288
#include <bits/stdc++.h>
using namespace std;
#define M 200010
#define LL long long
#define MOD 1000000007
#define inf 2147483647
#define llinf 40000000000000000ll
#define For(i, x, y) for(int i = (x); i < (y); ++ i)
#define rep(i, x, y) for(int i = (x); i <= (y); ++ i)
#define drep(i, x, y) for(int i = (x); i >= (y); -- i)
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline LL llread(){
	char ch=getchar();LL x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct Edge{
	int u, v, w, Next;
} G[M*2];
int head[M], tot;
inline void add(int u, int v, int w) {
	G[++ tot] = (Edge){u, v, w, head[u]};
	head[u] = tot;
}
struct Node{
	LL d; int u;
	inline bool operator < (const Node& rhs) const {
		return d > rhs.d;
	}
};
priority_queue<Node> Q;
bool done[M];
LL ds[M], dt[M];
LL fs[M], ft[M];
inline void dij(int n, int s, LL d[], LL f[]) {
	memset(done, 0, sizeof(done));
	while(!Q.empty()) Q.pop();
	rep(i, 1, n) d[i] = MOD*200000ll;
	d[s] = 0; Q.push((Node){0, s});
	f[s] = 1;
	while(!Q.empty()) {
		Node x = Q.top(); Q.pop();
		if(done[x.u]) continue;
		done[x.u] = 1;
		for(int i = head[x.u]; i != -1; i = G[i].Next) {
			if(d[G[i].v] > d[x.u] + G[i].w) {
				d[G[i].v] = d[x.u] + G[i].w;
				f[G[i].v] = f[x.u];
				Q.push((Node){d[G[i].v], G[i].v});
			}
			else if(d[G[i].v] == d[x.u] + G[i].w) {
				(f[G[i].v] += f[x.u]) %= MOD;
			}
		}
	}
}

int main() {
	//freopen("08.txt", "r", stdin);
	int n = read(), m = read(), s = read(), t = read();
	memset(head, -1, sizeof(head));
	rep(i, 1, m) {
		int u = read(), v = read(), w = read();
		add(u, v, w); add(v, u, w);
	}
	dij(n, s, ds, fs); dij(n, t, dt, ft);
	//rep(i, 1, n) printf("%d\n", fs[i]);
	LL res = 0;
	rep(i, 1, n) {
		if(ds[i] == dt[i] && ds[i] != MOD * 200000ll) {
			if(ds[i] + dt[i] == ds[t]) {
				res += fs[i] * ft[i] % MOD * fs[i] % MOD * ft[i] % MOD;
				res %= MOD;
			}
		}
	}
//	printf("%lld\n", res);
	rep(i, 1, tot) {
		int x = G[i].u, y = G[i].v;
		if(ds[x] + dt[y] + G[i].w == ds[t]) {
			if(min(ds[x], dt[y]) + G[i].w > max(ds[x], dt[y])) {
				//printf("%lld %lld %lld\n", ds[x], dt[y], G[i].w);
				res += fs[x] * ft[y] % MOD * fs[x] % MOD * ft[y] % MOD;
				res %= MOD;
			}
		}
	}
	//printf("%lld\n", res);
	printf("%lld\n", (fs[t] * ft[s] % MOD - res + MOD) % MOD);
	return 0;
}



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

int main(){

  char I[1000001], L[10001];
  int i, j, in, ln, state;

  scanf("%s", I);
  scanf("%s", L);

  in=strlen(I);
  ln=strlen(L);

  for(i=0 ;i<in; i++)
    if(strncmp(&I[i], L, ln)==0)printf("%d\n",i);

  return 0;

}

Measured memory_bytes: 3740
//ID:computerbox --> Hajiyev Huseyn
#include <bits/stdc++.h>
#define FAST_READ ios_base::sync_with_stdio(false);
#define in freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define MAXN 200010

using namespace std;

string nujno;
string odd="";

int main(){
FAST_READ;
cin>>nujno;
for(ll i=0;i<nujno.size();i++)
{
	ll id=i+1;
	if(id%2!=0)
	{
		odd+=nujno[i];
	}
}

cout<<odd<<endl;




return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int d, n;
    cin >> d >> n;
    int t = 1;
    for(int i = 0; i < d; i++)
    {
        t *= 100;
    }
    if(n != 100)
    {
        cout << t * n << endl;
    }
    else
    {
      cout << t*n + t << endl;
    }
}


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

int main()
{
    string s;
    cin >> s;
    int sum = 0;
    stack<int> stack1;
    stack<pair<int, int>> stack2;
    rep(i, s.size())
    {
        if (s[i] == '\\')
            stack1.push(i);
        else if (s[i] == '_')
            continue;
        else
        {
            if (!stack1.empty())
            {
                int idx = stack1.top();
                sum += i - idx;
                stack1.pop();
                int area = 0;
                while (!stack2.empty() && stack2.top().first > idx)
                {
                    int sub_area = stack2.top().second;
                    area += sub_area;
                    stack2.pop();
                }
                area += (i - idx);
                pair<int, int> p = make_pair(idx, area);
                stack2.push(p);
            }
        }
    }
    cout << sum << endl;
    cout << stack2.size();
    if (stack2.size() == 0)
        cout << endl;
    else
        cout << ' ';
    int r = stack2.size();
    vector<int> ans(r);
    rep(i, r)
    {
        ans[r - 1 - i] = stack2.top().second;
        stack2.pop();
    }
    rep(i, r)
    {
        cout << ans[i];
        if (i == r - 1)
            cout << endl;
        else
            cout << ' ';
    }
    return 0;
}

// accepted


Measured memory_bytes: 3272
import sys
 
# 関数 solve は，もちろん，問題に応じて書き換える
def solve(R):
    if R < 1200 :
        return 'ABC'
    elif R < 2800 :
        return 'ARC'
    else :
        return 'AGC'
 
# ここから下は，入力・出力形式が同じであれば，変えなくて良い．
def readQuestion():
    line = sys.stdin.readline().rstrip()
    return int(line)
 
def main():
    n = readQuestion()
    answer = solve(n)
    print(answer)
    
if __name__ == '__main__':
    main()

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

int cnt[100010][2];
int main(){
	int n; cin>>n;
	int ganjil = 0, genap = 0;
	for(int i=0; i<n; i++){
		int a; cin>>a;
		cnt[a][i%2]++;
		if(i%2) ganjil = max(ganjil, a);
		else genap = max(genap, a);
	}
	int odd = 0;
	cnt[0][1] = 0;
	for(int i=1; i<=ganjil; i++){
		if(cnt[i][1] > cnt[odd][1]){
			odd = i;
		}
	}
	int even = 0;
	cnt[0][0] = 0;
	for(int i=1; i<=genap; i++){
		if(cnt[i][0] > cnt[even][0]){
			even = i;
		}
	}

	if(odd == even){
		int tmp1 = 0;
		for(int i=1; i<=ganjil; i++){
			if(cnt[i][1] > cnt[tmp1][1] && (i != odd)){
				tmp1 = i;
			}
		}
		int tmp2 = 0;
		for(int i=1; i<=genap; i++){
			if(cnt[i][0] > cnt[tmp2][0] && (i != even)){
				tmp2 = i;
			}
		}
		int ans = n - cnt[odd][1] - max(cnt[tmp1][1], cnt[tmp2][0]);
		cout<<ans<<endl;
	} else {
		int ans = n - cnt[odd][1] - cnt[even][0];
		cout<<ans<<endl;
	}

}

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

int main(){
  string S;
  cin>>S;
  int N0=0,N1=0;
  for(int i=0;i<S.size();++i){
    if(S.at(i)=='0'){
      ++N0;
    }
    else{
      ++N1;
    }
  }

  cout<<2*min(N0,N1)<<endl;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;

const int MAXN = 1e5 + 10;
int N, L;
int A[MAXN];

int main() {
	register int i, j;
	scanf("%d%d", &N, &L);
	for(i = 0; i < N; ++i)
		scanf("%d", A + i);
	for(i = 0; i < N - 1; ++i)
		if(A[i] + A[i + 1] >= L) {
			puts("Possible");
			for(j = 0; j < i; ++j)
				printf("%d\n", j + 1);
			for(j = N - 1; j > i + 1; --j)
				printf("%d\n", j);
			printf("%d\n", i + 1);
			return 0;
		}
	puts("Impossible");
	return 0;
}

Measured memory_bytes: 1152
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod

N,K=map(int,input().split())

mod=10**9+7
for i in range(1,K+1):
    if N-K+1<i or K-1<i-1:
        print(0)
    else:
        print((nCr(N-K+1,i)*nCr(K-1,i-1))%mod)


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

int main(){
  int n;
  cin >> n;
  priority_queue<int> que;
  rep(i,n){
    int tmp;
    cin >> tmp;
    que.push(tmp);
  }
  int ans=0;
  ans += que.top()/2;
  que.pop();
  while(!que.empty()){
    ans+=que.top();
    que.pop();
  }
  cout << ans << endl;
}

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

int main() {
    int N, K; cin >> N >> K;
    vector<int> p(N); for (int i = 0; i < N; i++) cin >> p[i];
    sort(p.begin(), p.end(), less<int>());
    int a = 0;
    for (int i = 0; i < K; i++) {
        a += p[i];
    }
    cout << a << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long ;
int main(){
    int n,q;
    string s;
    cin >> n >> q >> s;
    vector<int> memo(n);
    vector<int> ans(n);
    memo[0] = 0;
    for(int i=1; i<n; i++){
        if(s[i] == 'C' && s[i-1] == 'A'){
            memo[i] = memo[i-1] +1;
        }
        else memo[i] = memo[i-1];
    }
    rep(i,q){
        int a,b;
        cin >> a >> b;
        a--; b--;
        ans[i] = memo[b] - memo[a] ;
    }
    rep(i,q){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 4312