akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::*;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::collections::*;

fn solve() {
    input! {
        n: usize, t: usize,
        mut abv: [(usize, usize); n]
    };

    abv.sort();
    let mut dp = vec![vec![0; t + 1]; n + 1];
    for i in 0..n {
        let (a, b) = abv[i];
        for j in 0..=t {
            let to_i = i + 1;
            let from_v = dp[i][j];

            // 食べない場合
            let to_j = j;
            let to_v = dp[to_i][to_j];
            dp[to_i][to_j] = to_v.max(from_v);

            // 食べた場合
            if j < t {
                let to_j = (j + a).min(t);
                let to_v = dp[to_i][to_j];
                dp[to_i][to_j] = to_v.max(from_v + b);
            }
        }
    }
    println!("{}", dp[n][t]);
}

fn main() {
    std::thread::Builder::new()
        .name("big stack size".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(|| {
            solve();
        })
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 71548
def main():
    mod = 10**9 + 7
    h, w, k = map(int, input().split())

    if w == 1:
        print(1)
        exit()
    if w == 2:
        print(pow(2, h-1, mod))
        exit()

    k -= 1

    fibo = [1, 2, 3, 5, 8, 13, 21]

    dp = [0] * w
    dp[0] = 1
    for _ in range(h):
        new_dp = [0] * w
        new_dp[0] = (dp[0] * fibo[w-2] + dp[1] * fibo[w-3]) % mod
        new_dp[1] = (dp[0] * fibo[w-3]) % mod
        new_dp[w-1] = (dp[w-1] * fibo[w-2] + dp[w-2] * fibo[w-3]) % mod
        new_dp[w-2] += (dp[w-1] * fibo[w-3]) % mod
        for i in range(1, w-1):
            new_dp[i] += ((fibo[i-1] * fibo[w-i-2]) * dp[i]) % mod
        for i in range(1, w-2):
            new_dp[i] += (fibo[i-1] * fibo[w-i-3]) * dp[i+1]
            new_dp[i] %= mod
            new_dp[i+1] += (fibo[i-1] * fibo[w-i-3]) * dp[i]
            new_dp[i+1] %= mod
        dp = new_dp

    print(dp[k] % mod)

main()

Measured memory_bytes: 62404
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		// 読み込み
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int N = sc.nextInt();

		List<Integer> p = new ArrayList<>();
		
		if (N == 0) {
			System.out.println(X);
			return;
		}
		for (int i = 1; i <=N ; i++) {
			p.add(sc.nextInt());
		}
		if (!p.contains(X)) {
			System.out.println(X);
			return;
		}
		
		int cost_l = Math.abs(X - 0);
		int ans_l = 0;
		
		for (int i = X -1; i >= 0 ; i--) {
			if(!p.contains(i)) {
				ans_l = i;
				cost_l = Math.abs(X - i);
				break;
			}
		}
		int cost_r = Math.abs(101 - X);
		int ans_r = 101;
		
		for (int i = X +1; i <= 101  ; i++) {
			if(!p.contains(i)) {
				ans_r = i;
				cost_r = Math.abs(X - i);
				break;
			}
		}		
		
		if(cost_l < cost_r) {
			System.out.println(ans_l);
		}
		else if(cost_l > cost_r) {
			System.out.println(ans_r);
		}
		else {
			System.out.println(ans_l);
		}
		
	}
}


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

