akhauriyash/Code-Regression huggingface dataset:
MOD = 10**9+7

# フェルマーの小定理
def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

N, M, K = map(int, input().split())
ans = 0
# 2点の差がxになる組み合わせは同じ行でM-x通り、2点の行の組み合わせはN*N通り
for x in range(M):
    ans += x * (M-x) * N*N
for y in range(N):
    ans += y * (N-y) * M*M

# 2点以外(K-2)をN*M-2のマスに配置する組み合わせはnCr(N*M-2, K-2)通り
ans *= nCr(N*M-2, K-2, MOD)
ans %= MOD

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t N, L;
  cin >> N >> L;
  vector<int64_t> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  bool flag = false;
  int cnt = 0;
  for(int i=0; i<N-1; i++){
    if(vec.at(i) + vec.at(i+1) >= L){
      flag = true;
      cnt = i+1;
    }
  }
  
  if(flag){
    cout << "Possible" << endl;
    for(int i=1; i<cnt; i++){
      cout << i << endl;
    }
    for(int i=N-1; i>cnt; i--){
      cout << i << endl;
    }
    cout << cnt << endl;
  }
  else{
    cout << "Impossible" << endl;
  }
}

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

int main() {
  int N, M, A, B, C;
  
  cin >> N;
  vector<string> s(N);
  for (int i = 0; i < N; i++) {
    cin >> s.at(i);
  }
  
  cin >> M;
  vector<string> t(M);
  for (int i = 0; i < M; i++) {
    cin >> t.at(i);
  }
  
  C = 0;
  
  for (int a = 0; a < N; a++) {
    A = 0;
    B = 0;
    string Test = s.at(a);
    if (s.at(a) == "0") {
      continue;
    }
    
    else {
      for (int j = 0; j < N; j++) {
        if (s.at(j) == Test) {
          A++;
          s.at(j) = "0";
        }
      }
      
      for (int k = 0; k < M; k++) {
        if (t.at(k) == Test) {
          B--;
        }
      }
    }
    C = max(A + B, C);
  }
  cout << C << endl;
  
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

cnt = 0
for i in range(N):
    if B[i] >= A[i]:
        cnt += A[i]
        B[i] -= A[i]
    else:
        cnt += B[i]
        B[i] = 0
    if B[i] == 0:
        continue
    if B[i] >= A[i+1]:
        cnt += A[i+1]
        A[i+1] = 0
    else:
        cnt += B[i]
        A[i+1] -= B[i]

print(cnt)

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

ll dp[100005];
int main(){

ll n , w ; 
cin >> n >> w;
ll W[n+1] ; ll v[n+1]; 
for(ll i=1 ; i<=n ;i++){
     cin >> W[i] ; cin >> v[i] ;
}

 for(ll i=0 ; i<=w ;i++){
 dp[i] = -1;

 }
 dp[0]= 0; ll  ans =0;
 for(ll i=1 ; i<=n ;i++){
for(ll j=w; j>=0 ; j--){ 

  if(j - W[i] >=0){  if(dp[j-W[i]] >=0){ dp[j] = max(dp[j] , dp[j-W[i]] + v[i]);}}
  ans = max(ans, dp[j]);
}
   
 }

 cout << ans << endl;

}

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

int main() {
  int n;
  cin >> n;
  cout << n / 2 + (n % 2) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long ll;

ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}
ll kai(ll x, ll y, ll m) {
	ll res = 1;
	for (ll i = x - y + 1; i <= x; i++) {
		res *= i; res %= m;
	}
	return res;
}
ll mod_pow(ll x, ll y, ll m) {
	ll res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

ll comb(ll x, ll y, ll m) {
	if (y > x)return 0;
	return kai(x, y, m) * mod_pow(kai(y, y, m), m - 2, m) % m;
}

int n, k, p[5010], a[5010];
bool bl[5010];
ll ans = -1000000000000000000;

signed main() {
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	cin >> n >> k;
	for (int i = 1; i <= n; i++)cin >> p[i];
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= n; i++) {
		fill(bl, bl + n + 1, false);
		int q = i;
		ll cnt = 0;
		ll kk = 0;
		while (kk < k) {
			q = p[q];
			if (bl[q])break;
			kk++;
			cnt += a[q];
			ans = max(ans, cnt);
			bl[q] = true;
		}
		if (kk == k) {
			ans = max(ans, cnt);
			continue;
		}
		int s = k - kk;
		vector<int> vec;
		while (1) {
			vec.push_back(q);
			q = p[q];
			if (q == vec[0])break;
		}
		int x = (int)vec.size();
		int y = s / x;
		for (int j = 0; j < (int)vec.size(); j++) {
			if (j < s%x)cnt += (ll)a[vec[j]] * y;
			else cnt += (ll)a[vec[j]] * (y - 1);
		}
		ans = max(ans, cnt);
		q = vec[s%x];
		for (int j = 0; j < x; j++) {
			cnt += a[q];
			q = p[q];
			ans = max(ans, cnt);
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3720
#include<bits/stdc++.h>
using namespace std;
int main(){
  int c[3][3];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>c[i][j];
    }
  }
  if(c[0][0]-c[0][1]==c[1][0]-c[1][1]&&c[0][0]-c[0][1]==c[2][0]-c[2][1]){
    if(c[0][0]-c[0][2]==c[1][0]-c[1][2]&&c[0][0]-c[0][2]==c[2][0]-c[2][2]){
      if(c[0][0]-c[1][0]==c[0][1]-c[1][1]&&c[0][0]-c[1][0]==c[0][2]-c[1][2]){
        if(c[0][0]-c[2][0]==c[0][1]-c[2][1]&&c[0][0]-c[2][0]==c[0][2]-c[2][2]){
          cout<<"Yes";
          return 0;
        }
      }
    }
  }
  cout<<"No";
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()

using namespace std;

namespace Dump {
#define dump(...) Dump::print(#__VA_ARGS__, __VA_ARGS__)
static std::vector<string> dumpKey;
static string dumpKeyBuf;

void print() { cerr << endl; }
template <class Head, class... Tail> void print(Head &&head, Tail &&... tail) {
  if (dumpKey.empty()) {
    dumpKeyBuf = head;
    dumpKeyBuf.erase(std::remove_if(dumpKeyBuf.begin(), dumpKeyBuf.end(),
                                    [](char c) { return c == ' '; }),
                     dumpKeyBuf.end());

    std::istringstream stream(dumpKeyBuf);
    string field;
    while (std::getline(stream, field, ','))
      dumpKey.push_back(field);

    reverse(dumpKey.begin(), dumpKey.end());
  } else {
    cerr << dumpKey.back() << ":" << head << "  ";
    dumpKey.pop_back();
  }
  Dump::print(std::move(tail)...);
}
}

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef vector<unsigned long long> vull;
typedef pair<int, int> pii; // p.first p.second

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

void solve(long long N, long long M, long long K) {
  if (K % N == 0 && K / N < M) {
    cout << "Yes" << endl;
    return;
  } else if (K % M == 0 && K / M < N) {
    cout << "Yes" << endl;
    return;
  }

  FOR(n, 0, N + 1) {
    FOR(m, 0, M + 1) {
      ll s = M * n + N * m - n * m * 2;
      // dump(n, m, s);
      if (s == K) {
        cout << "Yes" << endl;
        return;
      }
    }
  }
  cout << "No" << endl;
}

int main() {
  ios::sync_with_stdio(false);
  long long K;
  long long N;
  long long M;
  cin >> N;
  cin >> M;
  cin >> K;
  solve(N, M, K);
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
//#define int long long

signed main() {
    int n, q;
    cin >> n >> q;
    vector<priority_queue<int>> que(n);
    int k, t, x;
    rep(i, q) {
        cin >> k >> t;
        if (k == 0) {
            cin >> x;
            que[t].push(x);
        }
        else if (k == 1) {
            if (!que[t].empty())
                cout << que[t].top() << endl;
        }
        else {
            if (!que[t].empty())
                que[t].pop();
        }
    }
}


Measured memory_bytes: 4040
import java.util.Scanner;

public class Main {

	public static void main(String... args) {

		Scanner sc = new Scanner(System.in);
		int[] n = new int[4];
		n[0] = Integer.parseInt(sc.next());
		n[1] = Integer.parseInt(sc.next());
		n[2] = Integer.parseInt(sc.next());
		n[3] = Integer.parseInt(sc.next());
		sc.close();

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

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

				if(i==j) {
					continue;
				}

				for (int k=0; k<4;k++) {

					if(j==k) {
						continue;
					}

					for(int l=0; l<4; l++) {

						if(k==l) {
							continue;
						}

						if(n[i] == 1 && n[j] == 9 && n[k] == 7 && n[l] == 4 ) {
							System.out.println("YES");
							return;
						}
					}


				}
			}
		}

		System.out.println("NO");
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <list>
#include <cmath>
using namespace std;

int main() {
	int k, n;
	cin >> k >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a.at(i);
	}
	int max = a.at(0) + k - a.at(n - 1);
	for (int i = 1; i < n; ++i) {
		max = std::max(max, a.at(i) - a.at(i - 1));
	}
	cout << k - max << endl;

	return 0;
}

Measured memory_bytes: 1024
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

A, B, T = rl()

r = math.floor(T / A)
print(r * B)


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

int main(){
  int A,B;
  string S;
  cin>>A>>B>>S;
  bool finished=false;
  
  if(S.size()!=A+B+1){
    cout<<"No"<<endl;
    finished=true;
  }
  if(finished==false){
  	for(int i=0;i<A+B+1;i++){
      if(i==A){
      	if(S.at(i)!='-'){
    	  cout<<"No"<<endl;
  		  finished=true;
          break;
  		}
      }
      else{
      	if(S.at(i)<48||S.at(i)>57){
      	  cout<<"No"<<endl;
          finished=true;
          break;
      	}
      }
    }
  }
  if(finished==false)
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>

#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF 1<<29
#define ALEN(ARR) (sizeof(ARR) / sizeof((ARR)[0]))
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back
#define _DEBUG(x) cout<<#x<<": "<<x<<endl
#define _DDEBUG(x,y) cout<<#x<<": "<<x<<", "<<#y<<": "<<y<<endl
#define ll long long
#define ull unsigned long long
#define MOD 1000000007

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

    map<char, int> mp;
    string line;
    cin >> line;

    for(char c : line) {
        mp[c]++;
    }

#if DEBUG
    cout << "** RESULT **" << endl; // debug
#endif
	bool test = accumulate(begin(mp), end(mp), false, [](bool value, const map<char, int>::value_type& p){ return value || p.second % 2; });
    cout << (test ? "No" : "Yes") << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

def solve():
    E = list(map(int, list(input())))
    # print(E)

    for i in range(1<<3):
        op = ['-'] * 3
        for j in range(3):
            if i >> j & 1:
                op[j] = '+'

        f = '{}{}{}{}{}{}{}'.format(E[0], op[0], E[1], op[1], E[2], op[2], E[3])
        e = eval(f)
        if e == 7:
            print(f + '=7')
            return



if __name__ == '__main__':
    solve()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=998244353;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    int n,s;
    cin>>n>>s;
    int a[n];
    rep(i,n)cin>>a[i];
    int dp[s+1]={};
    dp[0]=1;
    ll ans=0;
    rep(i,n){
        for(int j=s-1;j>0;--j){
            if(j+a[i]<=s){
                dp[j+a[i]]=(dp[j+a[i]]+dp[j])%mod;
            }
        }
        if(a[i]<=s){
            dp[a[i]]=(dp[a[i]]+i+1)%mod;
        }
        ans=(ans+dp[s])%mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    string s;
    cin >> s;
    string ans;
    rep(i,s.size()){
        if(s[i] == 'B'){
            if(ans.size() != 0){
                ans.erase(ans.end()-1);
            }
        }else ans.pb(s[i]);
    }
    cout << ans << endl;
    
    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://yahoo-procon2019-qual.contest.atcoder.jp/tasks/yahoo_procon2019_qual_d
// rm -r -f test;oj dl http://abc043.contest.atcoder.jp/tasks/abc043_b

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

#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;

using namespace std;




void one_case() {
    int x, a, b;
    cin >> x >> a >> b;
    cout << (x - a) % b << "\n";
}


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


    int t = 1;
//    cin >> t;
    while (t--) {
        one_case();
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  int n;
  cin>>n;
  vector<int> as(n),bs(n),cs(n);
  for(int i=0;i<n;i++) cin>>as[i];
  for(int i=0;i<n;i++) cin>>bs[i];
  for(int i=1;i<n;i++) cin>>cs[i];

  int ans=0;
  for(int i=0;i<n;i++) ans+=bs[i];
  for(int i=0;i+1<n;i++)
    if(as[i]+1==as[i+1]) ans+=cs[as[i]];

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1000000007;

int main(){
    int N; cin >> N;
    string s[2];
    cin >> s[0] >> s[1];

    ll ans;
    int pos;
    char preType;


    if(s[0][0] == s[1][0]){
        pos = 1;
        ans = 3;
        preType = 'a';
    } else{
        pos = 2;
        ans = 6;
        preType = 'b';
    }

    while(pos < N){
        if(preType == 'a'){
            if(s[0][pos] == s[1][pos]){
                ans = ans*2%mod;
                pos++;
            } else {
                ans = ans*2%mod;
                pos += 2;
                preType = 'b';
            }
        } else {
            if(s[0][pos] == s[1][pos]){
                pos++;
                preType = 'a';
            } else {
                pos += 2;
                ans = ans*3%mod;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define mkt make_tuple
#define lP pair<ll, ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;

int n, q, s, t, x, u;
iP a[1<<18];
bool b;

int update(int s, int t, int x, int k, int l, int r, int i) {
	if (t < l || r < s)return 0;
	else if (s <= l&&r <= t) {
		a[k] = mkp(x, i);
		return 0;
	}
	else {
		update(s, t, x, k * 2, l, (l + r) / 2, i);
		update(s, t, x, k * 2 + 1, (l + r) / 2 + 1, r, i);
		return 0;
	}
}
int find(int x) {
	int y, z = -2;
	x += u;
	while (x) {
		if (z < a[x].second) {
			y = a[x].first;
			z = a[x].second;
		}
		x /= 2;
	}
	return y;
}


int main(){
	cin >> n >> q;
	for (int i = 1;; ++i) {
		if ((1 << i) / n >= 2) {
			u = (1 << i - 1);
			break;
		}
	}
	for (int i = 1; i != u * 2; ++i)
		a[i] = mkp(intmax, -1);
	for (int i = 0; i != q; ++i) {
		cin >> b >> s;
		if (b) {
			cout << find(s) << endl;
		}
		else {
			cin >> t >> x;
			update(s, t, x, 1, 0, u - 1, i);
		}
	}
	return 0;
}



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

int main() {

int N;
cin >>N;

int T;
cin >>T;

int c;
int t;

int ans=10000;//暫定の答え

for(int i=1; i<=N; i++){

cin >>c;

cin >>t;

if(t<=T && c<=ans){ans=c;}
}

if(ans<10000){cout <<ans;}
if(ans==10000){cout<< "TLE";}


}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <ctime>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
	ll n,q; cin >> n >> q;
	vl a(n); rep(i,n) cin >> a[i];
	vpl x(q);
	rep(i,q){
		cin >> x[i].first;
		x[i].second = i;
	}
	sort(rall(x));
	ll k=0;
	vl odds(n+1,0);
	vl evens(n+1,0);
	rep(i,n){
		if(i & 1){
			if(i > 1) evens[i+1] = evens[i-1] + a[i];
			else evens[i+1] = a[i];
		}else{
			if(i > 0) odds[i+1] = odds[i-1] + a[i];
			else odds[i+1] = a[i];
		}
	}
	ll sum = a.back();
	vl ans(q);
	rep(i,q){
		while(1){
			ll K = k+1;
			if(K > (n+1)/2) break;
			if(x[i].first >= a[n-1-K]) break;
			ll d = n - K - 1 - (lower_bound(all(a),x[i].first - (a[n-1-K] - x[i].first)) - a.begin());
			if(d >= K) sum += a[n-1-K], k++;
			else break;
		}
		ll id = n-k*2-2;
		if(id <= 0) ans[x[i].second] = sum;
		else{
			if(odds[id] == 0) ans[x[i].second] = evens[id] + sum;
			else ans[x[i].second] = odds[id] + sum;
		}
	}
	rep(i,q) cout << ans[i] << "\n";
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
 
template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
    out << '(' << p.first << ',' << p.second << ')';
        return out;
}
 
template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
    in >> p.first >> p.second;
        return in;
}
 
template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
    for (T &x : v)
        in >> x;
    return in;
}
 
template <class T>
ostream& operator << (ostream& out, const vector<vector<T> > &v)
{
    for (const vector<T> &x : v)
        out << x << '\n';
    return out;
}
 
template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
    for (const T &x : v)
        out << x << ' ';
    return out;
}
 
template <class T>
ostream& operator << (ostream& out,const set<T> &s)
{
    for (const T &x : s)
        out << x << ' ';
    return out;
}
 
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll > ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define sz(x) (ll)(x).size()
#define tr1(x) cerr << #x << ": " << x << nl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << nl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<nl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<nl
#define epsilon 0.00000001L
#define inf 9999999999999999ll// ~ 10^16
#define nl "\n"
#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()
#define fast()  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mod 1000000007ll
#define modulo 998244353ll
ll power(ll a,ll b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}

int main()
{
    fast();
    ll n;
    cin>>n;
    
    ll count=0;
    //include cases where c is zero
    for(ll a=1;a<=n;a++)
    {
        count+=n/a;
    }

    for(ll i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            count--;
            if(i*i!=n)
                count--;
        }
    }
    cout<<count<<nl;
}


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

int main() {
    int num;
    string i, j;
    cin >> i>>j;
    i+=j;
    num = sqrt(atoi(i.c_str()));
    if (pow(num, 2)==atoi(i.c_str())) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    string S,T;
    cin>>S>>T;
    int n,m;
    n=S.size();
    m=T.size();
    int cmax=0;
    for(int i=0;i<=n-m;i++){
        int cnt=0;
        rep(j,m){ 
            if(S[i+j]==T[j]) cnt++;
        }
        cmax=max(cmax,cnt);
    }
    cout<<m-cmax<<endl;
    return 0;
}

Measured memory_bytes: 3640
#include<stdio.h>
  
int main(void){
    /* 変数の宣言 */
  int N=0,Ni[20],max=0,result=0;
  scanf("%d", &N);

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

  for(int i=0;i<N;i++){
      if(Ni[i]>=max){
          max=Ni[i];
          result++;
      }
  }
  printf("%d",result);
  return 0;
}

Measured memory_bytes: 128
var A:array[1..5] of byte;
    i,j,tmp:byte;
begin
 readln(A[1],A[2],A[3]);
 for i:=1 to 2 do 
  for j:=i+1 to 3 do 
   if A[i]>A[j] then 
    begin
     tmp:=A[i];A[i]:=A[j];A[j]:=tmp;
    end;
  writeln(A[2]-A[1]+A[3]-A[2]); 
end.

Measured memory_bytes: 128
// abc145_c
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

struct Point {
    double x, y;
    explicit Point(double x=0, double y=0): x(x), y(y) {}
    Point& operator+=(const Point& v){ x += v.x; y+= v.y; return *this;}
    Point operator+(const Point& v) const{return Point(*this) += v;}
    Point& operator-=(const Point& v){x -= v.x; y-= v.y; return *this;}
    Point operator-(const Point& v) const{return Point(*this) -= v;}
    Point& operator*=(double s){x *= s; y *= s; return *this;}
    Point operator*(double s) const{return Point(*this) *= s;}
    Point& operator/=(double s){x /= s; y /= s; return *this;}
    Point operator/(double s) const{return Point(*this) /= s;}
    double dot(const Point& v) const {return x*v.x + y*v.y;}        /* 内積 */
    double cross(const Point& v) const {return x*v.y - v.x*y;}      /* 外積 */
    double norm2() const {return x*x + y*y;}                        /* ノルムの二乗*/
    double norm() const {return sqrt(norm2());}                     /* ノルム */
    int quadrant() const { if(y > 0) return x>0 ? 1:2; else return x>0 ? 4:3;} /* 象限判定 */
    Point rot(double theta) {return Point(cos(theta) * x - sin(theta) * y, sin(theta) * x + cos(theta) * y);} // 回転
    Point rot90() {return Point(-y, x);} // 90度回転
};
ostream& operator<<(ostream& os, const Point& v) {os<<"("<<v.x<<","<<v.y<<")"; return os;}
istream& operator>>(istream& is, Point& v){ is >> v.x >> v.y; return is;}


int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;
    vector<Point> points(N);
    REP(i, N){
        cin >> points[i];
    }

    vector<int> factorial(N+1);
    factorial[0] = 1;
    for (int i = 1; i <= N; ++i) { factorial[i] = factorial[i-1] * i;}

    double ans = 0;
    REP(i, N) REPN(j, i+1, N){
        ans += (points[i] - points[j]).norm();
    }
    ans = ans * 2 * (N - 1) * factorial[N-2] / factorial[N];
    print(ans);


    return 0;
}


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

int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  
  int tmp = a;
  a = b;
  b = tmp;
  tmp = a;
  a = c;
  c = tmp;
  cout << a << " " << b << " " << c << endl;
}

Measured memory_bytes: 256
import numpy as np
from functools import reduce
from operator import add,sub,mul,truediv
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))

x = a[0]

for i in range(1,len(a)):
    x = (x*a[i])//gcd(x,a[i])

x = x-1

ans = 0
for i in range(len(a)):
    ans = ans + x%a[i]

print(ans)

Measured memory_bytes: 15236
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main(){
  string s;
  while(cin>>s,s!="0"){
    int tbl[11]={};
    int n=s.length();
    int ans=0,sum=0;
    tbl[0]=1;
    for(int i=0;i<n;++i){
      if(i&1) sum-=s[i]-'0';
      else sum+=s[i]-'0';
      sum = (sum+11)%11;
      ans+=tbl[sum];
      if(i+1<n && s[i+1]!='0') tbl[sum]++;
    }
    cout << ans << endl;
  }
  return 0;
}

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



int sc1(){int x; scanf("%d",&x); return x;}

long long sc2(){long long x;scanf("%lld",&x);return x;}

#define  gcd(a,b)         __gcd(a,b)
#define  lcm(a,b)         (a*b)/gcd(a,b)
#define  Int              sc1()
#define  LL               sc2()
#define  For(n)           for(int i=0;i<n;i++)
#define  Forj(n)          for(int j=0;j<n;j++)
#define  Fork(n)          for(int k=0;k<n;k++)
#define  For1(n)          for(int i=1;i<=n;i++)
#define  ll               long long
#define  vi               std::vector<int>
#define  vll              std::vector<ll>
#define  qui              qu
#define  pb               push_back
#define  mpsi             std::map<string, int>







int main()
{
	//freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n=Int;

    int arr[n+1];

    For(n) arr[i]=Int;
    int pt = n-1;
    int ans=0;
    for(int i=n-1;i>=1;i--)
    {
    	if(arr[i]>arr[i-1])
    	{
    		ans=max(ans,pt-i);
    		pt=i-1;
    	}
    }
    ans=max(ans,pt-0);
    cout<<ans<<endl;
    
    return 0;
}




Measured memory_bytes: 640
N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            break
        dp[i] = min(dp[i], dp[i - j] + abs(H[i - j] - H[i]))
print(dp[-1])

Measured memory_bytes: 85224
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
typedef long long ll;
int N;
ll X,Y;
ll a[2000];
ll last;
ll T;
bool memo[2010][2];
bool vis[2010][2];
bool Xwin(int y,bool xturn){
	if(y>=0 && vis[y][xturn]) return memo[y][xturn];
	vis[y][xturn] = 1;
 
	if(xturn){
		for(int nx = y+1;nx<N-1;nx++){
			if(abs(a[nx]-last) < T) continue;
			if(Xwin(nx,0)) return memo[y][xturn] = 1;
		}
		return memo[y][xturn] = 0;
	}else{
		for(int nx = y+1;nx<N-1;nx++){
			if(abs(a[nx]-last) >= T) continue;
			if(!Xwin(nx,1)) return memo[y][xturn] = 0;
		}
		return memo[y][xturn] = 1;
	}
}
bool can(ll t){
	rep(i,2010) rep(j,2) vis[i][j] = 0;
	T = t;
	if(abs(Y-last)>=t) return 1;
	return Xwin(0,-1);
}
int main(){
	cin>>N>>X>>Y;
	rep(i,N) cin>>a[i];
	last = a[N-1];
	ll ub = 1e9, lb = 0;
	while(ub-lb>1){
		ll m = (ub+lb)/2;
		if(can(m)) lb = m;
		else ub = m;
	}
	cout<<lb<<endl;
}

Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


# inputna
n = int(input())
s = input()
if n>=3200:
    print(s)
else:
    print("red")

Measured memory_bytes: 61296
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define speed                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define ll long long
#define pb push_back
#define mem1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define endl "\n"
#define mod 1000000007
#define mod1 998244353
#define ff first
#define ss second
#define MAX 500005
#define N 10004
#define INF 1000000009
#define all(v) v.begin(), v.end()
#define sbit(a) __builtin_popcount(a)
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> ppl;
typedef map<ll, ll> mpll;
typedef map<vector<ll>, ll> mpvl;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
 
    x = x % p;
 
    if (x == 0)
        return 0;
    while (y > 0)
    {
 
        if (y & 1)
            res = (res * x) % p;
 
        y = y >> 1;
        x = (x * x) % p;
    }
 
    return res;
}
void solve()
{
 
    ll n, x, m;
    cin >> n >> x >> m;
    ll ans = x;
    ll t = x * x;
    ll c = 0;
    map<ll, ll> mp;
    n--;
    ll s[m + 1];
    mem0(s);
    ll tans = 0;
    ll tmp;
    for (ll i = 1; i <=m + 1; i++)
    {
        ll md = t % m;
        if (!mp.count(md))
        {
            tans += md;
            t = md * md;
        }
        else
        {
            c = i - mp[md];
            tmp = mp[md];
            break;
        }
        mp[md] = i;
        s[i] = tans;
    }
    if (mp.count(0))
    {
        ans += tans;
        cout << ans << endl;
        return;
    }
    tmp--;
    n -= tmp;
    ll div = n / c;
    ll md = n % c;
    ans += (div * (s[c + tmp] - s[tmp]));
    ans += s[tmp];
    ans += s[tmp + md] - s[tmp];
    cout << ans << endl;
}
int main()
{
    speed;
    ll kk;
    kk = 1;
    //cin >> kk;
    while (kk--)
    {
 
        solve();
    }
 
    return 0;
}

