akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define mx 200005
#define ll long long
ll arr[mx] = {0};
ll contribute[mx] = {0};
int in[mx];
int main()
{	
	ios_base::sync_with_stdio(0);

	int n,a;
	cin>>n;
    for(int i=1; i<=n; i++){
    	cin>>a;
    	arr[a]++;
    	in[i] = a;
    }
    ll sum = 0;
    for(int i=1; i<=n; i++){
    	if(arr[i]){
	    	ll add = arr[i];
	    	add*=(add-1);
	    	add/=2;
	    	sum+=add;
	    	contribute[i]+=add;
		}
    }
    for(int i=1; i<=n; i++){
    	ll cont = contribute[ in[i] ];
    	ll ans = sum - cont;
    	ll add = arr[ in[i] ]-1;
    	add*=(add-1);
    	add/=2;
    	ans+=add;
    	cout<<ans<<endl;
    } 
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
using V = vector<ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

void solve_abc_a() {
	//ll k, a, b;
	string s, t;
	ll ans = 0;
	//string ans = "NG";

	cin >> s >> t;

	rep(i, s.size()) {
		if (s[i] == t[i]) ans++;
	}

	cout << ans << "\n";

	return;
}

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

	solve_abc_a();

	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
    public static void main(String[] args){
        FastScanner sc = new FastScanner();
        int a = sc.nextInt();
        String operator = sc.next();
        int b = sc.nextInt();
        int result = 0;
        if(operator.equals("+")){
            result = a + b;
        }else{
            result = a - b;
        }
        System.out.println(result);

    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            }else{
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }else if(b == -1 || !isPrintableChar(b)){
                    return minus ? -n : n;
                }else{
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
    }
}

Measured memory_bytes: 20564
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin>>n>>k;
  vector<int> sunuke(n,0);
  for(int i=0; i<k; i++){
    int a;
    cin>>a;
    for(int j=0; j<a; j++){
      int b;
      cin>>b;
      sunuke.at(b-1)=1;
    }
  }
  int ans=0;
  for(int i=0; i<n; i++){
    if(sunuke.at(i)==0)ans++;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3632
from fractions import*
N=int(input())
# 4hnw=Nnw+Nhw+Nhn
for h in range(1,3501):
 for n in range(h,3501):
  x=4*h*n-N*n-N*h
  if x>0 and N*h*n%x==0:print(h,n,N*h*n//x),quit()

Measured memory_bytes: 5176
N, M, C = gets.split.map(&:to_i)

bm = gets.split.map(&:to_i)

ans = 0
N.times {
  am = gets.split.map(&:to_i)
  sum = 0
  (0..(M-1)).each { |i| sum += am[i] * bm[i] }
  ans += 1 if sum + C > 0
}

puts ans


Measured memory_bytes: 1788
n,d = map(int,input().split())
x = [0 for _ in range(d)]*n
for i in range(n):
    x[i] = [int(_) for _ in input().split()]
res = 0
sq = [i*i for i in range(10000)] 
for i in range(n):
    for j in range(n):
        if i != j:
            if sum([(x[i][k]-x[j][k])**2 for k in range(d)]) in sq:
                res += 1
print(res//2)

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  if(A + B > C + D){
    cout << "Left" << endl;
  }
  else if(A + B == C + D) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}
  

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n; cin>>n;
    vector<double> x(n), y(n);
    for(int i=0; i<n; i++) cin>>x[i]>>y[i];

    vector<int> v(n);
    iota(v.begin(), v.end(), 0);

    double ans = 0;
    do{
        for(int i=0; i<n-1; i++){
            ans += sqrt((x[v[i]] - x[v[i+1]]) * (x[v[i]] - x[v[i+1]]) + (y[v[i]] - y[v[i+1]]) * (y[v[i]] - y[v[i+1]]));
        }

    }while(next_permutation(v.begin(), v.end()));

    for(int i=1; i<=n; i++){
        ans /= i;
    }

    printf("%.10f\n", ans);

    return 0;
}


Measured memory_bytes: 256
use proconio::input;

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [u64; n],
    }

    let mut t = FenwickTree::from_vec(a);
    for _ in 0..q {
        input! { f: usize };
        if f == 1 {
            input! { l: usize, r: usize }
            println!("{}", t.sum(l, r));
        } else {
            input! { p: usize, x: u64 }
            t.add(p, x);
        }
    }
}

struct FenwickTree<T> {
    v: Vec<T>,
}

use std::ops::AddAssign;
use num::{Integer, zero};

impl<T: Copy + AddAssign + Integer> FenwickTree<T> {
    fn new(n: usize) -> Self {
        Self {
            v: vec![zero(); n],
        }
    }

    fn from_vec(v: Vec<T>) -> Self {
        let n = v.len();
        let mut t = Self::new(n);
        for i in 0..n {
            let v = t.v[i] + v[i];
            t.v[i] = v;
            let p = i + ((i + 1) & (i + 1).wrapping_neg());
            if p < n {
                t.v[p] += v;
            }
        }
        t
    }