int main(void){
    char a[10];
    char b[1000];
    int j,count;
    count=0;
    scanf("%s",a);
    for(;;){
        scanf("%s",b);
        if(strcmp(b,"END_OF_TEXT")==0) break;
        for(j=0;j<1000;j++){
            if('A'<=b[j]&&b[j]<='Z') b[j]+=32;
        }
        if(strcmp(a,b)==0) count+=1;
    }
    printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 1812
n,*x = map(int,open(0).read().split())
ans = 0
xr = {}
xl = {}
for i in range(n):
  xrt = i+x[i]
  if xrt < n:
    if xrt in xr:
      xr[xrt] += 1
    else:
      xr[xrt] = 1
  xlt = i-x[i]
  if xlt >= 0:
    if xlt in xl:
      xl[xlt] += 1
    else:
      xl[xlt] = 1
for i in xr.keys():
  if i in xl:
    ans += xr[i]*xl[i]
print(ans)

Measured memory_bytes: 36268
// A.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
int main()
{
    string s;

    cin >> s;
    int sum = 0;
    for (int i = 0; i < s.size(); i++) {
        sum += s[i] - '0';
    }
    if (sum % 9 == 0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3748
def resolve():
    N = int(input())
    L = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        for j in range(i, N):
            if L[i] == L[j]:
                continue
            for k in range(j, N):
                if L[k] == L[i] or L[k] == L[j]:
                    continue
                s = sorted([L[i], L[j], L[k]])
                if s[0] + s[1] > s[2]:
                    ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

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

int main(){
    int N, M;
    cin >> N >> M;
    vector<pair<long long, long long>> A(N);
    for(int i = 0; i < N; i++)cin >> A[i].first >> A[i].second;
    sort(A.begin(), A.end());
    priority_queue<long long> que;
    int days = 1, n = 0;
    long long ans = 0;
    while(days <= M){
        if(n != N && A[n].first <= days){
            que.push(A[n].second);
            n++;
        }else{
            days++;
            if(!que.empty()){
                ans += que.top();
                que.pop();
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2936
'use strict'

function main(s) {

  const nums = s.split('\n').slice(1, -1).map(n => Number(n));
  let sum  = nums.reduce((a, b) => a + b);

  if (sum % 10 === 0) {
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
      if (nums[i] % 10 !== 0) {
        sum -= nums[i];
        break;
      }
    }

    if (sum % 10 === 0) {
      sum = 0;
    }
  }

  console.log(sum);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7500
x,y=map(int,input().split())
mod = pow(10, 9) + 7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**6+1)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys
if (x+y)%3:
    print(0)
    sys.exit()
c = (x+y)//3
if x < c or y < c:
    print(0)
    sys.exit()

x,y=x-c,y-c
print(cmb(x+y,x,mod))


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

int main()
{
  int s,k;
  cin>>k>>s;
  int h = 2500;
  int ans = 0;
  for(int i = 0; i <=k; i++)
    for(int j = 0; j <= k; j++)
      if(s - (i+j) >= 0 && s-(i+j) <= k)
        ans++;  
  
  cout<<ans<<"\n";
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
        int x,y;
    while(true){
   cin>>x>>y;
   if(x==0 && y==0){
       break;
   }
   if(x<y){
     cout<< x<<" "<<y<<endl;
   }
   else{
    cout<< y<<" "<<x<<endl;
   }


   }
 return 0;
}


Measured memory_bytes: 3000
#include<stdio.h>
#define MAX 25
#define NIL -1
typedef struct  { int parent, left, right; }Node;

Node T[MAX];
int n, D[MAX], H[MAX];

void preorder(int u)
{
	if (u == NIL) return;
	printf(" %d", u);
	preorder(T[u].left);
	preorder(T[u].right);
}
void inorder(int u)
{
	if (u == NIL) return;
	inorder(T[u].left);
	printf(" %d", u);
	inorder(T[u].right);
}
void postorder(int u)
{
	if (u == NIL) return;
	postorder(T[u].left);
	postorder(T[u].right);
	printf(" %d", u);
}
int main()
{
	int v, l, r, root = 0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) T[i].parent = NIL;

	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &v, &l, &r);
		T[v].left = l;
		T[v].right = r;
		if (l != NIL) T[l].parent = v;
		if (r != NIL) T[r].parent = v;
	}

	for (int i = 0; i < n; i++) {
		if (T[i].parent == NIL) root = i;
	}

	printf("Preorder\n");
	preorder(root);
	printf("\nInorder\n");
	inorder(root);
	printf("\nPostorder\n");
	postorder(root);
	printf("\n");
}


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

int main(){
    int n,t;
    vector<pair<int,int> > timeCost;
    scanf("%d %d",&n,&t);
    for(int i=0;i<n;i++){
        int t1,c1;
        scanf("%d %d",&c1,&t1);
        timeCost.push_back({c1,t1});
    }
    sort(timeCost.begin(),timeCost.end());
    int cost;
    bool flag=false;
    for(int i=0;i<n;i++){
        if(timeCost[i].second<=t) {
            cost=timeCost[i].first;
            flag=true;
            break;
        }
    }
    if(flag) printf("%d\n",cost);
    else printf("TLE\n");
    return 0;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::*;

fn read <T: FromStr>(s: &mut StdinLock) -> Option<T> {
    let s = s.by_ref().bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

pub fn main() {
    let stdin = stdin();
    let mut stdin = stdin.lock();

    let n: u32 = read(&mut stdin).unwrap();
    let nums: Vec<u32> = (0..n).map(|_x| read(&mut stdin).unwrap()).collect();

    let mut res: Vec<u32> = Vec::with_capacity(n as usize);
    for i in 0..n as usize {
        let x = nums[i];

        if !res.contains(&x) {
            res.push(x);
        }
    }

    println!("{:?}", res.len());
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>

using namespace std;

string rotate(const string& s) { return s.back() + s.substr(0, s.size() - 1); }

int main() {
  string s, t;
  cin >> s >> t;

  bool ok = false;
  for (int i = 0; i < s.size(); ++i) {
    s = rotate(s);
    if (s == t) {
      ok = true;
      break;
    }
  }
  if (ok)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
/*
    By Prabal Aggarwal
*/
#include <bits/stdc++.h>
#define fastIo                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
using namespace std;
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1)
{
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args)
{
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}
#else
#define trace(...)
#endif
#define ll long long
#define MOD 1000000007
const int N = 100005;
int C[N];
void Rotate(int B[],int n,int k)
{
    k=k%n;
    if(k==0)
        return;
    int i=0,j=n-1;
    while(i<j)
    {
        swap(B[i],B[j]);
        i++,j--;
    }
    i=0,j=k-1;
    while(i<j)
    {
        swap(B[i],B[j]);
        i++,j--;
    }
    i=k,j=n-1;
    while(i<j)
    {
        swap(B[i],B[j]);
        i++,j--;
    }

}
bool f(int A[], int B[], int n)
{
    reverse(B,B+n);

    int x = -1;
    for(int i=0;i<n;i++)
    {
        if(A[i]==B[i])
        {
            x = A[i];
            break;
        }
    }
    if(x==-1)
        return true;

    vector<int>v;
    for(int i=0;i<n;i++)
    {
        if(A[i]!=B[i] && A[i]!=x && B[i]!=x)
        {
            v.push_back(i);
        }
    }

    for(int i=0;i<n;i++)
    {
        if(A[i]==B[i])
        {
            if(v.size()==0)
                return false;
            int j = v.back();
            v.pop_back();
            swap(B[i],B[j]);
        }
    }

    return true;



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

    int A[n];
    int B[n];
    for (int i = 0; i < n; i++)
        cin >> A[i];

    for (int i = 0; i < n; i++)
        cin >> B[i];

    if (f(A, B, n))
    {
        cout << "Yes" << endl;
        for (int i = 0; i < n; i++)
            cout << B[i] << " ";
    }
    else
    {
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 5844
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

vector<vector<int>> to;
vi seen;

void dfs(int v) {
    if (seen[v]) return;
    seen[v] = true;
    for (auto u : to[v]) {
        dfs(u);
    }
}

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

    int n, m;
    cin >> n >> m;
    to.resize(m+n);
    rep(i, n) {
        int id = m+i;
        int k;
        cin >> k;
        rep(j, k) {
            int l;
            cin >> l;
            l--;
            to[id].pb(l);
            to[l].pb(id);
        }
    }
    seen.resize(m+n);
    dfs(m);
    for (int i = m; i < m+n; ++i) {
        if (!seen[i]) { puts("NO"); return 0;}
    }
    puts("YES");
}


Measured memory_bytes: 9208
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}

vector<ll> pw2(51,1);vector<ll> pw10(19,1);
ll fac[500001],finv[500001],inv[500001];
 
void table() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(ll i=2;i<500001;i++){
        fac[i]= fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

ll dev(long long a,long long b){
    return (a*inv[b])%MOD;
}

ll comb(ll n, ll k){
    if(n<k) return 0;
    if(n<0 || k<0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll perm(ll n,ll k){
    if(n<k) return 0;
    if(n<0 || k<0) return 0;
    return (fac[k]*comb(n,k))%MOD;
}
int main(){
    table();
    {rep1(i,50) pw2[i]=2*pw2[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll N; cin>>N;
    ll ans=0;
    vector<ll> A(N+1,0);
    vector<ll> s(N+2,0);
    rep1(i,N){
      cin>>A[i];
      s[i+1]=s[i]+(fac[N]*inv[i])%MOD;
        s[i+1]%=MOD;
    }
    rep1(i,N){
        ll tmp_1=(s[i+1]-s[2]);
        ll tmp_2=(s[N-i+2]-s[1]);
        if(tmp_1<0) tmp_1+=MOD;
        if(tmp_2<0) tmp_2+=MOD;
        tmp_1%=MOD;
        tmp_2%=MOD;
        
        ans+=(A[i]*(tmp_1+tmp_2)%MOD)%MOD;
        ans%=MOD;
    }
    cout<<ans<<endl;
}



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

long long n, x, y, arr[100005];

int main () {
	cin>>n;
	
	for(int i=1; i<=n; i++){
		cin>>arr[i];
	}
	sort(arr+1, arr+n+1);
    
    for(int i=n; i>0; i--){
        if(arr[i]==arr[i-1]){
            if(x==0){
                x=arr[i];
                i--;
            }
            else{
                y=arr[i];
                break;
            }
        }
    }
    
    cout<<x*y<<endl;
}


Measured memory_bytes: 4324
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <cctype>
using namespace std;

int main(){
    string A,B,C;cin>>A>>B>>C;
    int lenA,lenB,lenC;
    lenA=A.length();
    lenB=B.length();
    lenC=C.length();
    if(A[lenA-1]==B[0]&&B[lenB-1]==C[0]){
        puts("YES");
    } else {
        puts("NO");
    }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a,b,c, k;
    cin >> a >> b >> c >> k;
    ll ans=(k%2==0)?(a-b):(b-a);
    cout<<ans<<"\n";
}


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

int main(){
  int a,b;
  cin>> a >> b;
  
  int x=max(a,b),y=min(a,b),z=x%y;
  while (z!=0){
    x=y; y=z; z=x%y;
  }
  cout<< (int64_t)a*b/y <<endl;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n;cin >> n;
    int t2=0, x2=0, y2=0;
    vector<int> tv(n), xv(n), yv(n);
    REP(i,n){
        cin >> tv[i] >> xv[i] >> yv[i];
    }
    REP(i,n){

        int t = tv[i], x = xv[i], y = yv[i];
        int tmp = (t - t2 - (abs(x2 - x) + abs(y2 - y)));
        if (tmp% 2 == 0&&tmp>=0)
        {
        }
        else
        {
            cout << "No"
                 << "\n";
            return 0;
        }

        t2 = t;
        x2 = x;
        y2 = y;
    }
    cout << "Yes" << "\n";
    return 0;
}

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

int main() {
    int A, B;
    cin >> A >> B;
    string s;
    cin >> s;

    bool flag = true;
    if(s[A] != '-') flag = false;
    if(s.size() != A+B+1) flag = false;
    for(int i = 0; i < s.size(); i++) {
       if(i == A) continue;
       if(s[i] < '0' || '9' < s[i]) flag = false;
    }

    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

int a[MAX];
int n;
int count;


void bubbleSort(){
	int i;
	int flag=1;
	int t;

	while(flag){
		flag=0;
		for(i=n-1;i>0;i--){
			if(a[i-1]>a[i]){
				t=a[i-1];
				a[i-1]=a[i];
				a[i]=t;
				++flag;
				++count;
			}
		}

	}

	return;
}


int main(void){
	int i;

	cin>>n;
	for(i=0;i<n;i++)cin>>a[i];

	bubbleSort();

	for(i=0;i<n;i++){
		cout<<a[i];
		if(i!=n-1)cout<<" ";
	}
	cout<<endl<<count<<endl;



}

Measured memory_bytes: 1160
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
#include <set>
#include <string>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
//typedef pair<ll, P> T;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define revrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define f first
#define s second
#define pb push_back

ll mod = 1000000007;
const ll INF = 100000000000010000;
//const ull B = 998244353;

ll bit[200010];
//ll kai[3010];
ll Cnt[1000010];

//void pres(double A, ll x = 20) { printf("%.20f\n", x); }



/*ll sum(ll i)
{
	//i += 1;
	ll t = 0;
	while (i > 0)
	{
		t += bit[i];
		i -= i & -i;
	}
	return t;
}

void add(ll i, ll x)
{
	//i += 1;
	while (i <= 200005)
	{
		bit[i] += x;
		i += i & -i;
	}
}*/

/*`ll SAIKI(ll S) {
	for (ll T = S; ; T = (T - 1) & S) {

	}
}*/



void test() {
	cout << "888888888888888888888888" << endl;
}

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll k) {
	x %= mod;
	ll res = 1;
	while (k > 0) {
		if (k % 2) {
			res *= x; res %= mod;
		}
		x *= x; x %= mod;
		k /= 2;
	}
	return res;
}

ll div_mod(ll x) {
	return pow_mod(x, mod - 2);
}

//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAXcomb; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
ll comb(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * finv[k] % mod * finv[n - k] % mod;
}

void makePrimeList(ll x) {
	ll X = x;
	for (ll j = 2; j * j <= x; j++) {
		ll cnt = 0;
		while (X % j == 0) {
			cnt++;
			X /= j;
		}
		if (cnt) {
			Cnt[j] = max(Cnt[j], cnt);
		}
	}
	if (X != 1) Cnt[X] = max(Cnt[X], 1LL);
}

ll a, b;

void solve() {
	cin >> a >> b;
	if (a < 10 && b < 10) {
		cout << a * b << endl;
	}
	else {
		cout << -1 << endl;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	ll N;
	cin >> N;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L
const int mxN = 1e9 + 7;

char s[100005];
long long dp[100005][13];

int main() {
    string s;
    cin >> s;
    int n = s.length();

    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        int c;
        if (s[i] == '?') c = -1;
        else c = s[i] - '0';

        for (int j = 0; j < 10; j++) {
            for (int ki = 0; ki < 13; ki++) {
                if (c != -1 && c != j) continue;
                dp[i + 1][(ki * 10 + j) % 13] += dp[i][ki];
            }
        }
        for (int j = 0; j < 13; j++) dp[i+1][j] %= MOD;
    }

    long long res = dp[n][5];
    cout << res;
    return 0;
}

Measured memory_bytes: 13868
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 200005
#define INF 1000000005LL
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int a,b,c,d;
int x,y,z;
int n,k;
string s;
map<char,char> m;

int main(){
  cin >> n >> k >> s;
  m['A'] = 'a';
  m['B'] = 'b';
  m['C'] = 'c';
  s[k-1] = m[s[k-1]];
  cout << s << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n, h, w; cin >> n >> h >> w;
  vector<bool> sel(n*w);
  for(int i=0;i<n;++i) {
    int x; cin >> x;
    if(i%2 == 0) {
      for(int j=0;j<w;++j) {
        if(0 <= i*w+x+j && i*w+x+j < n*w) sel[i*w+x+j] = true;
      }
    } else {
      for(int j=0;j<w;++j) {
        if(0 <= i*w-x+j && i*w-x+j < n*w) sel[i*w-x+j] = true;
      }
    }
  }
  int cnt = 0;
  for(int i=0;i<n*w;++i) {
    cnt += !sel[i];
  }
  cout << cnt * h << endl;
}



Measured memory_bytes: 3184
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    A, B, C = map(int, input().split())
    K = int(input())
    ans = 0
    while A >= B:
        ans += 1
        B *= 2
    
    while B >= C:
        ans += 1
        C *= 2
    if ans <= K:
        print('Yes')
    else:
        print('No')

if __name__ == "__main__":
    main()


Measured memory_bytes: 9460
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a[50], n, sum = 0;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &a[i]);
	}
	for(int i = 0; i < n; ++i){
		for(int j = i-1; j >= 0; --j){
			sum += a[i] * a[j];
			//printf("i%d j%d \t", i, j);
		}
	}
	printf("%d\n", sum);
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

int di[] = {1, 0, -1, 0}, dj[] = {0, 1, 0, -1};

void solve() {
  int w, h;
  while (cin >> w >> h, w) {
    int sx, sy, gx, gy, n;
    cin >> sx >> sy >> gx >> gy >> n;
    sx--, sy--, gx--, gy--;
    vvi v(h, vi(w));
    rep(i, n) {
      int c, d, x, y;
      cin >> c >> d >> x >> y;
      x--;
      y--;
      rep(i, 2 + d * 2) rep(j, 4 - d * 2) v[y + i][x + j] = c;
    }
    int roadColor = v[sy][sx];
    function<bool(int, int)> dfs = [&](int i, int j) {
      if (i < 0 || j < 0 || i >= h || j >= w || v[i][j] != roadColor) return false;
      if (i == gy && j == gx) return true;
      v[i][j] = -1;
      bool b  = false;
      rep(k, 4) b |= dfs(i + di[k], j + dj[k]);
      return b;
    };
    cout << (dfs(sy, sx) ? "OK" : "NG") << endl;
  }
}

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		if(a == 7 || a == 5 || a == 3) System.out.println("YES"); 
		else System.out.println("NO"); 
	}
}

Measured memory_bytes: 21972
#include <iostream>
using namespace std;
int main()
{
	int A,B,x[3],max;
	cin>>A>>B;
	x[0]=A+B;
	x[1]=A-B;
	x[2]=A*B;
	max=x[0];
	for(int i=1;i<3;i++)
		if(x[i]>max)max=x[i];
	cout<<max;
	return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 998244353
#define rep(i,x) for(int i=0;i<x;i++)
string s,t;
int A,B;
ll modpow(ll x,ll n)
{
	ll res=1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[50005],R[50005];
void make(){
	F[0] = 1;
	for(int i=1;i<50005;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<50005;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){return F[a]*R[b]%mod*R[a-b]%mod;}
int main(){
	cin>>s>>t;make();
	rep(i,s.size()){
		if(s[i]==t[i]&&s[i]=='1') A++;
		else if(s[i]=='1') B++;
	}
	ll ans = 0;
	for(int i=0;i<=A;i++){
		ll ret = F[i]*F[A-i]%mod*F[A-i]%mod;
		ll add = 0;
		int sum = i+B;
		for(int i=0;i<=B;i++){
			ll x = C(B,i);
			x = x*modpow(B-i,sum)%mod;
			if(i%2==0) add=(add+x)%mod;
			else add=(add+mod-x)%mod;
		}
		ans += ret*add%mod*F[B]%mod*C(A+B,i+B)%mod*C(A,i)%mod;
	}
	cout<<ans%mod<<endl;
}

Measured memory_bytes: 1152
#include<cstdio>
#include<cmath>
#define SIZE 1000000
#define sizE 1000000

int prime[sizE], nprime=0;
int mark[SIZE];

void sieve()
{
    int i,j, limit=sqrt(SIZE*1.0)+2;

    mark[0]=1;
    mark[1]=1;

    for(i=4; i<=SIZE; i+=2)
        mark[i]=1;

    prime[nprime]=2;

    for(i=3; i<=SIZE; i+=2)
    {
           if(!mark[i])
            {
            prime[++nprime] = i;

            if(i<=limit)
            {
                for(j=i*i; j<=SIZE; j+=i*2)
                mark[j]=1;
            }
        }
    }

}

int main()
{
    int n;

    sieve();

    while(scanf("%d", &n)==1)
    {
        int i,k;
        i=k=0;

        while(i++<n)
        {
            if(!mark[i])
            k++;
        }

        printf("%d\n", k);
    }

    return 0;
}

Measured memory_bytes: 6764
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define Rep(i,a,b) for(ll i=a;i<b;i++)
#define pb emplace_back
#define allv v.begin(),v.end()
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
#define FASTio ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define deb(x) cout<<(#x)<<" "<<x<<endl
ll mod=1e9+7;
template<typename t>
ll Max(ll a,ll b)
{
    return (a>b)?a:b;
    
}
ll Min(ll a,ll b)
{
    return (a>b)?b:a;
}
ll power(ll a,ll b)
{
    ll p=1;
    a=a%mod;
    b=b%mod;
    while(b)
    {
        if(b&1)
        {
            p=((p%mod)*(a%mod))%mod;
        }
        a=((a%mod)*(a%mod))%mod;
        b=(b/2);
    }
    return p%mod;
}
ll h,w,k;
ll ma=1e15;
bool isValid(ll i,ll j)
{
    return (i>=1 && i<=h && j>=1 && j<=w);
}
ll direc[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main()
{
    int t;
    t=1;
  //  cin>>t;
    while(t--)
    {
      //  ll h,w,k;
      cin>>h>>w>>k;
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        char mat[h+1][w+1];
        Rep(i,1,h+1)
        {
            Rep(j,1,w+1)
            cin>>mat[i][j];
        }
        ll dist[h+1][w+1];
        bool visited[h+1][w+1];
       // memset(dist,INT_MAX,sizeof(dist));
       for(ll i=1;i<=h;i++){
       for(ll j=1;j<=w;j++)
       {
           dist[i][j]=-1;
           visited[i][j]=false;
       }}
        dist[x1][y1]=0;
        visited[x1][y1]=true;
        queue<pair<ll,ll>> q;
        q.push(make_pair(x1,y1));
        while(!q.empty())
        {
            pair<ll,ll> curr=q.front();
            q.pop();
            ll i=curr.first;
            ll j=curr.second;
            for(ll p=0;p<4;p++)
            {
              for(ll Q=1;Q<=k;Q++)
              {
                ll i1=i+direc[p][0]*Q;
                ll j1=j+direc[p][1]*Q;
                if(isValid(i1,j1) && mat[i1][j1]!='@')
                {
                    if(dist[i1][j1]==-1)
                    {
                        dist[i1][j1]=dist[i][j]+1;
                        q.push(make_pair(i1,j1));
                    }
                    else
                    {
                        if(dist[i1][j1]>=(dist[i][j]+1))
                        dist[i1][j1]=dist[i][j]+1;
                        else
                        break;
                    }
                    
                    

                }
                else
                break;
              }
            }
            
        }
        
        cout<<dist[x2][y2]<<endl;
    }
    return 0;
}


Measured memory_bytes: 14944
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<ll, int> P;
#define MOD (1000000007ll)

ll sq(ll x){
	return x*x;
}

int main(void){
	int a,b,c;
	cin >> a >> b >> c;
	cout << ((a+b==c || b+c==a || c+a==b)?"Yes":"No") << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string[] str=Console.ReadLine().Split(' ');
      int A=int.Parse(str[0]);
      int B=int.Parse(str[1]);
      Console.WriteLine(A*B-(A+B-1));
    }
    
  }

}


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

using ll = long long;
const int N = 100010;

int a[N], b[N], c[N], fa[N];

int find(int u){
    return fa[u] == u ? u : (fa[u] = find(fa[u]));
}

void unite(int u, int v){
    u = find(u), v = find(v);
    if (u == v){
        return;
    }
    fa[u] = v;
}

int main(){
    int n, q;
    ll m;
    scanf("%d%lld%d", &n, &m, &q);
    for (int i = 0; i < n; ++ i){
        fa[i] = i;
    }
    bool flag = false;
    for (int i = 0; i < q; ++ i){
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        if (c[i] == 0){
            unite(a[i], b[i]);
        }
        else{
            flag = true;
        }
    }
    for (int i = 0; i < q; ++ i){
        if (c[i] == 1){
            if (find(a[i]) == find(b[i])){
                puts("No");
                return 0;
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; ++ i){
        if (find(i) == i){
            ++ cnt;
        }
    }
    ll left = n - 1 + int(flag);
    ll right = n - 1 + 1ll * cnt * (cnt - 1) / 2 - (cnt - 1);
    puts(left <= m && m <= right ? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define int         ll int
#define float       double
#define	endl		'\n'
#define maxpq       priority_queue<ll>
#define minpq       priority_queue<ll, vector<ll>, greater<ll> >
#define mii         map<int,int>
#define msi         map<string,int>
#define mis         map< int, string>
#define mpi         map<pair< int, int>, int>
#define pii         pair< int, int>
#define vi          vector< int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define EPS         1e-9
#define INF         1e18
#define PI          3.14159265358979323846
#define MAXI        1000000
#define what_is(x)  cerr << #x << " is " << x << endl;
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
#define N 100005
signed main()
{
	fast;
    int t=1;
    //cin>>t;
    while(t--)
    {
    	int n;
    	cin>>n;
    	int arr[n];
    	int i,k;
    	int sum=0;
    	for(i=0;i<=n-1;i++)
    	{
    		cin>>arr[i];
    		sum+=arr[i];
		}
    	sort(arr,arr+n);
    	int num=n-1;
    	int ans=0;
    	ans+=arr[n-1];
    	num--;
    	for(i=n-2;i>=0;i--)
    	{
    		if(num<=0) break;
    		ans+=arr[i];
    		num--;
    		if(num<=0) break;
    		ans+=arr[i];
    		num--;
    		if(num<=0) break;
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 5172
/*
      author : nishi5451
      created: 11.08.2020 22:11:09
*/

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


int main(){
    int r; 
    cin >> r;
    cout << 3*r*r << endl;
    return 0;
}

Measured memory_bytes: 3640
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <string>
#include <map>
#include <set>
#include <iostream>

typedef long long ll;

using namespace std;

int main() {
	string s;
	cin >> s;
	while (s.size() >= 2 && s.back() == 'i' && s[s.size() - 2] == 'h') {
		s.pop_back();
		s.pop_back();
	}
	if (s.size() == 0) {
		puts("Yes");
	}
	else {
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 764
/*================================================================
*   Copyright (C) 2019 Sangfor Ltd. All rights reserved.
*
*   创 建 者： badcw
*   创建日期： 2019/12/22
*
================================================================*/
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn = 100;
const int mod = 1e9+7;
ll qp(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

template <class T>
inline bool scan(T& ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0; // EOF
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
}

//template <class T>
//inline void out(T x) {
//    if (x > 9) out(x / 10);
//    putchar(x % 10 + '0');
//}

ll f(ll n) {
    if (n < 5) return 0;
    return n / 5 + f(n / 5);
}

int main(int argc, char* argv[]) {
    ll n;
    scanf("%lld", &n);
    if (n & 1) puts("0");
    else {
        printf("%lld\n", f(n / 2));
    }
    return 0;
}

Measured memory_bytes: 256
from collections import deque
n = int(input())
a = list(map(int, input().split()))

d = deque()

for i in range(0,n,2):
    d.append(a[i])

for i in range(1,n,2):
    d.appendleft(a[i])

if n % 2 == 0:
    for i in d:
        print(i)
else:
    d.reverse()
    for i in d:
        print(i)

Measured memory_bytes: 106592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
//-------
const int N = 101010, MOD = 1e9 + 7;
typedef pair<pii, int> iii;
int n, m, S, T;
iii edge[N + N];
vector<pii> G[N];
ll dT[N], dS[N];
int toS[N], toT[N];
bool vis[N];
int add(int a, int b) {
	a += b;
	if(a >= MOD) a -= MOD;
	return a;
}
int sub(int a, int b) {
	a -= b;
	if(a < 0) a += MOD;
	return a;
}
int mul(int a, int b) {
	return 1ll * a * b % MOD;
}
void dij(int st, ll dis[], int tot[]) {
	priority_queue<pair<ll, int> > q;
	rep(i, 0, n) dis[i] = 1e18;
	rep(i, 0, n) vis[i] = 0;
	rep(i, 0, n) tot[i] = 0;
	tot[st] = 1;
	dis[st] = 0;
	q.push({0, st});
	while(!q.empty()) {
		int u = q.top().se; q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(const auto & to : G[u]) {
			int v, w; tie(v, w) = to;
			if(vis[v]) continue;
			ll d = dis[u] + w;
			if(d < dis[v]) {
				q.push({-d, v});
				dis[v] = d;
				tot[v] = tot[u];
			} else if(d == dis[v]) {
				tot[v] = add(tot[u], tot[v]);
			}
		}
	}
}
int main() {
	scanf("%d%d%d%d", &n, &m, &S, &T);
	S--, T--;
	rep(i, 0, m) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		u--, v--;
		edge[i] = {{u, v}, w};
		G[u].pb({v, w});
		G[v].pb({u, w});
	}
	dij(S, dT, toT);
	dij(T, dS, toS);
	assert(toT[T] == toS[S]);
	assert(dS[S] == dT[T]);
//	rep(i, 0, n) de(dS[i]);
	vector<iii> e;
	rep(i, 0, m) {
		int u, v, w; u = edge[i].fi.fi, v = edge[i].fi.se, w = edge[i].se;
		if(dS[v] + w == dT[T] - dT[u] || dS[u] + w == dT[T] - dT[v]) e.pb(edge[i]);
	}
	int ans = 0;
	ans = mul(toT[T], toS[S]);
//	de(ans);
	rep(i, 0, n) if(dT[i] + dS[i] == dT[T] && dT[i] == dS[i]) ans = sub(ans, mul(mul(toT[i], toS[i]), mul(toT[i], toS[i])));
	rep(i, 0, sz(e)) {
		int u, v, w; u = e[i].fi.fi, v = e[i].fi.se, w = e[i].se;
//		dd(u), dd(v), de(w);
		if(dT[u] + w == dT[v] && dT[u] * 2 < dT[T] && dS[v] * 2 < dT[T] && dT[u] + dS[v] + w == dT[T]) ans = sub(ans, mul(mul(toT[u], toS[v]), mul(toT[u], toS[v])));
		swap(u, v);
		if(dT[u] + w == dT[v] && dT[u] * 2 < dT[T] && dS[v] * 2 < dT[T] && dT[u] + dS[v] + w == dT[T]) ans = sub(ans, mul(mul(toT[u], toS[v]), mul(toT[u], toS[v])));
	//	if(dT[u] + w == dT[v] && abs(dT[u] - dS[v]) < w) ans = sub(ans, mul(toT[u], toS[v]));
//		dd(dT[u]), de(dS[v]);
	//	if(dT[v] + w == dT[u] && abs(dT[v] - dS[u]) < w) ans = sub(ans, mul(toT[v], toS[u]));
//		dd(dT[v]), de(dS[u]);
//		de(ans);
	}
	printf("%d\n", ans);
	return 0;
}



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

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

int main() {
    int n;cin>>n;
    string s;cin>>s;
    
    int a[4][n+1];
    
    rep(i,4){
        rep(j,2){
            a[i][j]=0;
        }
    }
    a[0][0]=1,a[0][1]=1,a[1][0]=1,a[2][1]=1;
    
    
    rep(i,4){
        rep(j,n-1){
            if(s[j+1]=='o'){
                if(a[i][j+1]==1)a[i][j+2]=a[i][j];
                else a[i][j+2] = 1 - a[i][j];
            }
            else{
                if(a[i][j+1]==1)a[i][j+2] = 1 - a[i][j];
                else a[i][j+2] = a[i][j];
            }
        }
        if((s[0]=='o' && a[i][0]==1 && a[i][1]==a[i][n-1] )|| (s[0]=='x' && a[i][0]==1 && a[i][1]!=a[i][n-1]) || (s[0]=='o' && a[i][0]==0 && a[i][1]!=a[i][n-1] )|| (s[0]=='x' && a[i][0]==0 && a[i][1]==a[i][n-1])){
            if((s[n-1]=='o' && a[i][n-1]==1 && a[i][0]==a[i][n-2] )|| (s[n-1]=='x' && a[i][n-1]==1 && a[i][0]!=a[i][n-2]) || (s[n-1]=='o' && a[i][n-1]==0 && a[i][0]!=a[i][n-2] )|| (s[n-1]=='x' && a[i][n-1]==0 && a[i][0]==a[i][n-2])){
         rep(j,n){
             if(a[i][j]==1)cout<<'S';
             else cout<<'W';
         }
         cout<<endl;
         return 0;
        }
        }
    }
    
    cout<<-1<<endl;
	return 0;
}

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

#define ran 2022

int n, m;
vector<int> e[ran];
bool found, on_path[ran];
int T;
int v[ran], dep[ran];
int q[ran], ans[ran], la;

void dfs(int cur, int d) {
	//printf("> %d %d\n", cur, d);
	v[cur] = T;
	on_path[cur] = true;
	dep[cur] = d;
	q[d] = cur;
	
	int aid = -1;
	for(int i=0;i<(int)e[cur].size();i++) {
		int nxt = e[cur][i];
		if(v[nxt] == T && on_path[nxt]) {
			//printf("found %d\n", nxt);
			found = true;
			if (aid < 0 || dep[aid] < dep[nxt])
				aid = nxt;
		}
	}
	if(found) {
		la = 0;
		for(int it = aid;it!=cur;) {
			ans[la++] = it;
			int ma_dep = -1, ma_pos = -1;
			for(int j=0;j<(int)e[it].size();j++) {
				int nit = e[it][j];
				if (v[nit]!=T) continue;
				if (dep[nit]>ma_dep) {
					ma_dep = dep[nit];
					ma_pos = nit;
				}
			}
			it = ma_pos;
		}
		ans[la++] = cur;
		return;
	}
	
	for(int i=0;i<(int)e[cur].size();i++) {
		int nxt = e[cur][i];
		
		if(v[nxt]>=0) continue;
		else {
			dfs(nxt, d+1);
			if (found) return;
		}
	}
	
	on_path[cur] = false;
	dep[cur] = -1;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i=0;i<m;i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		e[x].push_back(y);
	}
	
	found = false;
	memset(v, -1, sizeof v);
	memset(dep, -1, sizeof dep);
	memset(on_path, false, sizeof on_path);
	T = 0;
	for(int i=1;i<=n && !found;i++)
		if (v[i]==-1) {
			T++;
			dfs(i, 1);
		}
		
	if (!found) puts("-1");
	else {
		printf("%d\n", la);
		for(int i=0;i<la;i++)
			printf("%d\n", ans[i]);
	}
	
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
int dis[N];
vector<int> G[N];
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
	}
	memset(dis, -1, sizeof(dis));
	dis[1] = 0;
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(int i = 0; i < G[u].size(); ++i)
		{
			int v = G[u][i];
			if(dis[v] == -1)
			{
				dis[v] = dis[u] + 1;
				q.push(v);
				if(v == n) break;
			} 
		}
	}
	puts((dis[n] != -1 && dis[n] <= 2) ? "POSSIBLE" : "IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 9592
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N_MAX = 100005;
vector<int> edge[N_MAX];
vector<int> len[2];

void dfs(int v, int p, int num, int i){
    len[i][v] = num;
    for(int u : edge[v]){
        if (u == p)continue;
        dfs(u, v, num+1, i);
    }
}

int main(){
    int n, u, v;
    cin >> n >> u >> v;
    for(int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    len[0].resize(n+1);
    len[1].resize(n+1);
    dfs(u, -1, 0, 0);
    dfs(v, -1, 0, 1);
    int ans = 0;
    int eqmin = 1000005;
    for(int j = 1; j <= n; j++){
        if (len[0][j] > len[1][j])continue;
        else if (len[0][j] == len[1][j]){
            eqmin = min(eqmin, len[1][j]);
        }
        else{
            ans = max(ans, len[1][j]-1);
        }
    }
    if (eqmin < 100000)ans = max(ans, eqmin);
    cout << ans << endl;
    return 0;
}

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

string to_string(string s) {
    return '"' + s + '"';
}
string to_string(char ch) {
    string s(1, ch);
    return '\'' + s + '\'';
}
string to_string(const char *s) {
    return to_string((string)s);
}
string to_string(bool b) {
    return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}
 
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

typedef long long int ll;
#define int ll
#define pb          push_back
#define pll         pair<int,int>
#define mll	        map<int,int>
#define F           first
#define S           second
#define lbnd(v,val) lower_bound(v.begin(),v.end(),val)
#define ubnd(v,val) upper_bound(v.begin(),v.end(),val)
#define bs(v,val)   binary_search(v.begin(),v.end(),val)
#define mp          make_pair
#define f(i,x,n)    for(int i=x;i<n;i++)
#define isup		isupper
#define islow 		islower
#define max3(a,b,c)	max(a,max(b,c))
#define endl        "\n"
#define countbits(n)	 __builtin_popcountll(n)
#define all(ar) ar.begin(), ar.end()
#define rall(ar) (ar).rbegin(), (ar).rend()
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX;
const ll N = 2e5 + 10;

typedef vector<vector<ll>> matrix;
typedef vector<ll> vll;


void solve(){
	int n;
	cin>>n;
	vll v(n);
	f(i,0,n){
		cin>>v[i];
	}
	int sum=0;
	vll ans(n,0);
	if(n==2){
		cout<<abs(v[0]-v[1])<<endl;
		return;
	}
	ans[n-2]=abs(v[n-2]-v[n-1]);
	for(int i=n-3;i>=0;i--){
		ans[i] = min(abs(v[i]-v[i+1])+ans[i+1],abs(v[i]-v[i+2])+ans[i+2]);
	}
	// debug(ans);
	cout<<ans[0]<<endl;
}

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

 //    #ifndef ONLINE_JUDGE
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
 //    #endif

    int t=1;
    // cin>>t;
    while(t--){
    	solve();
    }
    return 0;
}


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

int main(){
    string s;
    cin >> s;
    set<char> t;
    for(int i = 0;i < s.size();i++) t.insert(s.at(i));
    if(t.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define sz(x) int(x.size())
using ll = long long;
const ll LLINF = numeric_limits<long long>::max();
const int mod = 1000000007;
const int INF = 1001001001;

int ans=0;
ll N,M,Q;
vector<int> a;
vector<int> b;
vector<int> c;
vector<int> d;

void dfs(vector<int> A){
    if(A.size() == N+1 ){
        
        int ma=0;
        for(int i=0;i<Q;i++){
            if(A[b[i]] - A[a[i]] == c[i]) ma += d[i];
        }
        ans = max(ans,ma);

        return;
    }

    A.push_back(A.back());
    while(A.back()<=M){
        dfs(A);
        A.back()++;
    }
}

int main()
{
    
    
    cin >> N >> M >> Q;
    a = b = c = d = vector<int>(Q); 
    
    

    for(int i=0;i<Q;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }


    dfs(vector<int>(1,1));
    

   
    cout << ans;
    return 0;
}

Measured memory_bytes: 3640