Measured memory_bytes: 7496
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PSET(x,y) fixed<<setprecision(y)<<x
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int,int>
#define pid pair<int,double>
#define vi vector<int>
#define ff first
#define ss second
#define int long long int
#define ull unsigned long long
#define PI 3.14159265
#define SIZE 200010
#define MOD 1000000007
#define BIG 998244353
#define s(t) scanf("%d",&t)
#define p(t) printf("%d\n",t)
#define mii map<int,int>
#define tc int tcs;cin>>tcs;while(tcs--)
#define set_bit __builtin_popcount
#define MSET(table,i) memset(table, i, sizeof(table))
int toint(const string &s) {stringstream ss; ss << s; int x; ss >> x; return x;}
string tostring ( int number ){stringstream ss; ss<< number; return ss.str();}
 
int32_t main()
{
    int h1,m1,h2,m2,k;
  cin>>h1>>m1>>h2>>m2>>k;
  int start = h1*60+m1;
  int end = h2*60+m2;
  
  cout<<end-start-k;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX 200100

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> g[n];
    for (int i=0; i<n-1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    queue<int> q;
    q.push(0);
    int d[n];
    fill(d, d+n, MAX);
    d[0] = 0;
    int k;
    while (q.size() > 0) {
        k = q.front(); q.pop();
        for (size_t l=0; l<g[k].size(); l++) {
            if (d[g[k][l]] == MAX) {
                d[g[k][l]] = d[k] + 1;
                q.push(g[k][l]);
            }
        }
    }
    q.push(k);
    fill(d, d+n, MAX);
    d[k] = 0;
    while (q.size() > 0) {
        k = q.front(); q.pop();
        for (size_t l=0; l<g[k].size(); l++) {
            if (d[g[k][l]] == MAX) {
                d[g[k][l]] = d[k] + 1;
                q.push(g[k][l]);
            }
        }
    }
    printf("%s\n", d[k]%3 != 1 ? "First" : "Second");
    return 0;
}

Measured memory_bytes: 13556
#include <stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <cctype>

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i,l,n) for(int (i)=(int)(l);(i)<(int)(n);(i)++)
//#define d_arr(arr, h, w) rep(i,( (arr).size() ) ){ cout << "["; rep(j,(w) ) { cout << (arr)[i][j] << ", "; } cout << "]" << endl;}
#define d_arr(arr, type) rep(i, sizeof(arr)/sizeof(arr)[0] ){ cout << "["; rep(j,sizeof(arr[0])/sizeof(type)) { cout << (arr)[i][j] << ", "; } cout << "]" << endl;}