    fn add(&mut self, i: usize, v: T) {
        let mut i = i + 1;
        while i <= self.v.len() {
            self.v[i - 1] += v;
            i += i & i.wrapping_neg();
        }
    }

    fn sum(&self, l: usize, r: usize) -> T {
        self.get(r) - self.get(l)
    }

    fn get(&self, mut i: usize) -> T {
        let mut v = zero();
        while i > 0 {
            v += self.v[i - 1];
            i -= i & i.wrapping_neg();
        }
        v
    }
}


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

const int INF = 1e9 + 5;
int main(){
	
	int H, n;
	cin>>H>>n;
	vector<int> dp(H+1, INF);
  	dp[0] = 0;
	while(n--){
		int val, cost;
		cin>>val>>cost;
		for(int i=0;i<=H;i++){
			int j=min(H, i+val);
			dp[j] = min(dp[j], dp[i] + cost);
		}
	}
	cout<<dp[H]<<endl;	
	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>
#define len length()
#define sz size()
#define rng(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) rng(i, 0, n)
#define srt(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define vi(a, n) vector<int> a(n)
#define vs(a, n) vector<string> a(n)
#define vc(a, n) vector<char> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define erc(S, i) S.erase(S.begin() + i)
#define ers(S, i, j) S.erase(S.begin() + i, S.begin() + j)
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)
using namespace std;

int main(){
    int D;
    cin >> D;
    string ans;
    if(D == 25) ans = "Christmas";
    else if(D == 24) ans = "Christmas Eve";
    else if(D == 23) ans = "Christmas Eve Eve";
    else if(D == 22) ans = "Christmas Eve Eve Eve";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
 public static void main(String[] args){
  Scanner sc = new Scanner(System.in);
  int k = sc.nextInt();
  int s = sc.nextInt();
  int result=0;
  for(int x=0;x<=k;x++){
   for(int y=0;y<=k;y++){
if(x+y<=s&&x+y+k>=s){
result++;
}
} 
}
System.out.println(result);
  }
}

Measured memory_bytes: 9812
-- https://github.com/minoki/my-atcoder-solutions
import Data.Char (isSpace)
import Data.List (unfoldr)
import Control.Monad (forM_)
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as BS

main = do
  [n,k] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  -- 1 <= n <= 300, 1 <= k <= 10^5
  xs <- U.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  -- 1 <= a1 < a2 < ... < an <= k
  let vec = U.create $ do
        vec <- UM.new (k + 1)
        -- vec ! i: 双方が最善を尽くした時に現在の手番の人が勝つなら True
        UM.write vec 0 False
        forM_ [1..k] $ \i -> do
          result <- U.or <$> U.mapM (\x -> not <$> UM.read vec (i - x)) (U.takeWhile (<= i) xs)
          UM.write vec i result
        return vec
  putStrLn (if U.last vec then "First" else "Second")


Measured memory_bytes: 1148
/*g++ main.cpp -o main.out*/
/*./main.out*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int main()
{
    LL n,k;
    cin>>n>>k;
    cout<<min(n%k,abs(k-n%k))<<endl;
    return 0;
}


Measured memory_bytes: 256
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1001001001
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n+1)
using namespace std;


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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str;
    cin>>str>>a;
    vector<ll> v(n);
    vector<ll> w(n);
    if(a==1&&str[0]=='1') cout<<'1'<<endl;
    else {
        for(ll i=0;i<a;i++){
            sum=i;
            f=1;
            if(str[i]!='1') break;
        }
        if(f==1)cout<<str[sum]<<endl;
        else cout<<str[0]<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,m,l;cin>>n>>m>>l;

  vector<vector<pair<int,int>>> d(n,vector<pair<int,int>>(n,{1e9,1e9}));

  rep(i,m)
  {
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    if(c>l)continue;
    d[a][b]={0,c};
    d[b][a]={0,c};
  }
  rep(i,n)
  {
    d[i][i]={0,0};
  }
  // nは頂点数
  rep(x,2)for (int i = 0; i < n; i++)      // 経由する頂点
    for (int j = 0; j < n; j++)    // 開始頂点
     for (int k = 0; k < n; k++)  // 終端
     {
       int nf,ns;
       if(d[j][i]>=(pair<int,int>){1e9,1e9})continue;
       if(d[i][k]>=(pair<int,int>){1e9,1e9})continue;

       if(d[i][k].first+d[j][i].first==0&&d[i][k].second+d[j][i].second<=l)
       {
         nf=0;
         ns=d[j][i].second+d[i][k].second;
       }
       else
       {
         nf=d[j][i].first+d[i][k].first+1;
         ns=d[i][k].second;
       }
       d[j][k] = min(d[j][k],{nf,ns} );
     }
  int q;
  cin>>q;

  rep(i,q)
  {
    int a,b;
    cin>>a>>b;
    a--;b--;
    int res=d[a][b].first;
    if(res>=1e9)cout<<-1;
    else cout<<res;
    cout<<"\n";
  }
  cout<<endl;

}


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

int main() {
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; i < s.size(); i++)
    {
        int x = s[i] - 'A';
        x = (x + n) % 26;
        cout << (char)(x + 'A');
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

using namespace std;

int main()
{
    int x, y;

    cin >> x >> y;

    if (x == 2)
        x = 3;
    else if (x == 4 || x == 6 || x == 9 || x == 11)
        x = 2;
    else
        x = 1;

    if (y == 2)
        y = 3;
    else if (y == 4 || y == 6 || y == 9 || y == 11)
        y = 2;
    else
        y = 1;

    cout << (x == y ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
int getmin();


int main(){
    int N,K;
    cin >> N >> K;
    
    vector<int> h(N+2);
    for(int i=0;i<N;i++){
        cin >> h[i];
        //h[i] = 10000;
    }
    vector<int> dp(N+2);
    dp[0] = 0;
    dp[1] = abs(h[0]-h[1]);
    for(int i=2;i<N;i++){
        ll min = 100000000000;
        for(int j = 1;j<=K;j++){
            if(i>=j){
                if(min>dp[i-j]+abs(h[i]-h[i-j])){
                min=dp[i-j]+abs(h[i]-h[i-j]);
                }
            }
        }
        dp[i] = min;
    }
    
    cout << dp[N-1]<< endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int K = scan.nextInt();
		String S = scan.next();

		if(K < S.length()) {
			S = S.substring(0,K);
			System.out.print(S);
			System.out.println("...");
		} else {
			System.out.print(S);
		}
	}
}


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

int main(){
    int a, b;
    cin >> a >> b;
    int c = b-a;
    int sum = 0;
    for(int i = 1; i <= c; i++){
        sum += i;
    }
    int x = sum-b;
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


S = li()
maxs = 0
cnt = 0
diction = ['A', 'T', 'C', 'G']
for i in range(len(S)):
    if S[i] in diction:
        cnt += 1
    else:
        cnt = 0
    maxs = max(cnt, maxs)

print(maxs)


Measured memory_bytes: 3064
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

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

signed main(){
    FastIO;
    int s,w;
    cin>>s>>w;
    cout<<(w>=s?"unsafe":"safe");
    return 0;
}


Measured memory_bytes: 3668
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var line = Console.ReadLine().ToCharArray();
        var ans = 0;

        if (line[1] == 'R')
        {
            if (line[0] != 'R' && line[2] != 'R')
            {
                ans = 1;
            }
            else if (line[0] == 'R' && line[2] == 'R')
            {
                ans = 3;
            }
            else
            {
                ans = 2;
            }
        }
        else
        {
            if (line[0] == 'R' || line[2] == 'R')
            {
                ans = 1;
            }
            else
            {
                ans = 0;
            }
        }

        Console.WriteLine(ans);


        Console.ReadLine();
    }


}


Measured memory_bytes: 17596
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    n=parseInt(readline())
    a=parseMap(split(readline()))
    ans=0
    for i in 1:n
        if a[a[i]]==i
            ans+=1
        end
    end
    println(ans÷2)
end
main()

Measured memory_bytes: 168444
import bisect
import math
import sys
from collections import Counter, defaultdict, deque
from copy import copy, deepcopy
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from queue import Queue

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

inf = float("inf")


def main():
    N = int(input())
    S = input()
    ret = 0
    for i in range(1000):
        i = str(i).zfill(3)
        cursor = 0
        for s in S:
            if s == i[cursor]:
                cursor += 1
                if cursor == 3:
                    ret += 1
                    break
    print(ret)
        
      
if __name__=='__main__':
    main()

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

void testcase() {

}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> time;
	for (int i = 0; i < m; i++) {
		int cur;
		cin >> cur;
		time.push_back(cur);
	}
	for (int i = 0; i < m; i++) {
		n -= time[i];
	}
	if (n < 0)cout << "-1";
	else { cout << n; }


	return 0;
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
// scanf("%d %d %d %d",&w,&b,&d,&s); %lld
// printf("%d\n" ,points);
// const double PI=acos(-1);

int main(){
    ll n,d,rta=0,x,y;
    cin >> n >> d;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        if((x*x)+(y*y)<=(d*d)) rta++;
    }
    cout << rta << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)
vector<pair<ll,ll>> v[100500]; // [from].f1(to).f2(cost)
vector<ll> cost(100500,1e18);

bool dijkstra(ll st){
  
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> que;
 // vector<ll> cost(100500,1e18);
  cost[st]=0;

  que.push(mkpr(0,st));//(cost,node)
  while(!que.empty()){
    pair<ll,ll> p = que.top();
    que.pop();
    ll now = p.second;
    ll nc = p.first;
    //cout<<now<<" "<<nc<<endl;
    for(ll i=0;i<v[now].size();i++){
      if(cost[v[now][i].first]>nc+v[now][i].second){
        cost[v[now][i].first] = nc+v[now][i].second;
        que.push(mkpr(cost[v[now][i].first],v[now][i].first));
      }
    }
  }



}



int main(){

ll N,M;
cin>>N>>M;
ll tmp,tmp1,tmp2;
for(ll i=0;i<M;i++){
cin>>tmp>>tmp1>>tmp2;
tmp--;
tmp1--;
v[tmp].emplace_back(make_pair(tmp1,tmp2));
}

for(ll i=1;i<N;i++){
  v[i].emplace_back(make_pair(i-1,0));
}

dijkstra(0);

if(cost[N-1]==1e18){
  cout<<-1<<endl;
  return 0;
}

cout<<cost[N-1]<<endl;

  return 0;
}

Measured memory_bytes: 9468
(R,C,K),*t=[map(int,t.split())for t in open(0)]
G,*F=eval("eval('[0]*-~C,'*R),"*5)
for r,c,v in t:G[r-1][c]=v
for r in range(R):
 for x in 1,2,3:
  for c in range(C):F[x][r][c]=max(F[x-1][r][c],max(F[x-1][r][c-1],(x<2)*F[3][r-1][c])+G[r][c+1],F[x][r][c-1])
print(F[3][-1][-2])

Measured memory_bytes: 496052
import numpy as np

N = int(input())
X = np.array(list(map(int, input().split())))
best_score = None
for i in range(np.min(X), np.max(X)+1):
    score = np.sum(np.power(X - i, 2))
    if best_score is None:
        best_score = score
    elif best_score > score:
        best_score = score
print(best_score)

Measured memory_bytes: 12424
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        int X = sc.nextInt();
        int Y = sc.nextInt();
        
        if(N <= K){
            System.out.println(N*X);
        }else if(N > K){
            System.out.println(K*X + (N - K)*Y);
        }
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define number_of_digit(n) __builtin_ffs(n);
#define ll long long
#define T int
#define ld long double
inline void print(T n)
{
  if (n == 0)
  {
    putchar('0');
    putchar('\n');
  }
  else if (n == -1)
  {
    putchar('-');
    putchar('1');
    putchar('\n');
  }
  else
  {
    char buf[11];
    buf[10] = '\n';
    int i = 9;
    while (n)
    {
      buf[i--] = n % 10 + '0';
      n /= 10;
    }
    while (buf[i] != '\n')
      putchar(buf[++i]);
  }
}
int read()
{
       int cc = getc(stdin);
       for (;cc < '0' || cc > '9';)  cc = getc(stdin);
       int ret = 0;
       for (;cc >= '0' && cc <= '9';)
       {
          ret = ret * 10 + cc - '0';
          cc = getc(stdin);
       }
      return ret;
}
ll power(ll num,ll g)
{
  if(g==0)return 1;

  if(g%2==1)return (num*power((num*num),g/2));
  return power((num*num),g/2);
}
int main()
{
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int a,b,c;
  cin>>a>>b>>c;
  cout<<min(b/a,c)<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int w,h,x,y,n;
	double m;
	scanf("%d%d%d%d",&w,&h,&x,&y);
	m=double(w)*double(h)/2;
	if(x+x==w&&y+y==h)
	n=1;
	else
	n=0;
	printf("%lf %d\n",m,n);
	return 0;
}

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

#define EQ(a,b) (abs((a)-(b)) < EPS)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define sz size()
#define all(a) (a).begin(),(a).end()

using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef pair<D,int> pdi;

const D EPS = 1e-8;
const D PI = acos(-1);

inline D dot(P x, P y){return real(conj(x)*y);}
inline D cross(P x, P y){return imag(conj(x)*y);}

inline D seg_p_dis(L a,P x){
  if(dot(a.sc-a.fs,x-a.fs)<EPS)return abs(x-a.fs);
  if(dot(a.fs-a.sc,x-a.sc)<EPS)return abs(x-a.sc);
  return abs(cross(a.sc-a.fs,x-a.fs))/abs(a.sc-a.fs);
}

inline D seg_seg_dis(L a,L b){
  D res = 1e10;
  res = min(res,seg_p_dis(a,b.fs));
  res = min(res,seg_p_dis(a,b.sc));
  res = min(res,seg_p_dis(b,a.fs));
  res = min(res,seg_p_dis(b,a.sc));
  return res;
}

int main(){
  int w,n;
  while(cin >> w >> n){
    if(w==0)return 0;

    vector< vector<L> > l(n);
    rep(i,n){
      int m;
      cin >> m;
      vector<P> p(m);
      rep(j,m){
	int x,y;
	cin >> x >> y;
	p[j] = P(x,y);
      }
      rep(j,m){
	l[i].push_back(L(p[j],p[(j+1)%m]));
      }
    }

    int v = n+2;
    vector< vector<pdi> > g(v);
    g[v-2].pb(pdi(w,v-1));
    L ls = L(P(0,0),P(0,1e4)), lt = L(P(w,0),P(w,1e4));
    rep(i,n){
      D dis = w;
      for(L a : l[i])dis = min(dis, seg_seg_dis(ls,a));
      g[v-2].pb(pdi(dis, i));
      dis = w;
      for(L a : l[i])dis = min(dis, seg_seg_dis(lt,a));
      g[i].pb(pdi(dis,v-1));
      rep(j,i){
	dis = w;
	for(L a : l[i])for(L b : l[j]){
	    dis = min(dis, seg_seg_dis(a,b));
	  }
	g[i].pb(pdi(dis,j)); g[j].pb(pdi(dis,i));
      }
    }

    vector<D> d(v,1e9);
    d[v-2] = 0;
    bool use[220];
    memset(use,0,sizeof(use));

    for(;;){
      int u = -1;
      rep(i,v){
	if(!use[i] && (u<0 || d[u] > d[i]+EPS) )u = i;
      }
      if(u<0)break;
      use[u] = true;
      
      for(pdi nxt : g[u]){
	D ncost = d[u] + nxt.fs;
	if(!use[nxt.sc] && d[nxt.sc] > ncost +EPS){
	  d[nxt.sc] = ncost;
	}
      }
    }
    /*
    priority_queue<pdi, vector<pdi>, greater<pdi> > q;
    q.push(pdi(0,v-2));
    while(q.size()){
      pdi p = q.top(); q.pop();
      D cost = p.fs;
      int cur = p.sc;

      if(cur == v-1)break;
      if(d[cur]+EPS < cost)continue;

      for(pdi nxt : g[cur]){
	D ncost = cost + nxt.fs;
	int u = nxt.sc;
	if(d[u] > ncost + EPS){
	  d[u] = ncost;
	  q.push(pdi(ncost,u));
	}
      }
    }
    */
    cout << fixed << setprecision(9) << d[v-1] << endl;
  }
}