typedef pair<int ,int> P;

class Coordinates
{
    public:
        int x;
        int y;

        Coordinates(){ x = 0; y = 0;};
        Coordinates(int a, int b) { x = a; y = b;}

        Coordinates operator+(Coordinates p)
        {
            Coordinates tmp;
            tmp.x = x + p.x;
            tmp.y = y + p.y;
            return tmp;
        }

        friend bool operator==(const Coordinates a, const Coordinates b)
        {
            return (a.x == b.x && a.y == b.y);
        }
        friend bool operator<(const Coordinates a, const Coordinates b)
        {
            return (a.x < b.x && a.y < b.y);
        }
        friend bool operator<=(const Coordinates a, const Coordinates b)
        {
            return (a.x <= b.x && a.y <= b.y);
        }
};

typedef Coordinates Coo;

int max(int a, int b);



Coo ld[4] = { Coo(0,-1), Coo(1,0), Coo(0,1), Coo(-1,0) };
Coo rd[4] = { Coo(0,-1), Coo(-1,0), Coo(0,1), Coo(1,0) };

//テ・ツ渉づ・ツ環?ィツ??ヲツ閉ーテ」ツ??・ツ閉湘ゥツ。ツ古ヲツ閉ー
int M,N;


int main()
{
    cin >> M >> N;
    vector< vector<int> > ansers;

    int max=0;
    int max_i=0;
    rep(i, M)
    {
        vector<int> tmp;
        int sum =0;
        rep(j, N)
        {
            int x;
            cin >> x;
            tmp.push_back(x);
            sum += x; 
        }
        ansers.push_back(tmp);
        if( max < sum ) { max = sum; max_i = i;}// cout << "sum = " <<  sum << "max_i = " << j <<endl;  }
    }


    cout << max << endl;
}