Measured memory_bytes: 2052
module ISet=Set.Make(struct type t=int let compare=compare end);;
Array.(Scanf.scanf" %d %d %d %d %d %d"@@fun a b c d e f->
	let w =
		init (f/a/100+1) (fun i->
			init (f/b/100+1) (fun j->j))
		|>
		fold_left (fun (i,s) ar->
			i+1,snd @@ fold_left (fun (j,s) v->
				let w = 100*a*i+100*b*j in
				j+1,if w<=f then ISet.add w s else s
			) (0,s) ar
		) (0,ISet.empty) |> snd |> ISet.elements |> of_list
	in let s = 
		init (f/c+1) (fun i->
			init (f/d+1) (fun j->j))
		|>
		fold_left (fun (i,s) ar->
			i+1,snd @@ fold_left (fun (j,s) v->
				let w = c*i+d*j in
				j+1,if w<=f then ISet.add w s else s
			) (0,s) ar
		) (0,ISet.empty) |> snd |> ISet.elements |> of_list
	in
	fold_left (fun (d,p,q) w->
		let d',w,s = fold_left (fun (d,p,q) s->
			if w+s>f || w/100*e<s || w+s=0 then (d,p,q)
			else let d'=100. *. (float s) /. (float w +. float s) in
			if d'>d then (d',w,s) else (d,p,q)
		) (d,p,q) s in
		if d'>d then (d',w,s) else (d,p,q)
	) (0.,100*a,0) w
	|> (fun (d,w,s)->Printf.printf "%d %d\n" (w+s) s))

Measured memory_bytes: 7168
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

import itertools
X = list(itertools.permutations(range(1,N+1),N))
for i in range(len(X)):
  x = X[i]
  if P == x:
    a = i 
  if Q == x:
    b = i

print(abs(a-b))

Measured memory_bytes: 8052
import os, sys, re, math

N = int(input())
flg = False
words = []
for _ in range(N):
    w = input()
    if w in words:
        flg = True
        break
    else:
        words.append(w)

prev = words[0]
cur = ''

if flg:
    print('No')
else:
    for i in range(1,len(words)):
        cur = words[i]
        if prev[-1] == cur[0]:
            prev = words[i]
        else:
            flg = True
            print('No')
            break
    if flg == False:
        print('Yes')


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int N;
bitset<10> a[111];
int b[111][11];
int ans=-2e9;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<10;j++){
            int x;
            cin>>x;
            a[i][j]=x;
        }
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<11;j++)
            cin>>b[i][j];
    for(int x=1;x<1024;x++){
        int y=0;
        for(int i=0;i<N;i++){
            auto z=bitset<10>(x)&a[i];
            y+=b[i][z.count()];
        }
        ans=max(ans,y);
    }
    cout<<ans;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(i*j==n){
        puts("Yes");
        return 0;
      }
    }
  }
  puts("No");
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        string aite = Reader.ReadLine();


        int aitePa = aite.Count(a => a == 'p');

        int ans = (aitePa * -1) + (aite.Length / 2);
        Console.WriteLine(ans);



    }


    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"