int max(int a, int b) 
{
    if ( a > b)  { return a; }
    else         { return b; }
}

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

const ll MOD = 1e9+7;

int main() {
  ll N;
  cin >> N;
  if (N == 1) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 1, temp = 1, temp2 = 1;;
  rep(i, N) ans = (ans * 10) % MOD;
  rep(i, N) temp = (temp * 9) % MOD;
  rep(i, N) temp2 = (temp2 * 8) % MOD;
  ans -= temp;
  if (ans < 0) ans += MOD;
  ans -= temp;
  if (ans < 0) ans += MOD;
  ans += temp2;
  ans %= MOD;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3536
//C Slimes
#include "bits/stdc++.h"
using namespace std;

int main()
{
  string s;
  int n,ans;
  cin>>n>>s;
  ans=n;
  for(int i=0;i<n-1;i++)
  {
    if(s.at(i+1)==s.at(i))
    {
      ans--;
    }
  }
  cout<<ans<<endl;
}


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

int main() {
  ll a, b;
  ll v, w;
  ll t;
  cin >> a >> v;
  cin >> b >> w;
  cin >> t;

  ll dv = v - w;
  if(dv <= 0) {
    cout << "NO" << endl;
    return 0;
  }
  ll dd = abs(a - b);
  if(dv * t < dd) {
    cout << "NO" << endl;
    return 0;
  }
  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
  
int main() {
  string S;
  cin >> S;

  vector<string> weather{"Sunny", "Cloudy", "Rainy", "Sunny"};
  int i = find(weather.begin(), weather.end(), S) - weather.begin();
  
  cout << weather[i+1] << endl;
}

Measured memory_bytes: 256
from itertools import combinations


N,M,X=map(int,input().split())

mtable = [None]*N
cs = []
for n in range(N):
    aa = list(map(int,input().split()))
    c = aa.pop(0)
    cs.append(c)
    ms = aa
    mtable[n] = ms
    

# print(mtable)
idxes = list(range(N))

prices = []
for i in range(1, N+1):
    for c in combinations(idxes, i):
        sums = [0]*M
        for idx in c:
            for i, m in enumerate(mtable[idx]):
                sums[i] += m
        if all(map(lambda x:x >= X, sums)):
            price = 0
            for idx in c:
                price += cs[idx]

            prices.append(price)
if prices == []:
    print(-1)
else:
    print(min(prices))

Measured memory_bytes: 9336
#include <iostream>
using namespace std;
 
int main(){
    int a,b; 
    for(int i = 0; i < 100; i++){
        cin >> a >> b;
        int c = 0;
        if(a == 0 && b == 0) break;
        int l,m,n;
        for(l = 0; l < a; l++){
            for(m = 0; m < l; m++){
                for(n = 0; n < m; n++){
                    if(l + m + n == b - 3){
                        c++;
                    }
                }
            }
        }
        cout << c << endl;
    }
    return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
#define ALL(x) x.begin(),x.end()
#define P pair<int,int>
#define mod 1000000007

int main() {
  int a, b;
  cin >> a >> b;
  rep(i, max(a, b)) {
    cout << min(a, b);
  }
  cout << endl;

  return 0;
}


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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = (1LL<<31)-1;
const int mod = 1e9 + 7;

struct SegmentTree {
  vector<int> data, lazy;
  int sz;
  SegmentTree(int n) {
    sz = 1; while(sz < n) sz <<= 1;
    data.resize(2*sz-1, inf);
    lazy.resize(2*sz-1, -1);
  }
  void lazy_evaluate(int k, int l, int r) {
    if(~lazy[k]) {
      data[k] = lazy[k];
      if(r - l > 1) {
	lazy[2*k+1] = lazy[k];
	lazy[2*k+2] = lazy[k];
      }
      lazy[k] = -1;
    }
  }
  void update(int a, int b, int x, int k, int l, int r) {
    lazy_evaluate(k, l, r);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      lazy[k] = x;
      lazy_evaluate(k, l, r);
      return;
    }
    update(a, b, x, 2*k+1, l, (l+r)/2);
    update(a, b, x, 2*k+2, (l+r)/2, r);
  }
  void update(int a, int b, int x) {
    update(a, b, x, 0, 0, sz);
  }
  int query(int i, int k, int l, int r) {
    lazy_evaluate(k, l, r);
    if(r - l == 1) return data[k];
    if(l <= i && i <= r) {
      if(i < (l+r)/2) return query(i, 2*k+1, l, (l+r)/2);
      else return query(i, 2*k+2, (l+r)/2, r);
    }
    return inf;
  }
  int query(int i) {
    return query(i, 0, 0, sz);
  }
};

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n, q;
  cin >> n >> q;
  SegmentTree seg(n);
  rep(i, q) {
    int com, s, t, x;
    cin >> com >> s;
    if(com == 0) cin >> t >> x, seg.update(s, t+1, x);
    else cout << seg.query(s) << endl;
  }

  return 0;
}

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

int main(){
  ll n;
  cin >> n;
  vector<ll> A(n);
  rep(i,n) cin >> A[i];
  sort(A.begin(),A.end());
  ll count = 1;
  bool flag = false;
  rep(i,n-1){
    if(A[i] == A[i+1] && !flag){
      --count;
      flag = true;
    }
    else{
      ++count;
      flag = false;
    }
  }
  cout << count << endl;
  return 0;
}


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

int main() {
  string s;
  cin >> s;
  if(s.at(2) == s.at(3) && s.at(4) == s.at(5)){
    cout << "Yes";
  }else{
    cout << "No";
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{ 
    int n,k;
    cin>>n>>k;
    int cnt=0;
    int h=0;
    for(int i;i<n;i++)
    {
        cin>>h;
        if(h>=k){cnt++;}
    }
     cout<<cnt<<endl;
    return 0;
}


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

using namespace std;
string X,N;
int A[2000010]{};
bool B[2000010]{};
vector <int> C;
int main()
{
  cin>>N>>X;
  int count=0;
  for(int i=0;i<N.length();i++){
    if(N[i]!=X[i])count++;
  }
  cout<<count;
  
  return 0;
}





Measured memory_bytes: 3896
#include <cctype>
#include <iostream>
#include <cmath>
#include <locale>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>

typedef long long ll;

using namespace std;

int main() {
    string text;
    getline(cin, text);
    for (int i = 0; i < text.length(); i++) {
        if (isupper(text[i])) {
            text[i] = tolower(text[i]);
        }
        else if (islower(text[i])) {
            text[i] = toupper(text[i]);
        }
    }
    cout << text << endl;
    return 0;
}



Measured memory_bytes: 3148
k = int(input())

if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    i = 1
    m = 7 % k
    while True:
        if m == 0:
            print(i)
            break
        m = (10 * m + 7) % k
        i += 1


Measured memory_bytes: 9120
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val w = sc.nextLine()
  println(cntWords(sc.next(), w, makeCounter))

  def cntWords(start: String, cntWord: String, counter: () => Int): Int = {
    start match {
      case "END_OF_TEXT" => counter() - 1
      case _ =>
        if (start.toLowerCase() == cntWord.toLowerCase()) counter()
        cntWords(sc.next(), cntWord, counter)
    }
  }

  def makeCounter: () => Int = {
    var cnt = 0
    () => cnt += 1; cnt
  }
}

Measured memory_bytes: 44988
#include"bits/stdc++.h"
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
using Pl = pair<ll, int>;


void Main() {
	int k; string s;
	cin >> k >> s;
    int n = s.size();
    if(n <= k) {
    	cout << s << endl;
        return;
    }else{
    	s = s.substr(0, k);
    	cout << s;
    	cout << "..." << endl;
	}
    return;
}

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


Measured memory_bytes: 3652