ggppgggpgg

";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 3160
use std::io::stdin;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let chars: Vec<char> = buf.trim()
        .chars()
        .map(|c| c.to_uppercase().nth(0).unwrap())
        .collect();
    println!("{}", chars.iter().collect::<String>());
}



Measured memory_bytes: 5036
import java.util.Scanner;

public class Main {

  private static int a, b, c, divisior_count;

  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    a = stdIn.nextInt();
    b = stdIn.nextInt();
    c = stdIn.nextInt();
    divisior_count = 0;

    for (int i = a; i <= b ; i++ ) {
      if (c % i == 0) {
        divisior_count++;
      }
    }
    System.out.println(divisior_count);
  }
}

Measured memory_bytes: 26228
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node *link;
struct node{
  int key;
  link le,ri,pa;
};
link head;

void insert(int a);
void inorder(link h);
void preorder(link h);

int main(){
  int m,k;
  char op[10];
  int i;

  head=NULL;
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%s",op);
    if(strcmp(op,"insert")==0){
      scanf("%d",&k);
      insert(k);
    }else if(strcmp(op,"print")==0){
      inorder(head);
      printf("\n");
      preorder(head);
      printf("\n");
    }
  }

  return 0;
}

void insert(int a){
  link x,y,z;
  z=malloc(sizeof(struct node));
  z->key=a; z->le=NULL; z->ri=NULL;
  y=NULL;  x=head;
  while(x!=NULL){
    y=x;
    if(z->key<x->key)   x=x->le;
    else                x=x->ri;
  }
  z->pa=y;

  if(y==NULL)             head=z;
  else if(z->key<y->key)  y->le=z;
  else                    y->ri=z;
}

void inorder(link h){
  if(h==NULL) return;
  inorder(h->le);
  printf(" %d",h->key);
  inorder(h->ri);
}

void preorder(link h){
  if(h==NULL) return;
  printf(" %d",h->key);
  preorder(h->le);
  preorder(h->ri);
}


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

typedef long long ll;
#define endl "\n"

map<string,int> verd;

int main(){
	// INT VS LL
    // freopen("input.txt", "r", stdin);
    //	INT VS LL
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    while (n--){
    	string s;
    	cin>>s;
    	verd[s]++;
    }
    for (string s2: {"AC", "WA", "TLE", "RE"}){
    	cout<<s2<<" x "<<verd[s2]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

int main() {
    // string c;
    char c[1300];
    // cin >> c;
    fgets(c, 1300, stdin);
    for(int i = 0; i < sizeof c; i++) {
        if(c[i] >= 'A' && c[i] <= 'Z') {
            c[i] += 32;
        }
        else if(c[i] >= 'a' && c[i] <= 'z') {
            c[i] -= 32;
        }
    }
    cout << c;

    return 0;
}


Measured memory_bytes: 3084
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

ll dp[100005][13];
// 下からi桁目まで見たときに、あまりがjであるような数

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

    string s;
    cin >> s;

    int n = s.size();
    fill(dp[0], dp[n + 1], 0);
    dp[0][0] = 1;

    ll tmp = 1;
    for (int i = 1; i <= n; i++) {
        char c = s[n - i];

        // もらうDP
        if (c == '?') {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 13; k++) {
                    int d = (k + tmp * j % 13) % 13;
                    dp[i][d] += dp[i - 1][k];
                    dp[i][d] %= MOD;
                }
            }
        } else {
            int j = c - '0';
            for (int k = 0; k < 13; k++) {
                int d = (k + tmp * j % 13) % 13;
                dp[i][d] += dp[i - 1][k];
                dp[i][d] %= MOD;
            }
        }

        tmp *= 10;
        tmp %= 13;
    }

    cout << dp[n][5] << "\n";
    return 0;
}

Measured memory_bytes: 10688
# Problem: https://atcoder.jp/contests/abc067/tasks/abc067_b
# Python 1st Try

import sys
# from collections import defaultdict
# import heapq,copy
# from collections import deque


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def solver(selectNum, barLongth):
    result = 0
    barLongth.sort(reverse=True)
    #   print("{}".format(barLongth))
    # algorithm
    j = 0
    while j < selectNum:
        result = result + barLongth[j]
        j = j + 1
    return result


if __name__ == "__main__":
    _, K = MI()  # Nは要らない
    LII = LI()
    print("{}".format(solver(K, LII)))


Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main(){
    int n;
    cin >> n;

    string s;
    cin >> s;

    int k=s.size();
    for(int i=0;i<k;i++){
        if(s[i]+n >'Z'){s[i] = s[i] + n - 26;}
        else{s[i] = s[i]+n;}
    }

    cout << s << endl;

    return 0;
}

Measured memory_bytes: 256
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const double COOLING_RATE=0.9999;
const double SCALE_FACTOR=0.0005;

double rnd(){
	const int INF=1e9;
	return (double)(rng()%INF)/INF;
}

int n;
ll c[26];
ll d[400][26];

ll calc(vector<int> &contest){
	ll last[26];
	
	memset(last,-1,sizeof(last));
	
	ll res=0;
	rep(x,0,n){
		res+=d[x][contest[x]];
		last[contest[x]]=x;
		
		rep(y,0,26) res-=c[y]*(x-last[y]);
	}
	
	return res;
}

//store curr best
ll best;
vector<int> ans;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	//freopen("sample2.in","r",stdin);
	
	auto begin_time=chrono::steady_clock::now().time_since_epoch().count();
	
	cin>>n;
	rep(x,0,26) cin>>c[x];
	
	rep(x,0,n){
		rep(y,0,26) cin>>d[x][y];
	}
	
	vector<int> curr;
	rep(x,0,n){
		curr.push_back(0);
	}
	
	ll val=calc(curr);
	
	best=val;
	ans=curr;
	
	double tempreture=1;
	
	while (chrono::steady_clock::now().time_since_epoch().count()-begin_time<1900000000){
		int idx=rng()%n;
		int type=curr[idx];
		
		curr[idx]=rng()%26;
	
		ll temp=calc(curr);
		if (temp>val || rnd()<exp((temp-val)*SCALE_FACTOR/tempreture)){
			val=temp;
			
			if (best<val){
				best=val;
				ans=curr;
			}
		}
		else{
			curr[idx]=type;
		}
		
		tempreture*=COOLING_RATE;
	} 
	
	//pls uncomment later
	rep(x,0,n) cout<<ans[x]+1<<endl;
	
	//cout<<"debug: "<<best<<endl;
}


Measured memory_bytes: 4388
import java.util.Scanner;


public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // 整数の入力
    int a = sc.nextInt();
    // スペース区切りの整数の入力
    int b = sc.nextInt();
    int c = sc.nextInt();

//    int ab = a + b;
//    int bc = b + c;
//    int ac = a+c;
//
//    int result = Math.min(ab, Math.min(bc , ac));

    int max = Math.max(a, Math.max(b, c));

    System.out.println(a + b + c - max);
  }
}


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

int main() {
  string S;
  cin >> S;
  
  int ans = 0;
  if(S == "SUN") ans = 7;
  if(S == "MON") ans = 6;
  if(S == "TUE") ans = 5;
  if(S == "WED") ans = 4;
  if(S == "THU") ans = 3;
  if(S == "FRI") ans = 2;
  if(S == "SAT") ans = 1;
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii > vii;
typedef vector<pll > vll;
#define pb push_back
#define mp make_pair 
#define mod 1000000007
#define F first
#define S second
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define For(i, a, b) for(__typeof (a) i=a; i<=b; i++)
#define inp_arr(a,n) for(__typeof (n) i=0; i<n; ++i) {cin>>a[i];}
#define debug_arr(a,n) {{for(__typeof (n) i=0; i<n; ++i) {cout<<a[i]<<" ";}cout<<"\n";}}
 
ll power(ll x, ll y) 
{ 
    ll res = 1;   
    while (y > 0) { 
        if (y & 1) 
            res = (res*x)%mod; 
        y = y>>1;
        x = (x*x)%mod; 
    } 
    return res%mod; 
}

ll P(ll a[], ll n, ll k) 
{  
    sort(a, a + n); 
    ll product = 1; 
   
    if (a[n - 1] == 0 && (k & 1)) 
        return 0; 
  
    if (a[n - 1] <= 0 && (k & 1)) { 
        for (int i = n - 1; i >= n - k; i--) 
            product = (product*a[i])%mod; 
        return product; 
    } 
  
    int i = 0; 
    int j = n - 1; 
    if (k & 1) { 
        product = (product*a[j])%mod; 
        j--; 
        k--; 
    } 

    k >>= 1; 
    for (int itr = 0; itr < k; itr++) { 
        ll left_product = (a[i] * a[i + 1]); 
        ll right_product = (a[j] * a[j - 1]); 
        // cout<<left_product<<" "<<right_product<<"\n";
        
        if (left_product > right_product) { 
            product = (product*(left_product%mod))%mod; 
            i += 2; 
        } 
        else { 
            product = (product * (right_product%mod))%mod; 
            j -= 2; 
        } 
    } 
  
    return product; 
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    // #ifndef ONLINE_JUDGE
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout); 
    // #endif

    ll n,k;
    cin>>n>>k;
    ll a[n];
    inp_arr(a,n);
    ll ans = P(a,n,k);
    ans += mod;
    ans = ans%mod;
    cout<<ans<<"\n";


    return 0;
}

Measured memory_bytes: 5228
{-# LANGUAGE BangPatterns, OverloadedStrings #-}

import Control.Monad
import Data.Array.Unboxed
import Data.Bits
import Data.Bool
import Data.Char
import Data.Coerce
import Data.Function
import Data.Int 
import Data.IORef
import Data.List
import Data.Maybe
import qualified Data.Map.Strict as M
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV
import qualified Data.ByteString.Char8 as BS

main :: IO ()
main = do
  (n, k) <- getIntPair
  ns <- getIntList
  forM_ (zipWith (<) ns (drop k ns)) (putStrLn . bool "No" "Yes")


-- Input

getInt :: IO Int
getInt = readLn
second :: (b -> c) -> (a, b) -> (a, c)
second f (a, b) = (a, f b)

readInt :: BS.ByteString -> Maybe (Int, BS.ByteString)
readInt = fmap (second BS.tail) . BS.readInt

getIntVec :: Int -> IO (V.Vector Int)
getIntVec n = V.unfoldrN n readInt <$> BS.getLine
 
getIntList :: IO [Int]
getIntList = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

getIntegerList :: IO [Integer]
getIntegerList = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

getIntPair :: IO (Int, Int)
getIntPair = do
  v <- getIntVec 2
  return (v V.! 0, v V.! 1)

-- Search

bisearch :: (Int -> Bool) -> (Int, Int) -> (Int, Int)
bisearch check = bis
  where
    bis (l, r)
      | l + 1 == r = (l, r)
      | check mid  = bis (mid, r)
      | otherwise  = bis (l, mid)
      where
        mid = l + (r - l) `div` 2

-- Modular Arithmetic
--
 
modulo :: Int64
modulo = 10^9+7
addMod, subMod, mulMod :: Int64 -> Int64 -> Int64
addMod !x !y | x + y >= modulo = x + y - modulo
             | otherwise = x + y
subMod !x !y | x >= y = x - y
             | otherwise = x - y + modulo
mulMod !x !y = (x * y) `rem` modulo

newtype N = N { unwrapN :: Int64 } deriving (Eq)
instance Show N where
  show (N x) = show x
instance Num N where
  (+) = coerce addMod
  (-) = coerce subMod
  (*) = coerce mulMod
  fromInteger n = N (fromInteger (n `mod` fromIntegral modulo))
  abs = undefined; signum = undefined
---
 
exEuclid :: (Eq a, Integral a) => a -> a -> (a, a, a)
exEuclid !f !g = loop 1 0 0 1 f g
  where loop !u0 !u1 !v0 !v1 !f 0 = (f, u0, v0)
        loop !u0 !u1 !v0 !v1 !f g =
          case divMod f g of
            (q,r) -> loop u1 (u0 - q * u1) v1 (v0 - q * v1) g r
 
recipM :: Int64 -> Int64
recipM !x = case exEuclid x modulo of
             (1,a,_) -> a `mod` modulo
             (-1,a,_) -> (-a) `mod` modulo
divM :: Int64 -> Int64 -> Int64
divM !x !y = x `mulMod` recipM y
 
instance Fractional N where
  (/) = coerce divM
  recip = coerce recipM
  fromRational = undefined

-- 組み合わせ
powerset :: [a] -> [[a]]  
powerset xs = filterM (\x -> [True, False]) xs


Measured memory_bytes: 27188
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.stream.IntStream;

public class Main {

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

	private void solve() throws IOException {
		try {
			//			solveA();
			solveB();
			//			 solveC();
			//			 solveD();
			//			 solveE();
			//			 solveF();
		} finally {
			if (in != null) {
				in.close();
			}
			if (out != null) {
				out.flush();
				out.close();
			}
		}

	}

	private void solveA() {

		Map<Integer, Integer> wk = IntStream.range(0, 3).collect(() -> new HashMap<Integer, Integer>(),
				(t, i) -> {
					t.merge(nextInt(), 1, (oldV, newV) -> oldV + newV);
				},
				(t, u) -> {
					t.putAll(u);
				});

		out.println(wk.size());
	}

	private void solveB() {
		long numN = nextLong();
		long numK = nextLong();

		long res = (long) numK * (long) Math.pow(numK - 1, numN - 1);

		out.println(res);
	}

	private void solveC() {
		int numN = nextInt();

		out.println("");
	}

	private void solveD() {
		int numN = nextInt();

		out.println("");
	}

	private void solveE() {
		int numN = nextInt();

		out.println("");
	}

	private void solveF() {
		int numN = nextInt();

		out.println("");
	}

	private final PrintWriter out = new PrintWriter(System.out);
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
}

Measured memory_bytes: 21328
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long 
#define IOS ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
#define SIZE 100005
 
int main()
{
	ll a,b , k;
	cin >> a >>b >> k;
	
	if(a <= k)
	{
		k-=a;
		b-=k;
		if(b < 0) b = 0;
		cout<< 0 << " " << b << endl;
	}
	else
	{
		cout << a-k << " " << b << endl;
	}
	return 0;
}

Measured memory_bytes: 256
A,B = gets.split.map(&:to_i)
U = Array.new
U[0] = A+B
U[1] = A-B
U[2] = A*B
max = -1000000000
for k in 0..2
 if max < U[k]
  max = U[k]
 end
end
puts(max)

Measured memory_bytes: 1788