akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <ctime>
#define INF 200000000
#define LINF 9000000000000000000
#define mod 1000000007
 
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=(n);i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define rsort(x) sort(all(x));reverse(all(x))
#define pb push_back
#define mp make_pair
#define MOD(x) (x%(mod))
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

bool debug=false;
/*---------------------------------------------------*/

int d[205][205];
vi R;

void init(){
  rep(i,205)rep(j,205)d[i][j]=INF;
}

void wf(){
  rep(k,205){
    rep(i,205){
      rep(j,205){
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	//cout<<d[i][j]<<endl;
      }
    }
  }
}

int dfs(int now,bool used[],int cnt,int cost){
  //cout<<cost<<endl;
  int calc=INF;
  if(cnt==R.size())return cost;
  rep(i,R.size()){
    if(d[now][R[i]]!=INF&&used[i]!=true){
      used[i]=true;
      calc=min(calc,dfs(R[i],used,cnt+1,cost+d[now][R[i]]));
      used[i]=false;
    }
  }
  return calc;
}

//------------------------------------------------------------
/*
int DEBUG_dfs(int now,bool used[],int cnt,int cost,vi v){
  cout<<cost<<endl;
  int calc=INF;
  if(cnt==R.size()){
    rep(i,v.size())cout<<v[i]<<" ";
    cout<<endl;
    return cost;
  }
  rep(i,R.size()){
    if(d[now][R[i]]!=INF&&used[i]!=true){
      used[i]=true;
      v.pb(R[i]);
      calc=min(calc,DEBUG_dfs(R[i],used,cnt+1,cost+d[now][R[i]],v));
      v.pop_back();
      used[i]=false;
    }
  }
  return calc;
}
*/
//-------------------------------------------------------------------

int main(){
  int n,m,r;
  int a,b,c;
  cin>>n>>m>>r;
  rep(i,r){
    int x;
    cin>>x;
    R.pb(x);
  }
  init();
  rep(i,m){
    cin>>a>>b>>c;
    d[a][b]=c;
    d[b][a]=c;
    //cout<<d[a][b]<<endl;
  }
  
  wf();
  //rep(i,R.size())rep(j,R.size())cout<<R[i]<<" "<<R[j]<<" -> "<<d[R[i]][R[j]]<<endl;
  int ans=INF;
  rep(i,R.size()){
    bool used[R.size()];
    rep(j,R.size())used[j]=false;
    used[i]=true;
    //vi v;
    //v.pb(R[i]);
    //ans=min(ans,DEBUG_dfs(R[i],used,1,0,v));
    ans=min(ans,dfs(R[i],used,1,0));
    //cout<<"ans: "<<ans<<endl;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 384
INT_MAX=10**30+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#=====================================================================
s=input()
t=input()
count=0
for i in range(len(s)):
    if s[i]!=t[i]:
        count+=1
print(count)


Measured memory_bytes: 67988
#include<iostream>

int main(void){
  int X;
  int N;
  std::cin >> N;
  //std::cout << (int)((N+1)/1.08) <<" " << (int)(N/1.08) << std::endl;
  if((int)((N)/1.08) == (N/1.08)){
    std::cout << (int)(N/1.08);
  }else{
    if((int)((int)((N+1)/1.08)*1.08) == N){
      std::cout << (int)((N+1)/1.08);
    }else{
      std::cout << ":(";
    }
  }
  return 0;
}


Measured memory_bytes: 888
c = [ list(map(int, input().split())) for _ in range(3)]
a = [0]
b = [c[0][0], c[0][1], c[0][2]]
a.append(c[1][0]-b[0])
a.append(c[2][0]-b[0])
ans = "Yes"
for i in range(3):
    for j in range(3):
        if c[i][j]==a[i]+b[j]:
            continue
        else:
            ans = "No"
print(ans)

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

int main(){
  int x1, x2, y1, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  int x = x2 - x1;
  int y = y2 - y1;
  int x3 = x2 - y;
  int y3 = y2 + x;
  int x4 = x1 - y;
  int y4 = y1 + x;
  cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
}


Measured memory_bytes: 256
n = int(input())
s = list(input())

count = 0
for i in range(1, len(s)):
    if s[i] == 'E':
        count += 1
minc = count
for i in range(1, len(s)):
    if s[i - 1] == 'W':
        count += 1
    if s[i] == 'E':
        count -= 1
    minc = min(minc, count)
print(minc)

Measured memory_bytes: 6048
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

long long int w[107];
long long int v[107];
long long int dp[107][100007];
int main()
{
    int N,W;
    scanf("%d %d\n",&N,&W);
    for(int i=1; i<=N; i++)
    {
        scanf("%lld %lld\n",&w[i],&v[i]);
    }

    for(int i=1;i<=N;i++)
    {
        for(int k=0;k<=W;k++)
        {
            if(k+w[i]<=W)
            {
                dp[i][k+w[i]]=max(dp[i-1][k]+v[i], dp[i][k+w[i]]);
            }
            dp[i][k]=max(dp[i-1][k], dp[i][k]);
        }
    }

    printf("%lld\n",dp[N][W]);
    return 0;
}

Measured memory_bytes: 79232
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	const tmp = input[0].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(tmp[0], 10);
	var b = parseInt(tmp[1], 10);
	var c = parseInt(tmp[2], 10);
	var k = parseInt(input[1], 10);

	var res = 'No';

	// けいさん
	for (let i = 0; i < k; i++) {
		if (a >= b) {
			b *= 2;
		} else {
			c *= 2;
		}
	}
	if (a < b && b < c) {
		res = 'Yes';
	}

	//出力
	console.log('%s', res);
}

// 実行 ファイル名により本番かどうか判断
if (__filename.match("Main.js$")) {
	Main(require("fs").readFileSync("/dev/stdin", "utf8"));
} else {
//	Main("3\n4 5\nhello\n");
	Main(require("fs").readFileSync("q2.txt", "utf8"));
}


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

using namespace std;

int main(){
    int n,p[100],sl=0,minn,maxx;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> p[i];
}
    for(int i=0;i<n-2;i++){
        minn=min(min(p[i],p[i+1]),p[i+2]);
        maxx=max(max(p[i],p[i+1]),p[i+2]);
       if(p[i+1]!=maxx && p[i+1]!=minn){
           sl++;
       } 
    }
    cout <<sl;
}

Measured memory_bytes: 256
n=gets.split(' ').map(&:to_i)
a=gets.split(' ').map(&:to_i)
loop do
  min=a.min
  mini=a.index(min)
  a.map!.with_index {|m, i| mini==i ? m : m % min}
  a.delete(0)
  break if a.size == 1
end

p a[0]


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

#[fastout]
fn main() {
    input! {
        n:usize
    }
    if n % 10 == 7 || (n / 10) % 10 == 7 || (n / 100) == 7 {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2164
INF = 10**13

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[INF]*100010 for _ in range(N+1)]

for i in range(N):
    for now_v in range(100010):
        if now_v - v[i] >= 0:
            dp[i+1][now_v] = min(dp[i][now_v], dp[i][now_v-v[i]]+w[i])
        else:
            dp[i+1][now_v] = min(dp[i][now_v], w[i])

for ans_v in range(100010):
    if dp[N][ans_v] > W:
        ans = ans_v
        break
print(ans)

Measured memory_bytes: 120812
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define reps(i,x) for(ll i=1;i<=(ll)(x);i++)
#define rrep(i,x) for(ll i=((ll)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(ll)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
int main() {
  string s;
  int k;
  cin >> s >> k;
  rep(i, k)
    if(s[i] != '1' || i == s.size() - 1){
      cout << s[i] << endl;
      return 0;
    }

  cout << 1 << endl;
}



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

const int maxn=2e5+5;
const int maxk=15;
const int mod=998244353;
#define ll long long

struct Edge
{
    int l,r;
    bool operator < (const Edge &B) const
    {
        if(l==B.l) return r<B.r;
        return l<B.l;
    }
}a[maxk],b[maxk];
int cnt;

struct Node
{
	int l,r;
	ll sum,lazy;
	Node *ls,*rs;
	
	Node(int L,int R)
	{
		l=L;r=R;
		sum=lazy=0;
		ls=rs=NULL;
	}
	
	void pushup(){if(l!=r) sum=(ls->sum+rs->sum)%mod;}
	void deal(ll val){sum+=val*(ll)(r-l+1),sum%=mod;}
	void pushdown()
	{
		if(!lazy) return;
		if(l!=r)
		{
			ls->deal(lazy);ls->lazy+=lazy,ls->lazy%=mod;
			rs->deal(lazy);rs->lazy+=lazy,rs->lazy%=mod;
		}
		lazy=0;
	}
	
	void add(int L,int R,ll val)
	{
		if(l==L && r==R)
		{
			deal(val);
			lazy+=val;
            lazy%=mod;
			return;
		}
		pushdown();
		int mid=(l+r)>>1;
		if(R<=mid) ls->add(L,R,val);
		else if(L>=mid+1) rs->add(L,R,val);
		else ls->add(L,mid,val),rs->add(mid+1,R,val);
		pushup();
	}
	
	ll query(int L,int R)
	{
		pushdown();
		if(l==L && r==R) return sum%mod;
		int mid=(l+r)>>1;
		if(R<=mid) return ls->query(L,R)%mod;
		if(L>=mid+1) return rs->query(L,R)%mod;
		return (ls->query(L,mid)+rs->query(mid+1,R))%mod;
	}
}*root;

Node *build(int l,int r)
{
	int mid=(l+r)>>1;
	Node *node=new Node(l,r);
	if(l!=r)
	{
		node->ls=build(l,mid);
		node->rs=build(mid+1,r);
	}
	else node->sum=0;
	node->pushup();
	return node;
}

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

    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++) cin>>a[i].l>>a[i].r;
    sort(a+1,a+k+1);
    int l=a[1].l,r=a[1].r;
    for(int i=2;i<=k;i++)
    {
        if(a[i].l<=r)
        {
            r=max(r,a[i].r);
            continue;
        }
        b[++cnt]=(Edge){l,r};
        l=a[i].l,r=a[i].r;
    }
    b[++cnt]=(Edge){l,r};

    root=build(1,n);
    root->add(1,1,1);
    for(int i=1;i<=n;i++)
    {
        ll res=root->query(i,i);
        for(int j=1;j<=cnt;j++)
        {
            if(i+b[j].l>n) continue;
            root->add(i+b[j].l,min(i+b[j].r,n),res);
        }
    }
    cout<<root->query(n,n);
    return 0;
}

Measured memory_bytes: 22364
#include<algorithm>//sort(all(変数),greater<型名>())で降順に、*max_element(all(変数))で最大値を獲得
#include<bits/stdc++.h>
#include<cmath>//切り上げceil(値)
#include<deque>
#include<iomanip>//setprecision(数字)
#include<iostream>
#include<list>
#include<map>
#include<numeric>
//xとyのgcdは__gcd(x,y),xとyのlcmは(x*y)/__gcd、accumulate(all(変数),0)で要素の全加算
#include<queue>//priority_queue<型名> 変数
#include<set>
#include<stack>
#include<string>
#include<vector>
#define rep(i,n)  for(ll i=0; i<n; i++)
#define rrep(i,n) for(ll i=n-1; 0<=i; i--)
#define vll vector<ll>
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF 1e18
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
  int n,X; cin >> n >> X;
  vi x(n); rep(i,n) cin >> x[i];
  x.push_back(X);
  sort(all(x));
  vi distance(n);
  rep(i,x.size()-1) distance[i] = x[i+1]-x[i];
  int ans = 1e10;
  if(distance.size() == 1){
    ans = distance[0];
  }else{
    rep(i,distance.size()-1){
      int a = distance[i];
      int b = distance[i+1];
      chmin(ans,__gcd(a,b));
    }
  }
  cout << ans;
}


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

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

    string s;
    cin >> s;

    int res = 0;

    for (int i=0;i<(int)s.length();i++){
    	res = (res * 10 + (s[i]-'0'))%9;
    }

    if (res%9==0)
    	cout<<"Yes\n";
    else
    	cout<<"No\n";

	//return 0;
}


Measured memory_bytes: 3740
//includes
#include<iostream>
#include<list>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#include<numeric>
#include<assert.h>
#include<cstring>
#include<unordered_map>
#include<bitset>


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

//macros and consts
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define FORE(i,a) for(auto &i : a)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define accm accumulate
#define Fi first
#define Se second
#define INF 1e9
#define llINF (1LL<<60)
#define mINF -1e9
#define mllINF -(1LL<<60)
#define endl "\n"
#define CONT continue
#define BRK break
#define modulo(n, m) (((n)%(m)+(m))%m)

//shorter types
using namespace std;
using ll = long long;
using vi = std::vector<int>;
using vc = std::vector<char>;
using vll = std::vector<long long>;
using vs = std::vector<string>;
using Mi = map<int,int>;
using Mll = map<ll,ll>;
using UMi = unordered_map<int,int>;
using UMll = unordered_map<ll,ll>;
using Pi = pair<int,int>;
using Pll = pair<ll,ll>;
using vPi = vector<Pi>;
using vPll = vector<Pll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using pqgi = priority_queue<int,vector<int>,greater<int>>;
using pqsi = priority_queue<int,vector<int>,less<int>>;
using pqgll = priority_queue<int,vector<int>,greater<int>>;
using pssll = priority_queue<int,vector<int>,less<int>>;
template<class T>
using vec = vector<T>;
#define int long long




//here begins your code
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  string S;
  int Q;
  cin >> S;
  cin >> Q;
  list<char> chars;
  for(char c : S){
    chars.push_back(c);
  }

  bool flipped = false;
  for(int i = 0; i < Q; i++){
    int op;
    cin >> op;
    if(op == 1){
      flipped = !flipped;
      continue;
    }
    else{
      int f;
      char c;
      cin >> f >> c;
      if(f == 1){
        if(!flipped){
          chars.push_front(c);
        }
        else{
          chars.push_back(c);
        }
      }
      else{
        if(!flipped){
          chars.push_back(c);
        }
        else{
          chars.push_front(c);
        }
      }
    }
  }
  if(!flipped){
    string ans;
    for(auto c : chars){
      ans += c;
    }
    cout << ans << endl;
  }
  else{
    string ans;
    for(auto c : chars){
      ans += c;
    }
    reverse(all(ans));
    cout << ans << endl;
  }
  //check types
  //do not eb if you resize
  //resize before you access by idx
  return 0;
} 

Measured memory_bytes: 10452
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 998244353
#define INF 1000000000

int main(){
  int N,M;
  cin>>N>>M;
  vector<int> X(N);
  for(int i=0;i<N;i++){
    cin>>X.at(i);
  }
  sort(X.begin(),X.end());

  vector<int> A(M,0);
  for(int i=0;i<N;i++){
    A.at(X.at(i)%M)++;
  }

  if(M%2==1){
    int ans=0;
    vector<int> count(M);
    ans+=A.at(0)/2;
    count.at(0)=A.at(0)%2;
    for(int i=1;i<=M/2;i++){
      int x=min(A.at(i),A.at(M-i));
      ans+=x;
      count.at(i)=A.at(i)-x;
      count.at(M-i)=A.at(M-i)-x;
    }

    int i=0;
    while(i<N-1){
      if(X.at(i)==X.at(i+1)){
        if(count.at(X.at(i)%M)>=2){
          count.at(X.at(i)%M)-=2;
          ans++;
          i++;
        }
      }
      i++;
    }
    cout<<ans<<endl;
  }else{
    int ans=0;
    vector<int> count(M);
    ans+=A.at(0)/2;
    count.at(0)=A.at(0)%2;
    for(int i=1;i<M/2;i++){
      int x=min(A.at(i),A.at(M-i));
      ans+=x;
      count.at(i)=A.at(i)-x;
      count.at(M-i)=A.at(M-i)-x;
    }
    ans+=A.at(M/2)/2;
    count.at(M/2)=A.at(M/2)%2;

    int i=0;
    while(i<N-1){
      if(X.at(i)==X.at(i+1)){
        if(count.at(X.at(i)%M)>=2){
          count.at(X.at(i)%M)-=2;
          ans++;
          i++;
        }
      }
      i++;
    }

    cout<<ans<<endl;
  }
}


Measured memory_bytes: 1408
#include <stdio.h>
#include <math.h>

void check(int a, int b, int c){
 int x,y,z;
 x=a*a;
 y=b*b;
 z=c*c;
 if(z==x+y|| x== y+z || y== z+x)printf("YES\n");
 else printf("NO\n");
} 




int main(void){
 int N,a,b,c;
 int i;

 scanf("%d",&N);
 for(i=0; i<N; i++){
   scanf("%d %d %d",&a,&b,&c);
   check(a,b,c);
 }

 return 0;
}

Measured memory_bytes: 580
n=int(input())
task=[list(map(int,input().split())) for _ in range(n)]
task.sort(key=lambda x: x[1])

deadline=0
now=0
for i in range(n):
    now += task[i][0]
    deadline = task[i][1]
    if now > deadline:
        print('No')
        exit()

print('Yes')


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

ll dp[3001][3001][3], a[3001][3001];

int main() {
    ll r,c,items, x , y, v, maxi = 0;
    cin >> r >> c >> items;
    while(items--) {
    	cin >> x >> y >> v;
    	x--, y--;
    	dp[x][y][0] = a[x][y] = v;
    }
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) {
        for(int k=0;k<3;k++) {
            if(j+1 < c) dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k]);
            if(j+1 < c && k > 0) dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k-1] + a[i][j+1]);
        }
        if(i+1 < r) dp[i+1][j][0] = dp[i+1][j][1] = dp[i+1][j][2] = max({dp[i][j][0], dp[i][j][1], dp[i][j][2]}) + a[i+1][j];
    }
    for(int k=0;k<3;k++) maxi=max(maxi,dp[r-1][c-1][k]);
    cout << maxi;
	return 0;
}

Measured memory_bytes: 284880
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
print(len(Counter([input() for i in range(N)])))


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

#define ll long long
#define all(x) (x).begin(), (x).end()
const long long INF = 1LL << 60;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //(i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

int mod10(int a) { return a % 10; }
int top(int a) {
    if (mod10(a) == 0) return a;
    return (a / 10 + 1) * 10;
}

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // int a, b, c, d, e;
    // cin >> a >> b >> c >> d >> e;

    // 入力
    int a[5];
    rep(i, 5) cin >> a[i];
    //余りを入れる
    int b[5];
    rep(i, 5) b[i] = mod10(a[i]);

    int j = 200;  //一つの商品の制約以上の数を番兵にする
                  // （問題文の制約より123を超える数値）
    //余りが一番低い数を検索
    rep(i, 5) {
        if (b[i] != 0) {
            j = min(j, b[i]);
        }
    }

    //余りの最小値が見つからなかったら10にセット
    if (j > 10) {
        j = 10;
    }
    int total = 0;
    rep(i, 5) { total += top(a[i]); }
    // 10を引いて、見つかった最小の余りjを足す。
    total = total - 10 + j;
    cout << total << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
const int INF = 1LL<<55;
int Max(int &a,int b){return a=max(a,b);}
int Min(int &a,int b){return a=min(a,b);}
vector<int> G[N];



signed main(){
  int n,m;
  cin>>n>>m;

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


  int ans = 0;  
  for(int pos:G[0])
    for(int nx:G[pos]) if(nx==n-1) ans = 1;
  cout<<(ans? "POSSIBLE":"IMPOSSIBLE")<<endl;
  
  return 0;
}


Measured memory_bytes: 12776
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pie;

#define L first
#define R second
#define MP make_pair
#define PB push_back

const int maxn = 2e3 + 100;
vector <int> v[maxn];
queue <int> qu;
bool visited[maxn];
int k, dp[maxn], cnt = 0;
pair <int, int> edg[maxn];

void bfs (int u, int w){
    visited[u] = 1;
    visited[w] = 1;
    qu.push(u);
    qu.push(w);
    dp[u] = 0;
    dp[w] = 0;
    while (!qu.empty()){
        u = qu.front();
        if (dp[u] <= k and u != 0)
            cnt ++;
        for (auto ver : v[u]){
            if (!visited[ver]){
                qu.push(ver);
                dp[ver] = dp[u] + 1;
                visited[ver] = 1;
            }
        }
        qu.pop();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n >> k;
    for (int i = 1; i < n; i++){
        int u, w;
        cin >> u >> w;
        edg[i] = {u, w};
        v[u].PB(w);
        v[w].PB(u);
    }
    int ans = 0;
    if (k % 2 == 0){
        k /= 2;
        for (int i = 1; i <= n; i++){
            bfs (i, 0);
            ans = max (ans, cnt);
            memset (dp, 63, sizeof dp);
            memset (visited, 0, sizeof visited);
            cnt = 0;
        }
    }
    else {
        k /= 2;
        for (int i = 1; i < n; i++){
            bfs (edg[i].L, edg[i].R);
            ans = max (ans, cnt);
            memset (dp, 63, sizeof dp);
            memset (visited, 0, sizeof visited);
            cnt = 0;
        }
    }
    cout << n - ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int inf = 1<<30;
const ll mod = 1000000007;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n; cin >> n;
  map<string,int> mp;
  rep(i,n) {
    string s; cin >> s;
    SORT(s);
    mp[s]++;
  }

  ll ans = 0;
  for (auto& p : mp) {
    int s = p.second;
    ans += (ll)s*(s-1)/2;
  }

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

Measured memory_bytes: 11136
#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 <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

// 2?¬????BIT
// Verified: JOI 10 ??¬??? Planetary Exploration
template <typename T>
struct zeroIndexedTwodimBIT{
private:
    vector< vector<T> > array;
    const int n;
    const int m;

public:
    // ?????????
    zeroIndexedTwodimBIT(int _n, int _m) : array(_n+1, vector<T>(_m+1, 0)), n(_n), m(_m) {}

    // (0, 0) ?????? (x, y) ?????§????´???????????±???????
    T sum(int x, int y) {
        T s = 0;
        for(int i=x; i>=0; i = (i&(i+1))-1)
            for(int j=y; j>=0; j = (j&(j+1))-1)
                s += array[i][j];
        return s;
    }

    // [(x1, y1), (x2, y2)]???????´??????????
    T sum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1);
    }

    // (x, y) ??? ????´? k ?????????
    void add(int x, int y, T k) {
        for(int i=x; i<n; i |= i+1)
            for(int j=y; j<m; j |= j+1)
                array[i][j] += k;
    }
};

signed main() {
    int m, n, k; cin >> m >> n >> k;
    zeroIndexedTwodimBIT<int> cntJ(m, n), cntO(m, n), cntI(m, n);
    rep(i,0,m) {
        string s; cin >> s;
        rep(j,0,n) {
            if(s[j] == 'J') cntJ.add(i, j, 1);
            if(s[j] == 'O') cntO.add(i, j, 1);
            if(s[j] == 'I') cntI.add(i, j, 1);
        }
    }
    rep(i,0,k) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;
        int ansJ = cntJ.sum(x1, y1, x2, y2);
        int ansO = cntO.sum(x1, y1, x2, y2);
        int ansI = cntI.sum(x1, y1, x2, y2);
        printf("%lld %lld %lld\n", ansJ, ansO, ansI);
    }
    return 0;
}

Measured memory_bytes: 26016
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
using namespace std;

int count(int n){
    int c=0;
    for(int i=1;i<=n;i++){
        if(n%i==0){c++;}
    }
    return c;
}


int main(){
    int n;
    cin>>n;
    int a;
    for(int i=1;;i++){
        if(count(i)==n){a=i; break;}
    }
    cout<<a<<endl;
    
    
    
    return 0;
}



Measured memory_bytes: 3112
#include <iostream>
using namespace std;
int main(){
    char SAO;
    int count[26]={0};
    while(cin >> SAO){
        if(isalpha(static_cast<unsigned char>(SAO))){
        if(SAO == 'A' ||SAO == 'a'){
            count[0]++;
        }
        if(SAO == 'B'||SAO=='b'){
            count[1]++;
        }
        if(SAO =='C'||SAO=='c'){
            count[2]++;
        }
        if(SAO=='D'||SAO=='d'){
            count[3]++;
        }
        if(SAO=='E'||SAO=='e'){
            count[4]++;
        }
        if(SAO=='F'||SAO=='f'){
            count[5]++;
        }
        if(SAO=='G'||SAO=='g'){
            count[6]++;
        }
        if(SAO=='H'||SAO=='h'){
            count[7]++;
        }
        if(SAO=='I'||SAO=='i'){
            count[8]++;
        }
        if(SAO=='J'||SAO=='j'){
            count[9]++;
        }
        if(SAO=='K'||SAO=='k'){
            count[10]++;
        }
        if(SAO=='L'||SAO=='l'){
            count[11]++;
        }
        if(SAO=='M'||SAO=='m'){
            count[12]++;
        }
        if(SAO=='N'||SAO=='n'){
            count[13]++;
        }
        if(SAO=='O'||SAO=='o'){
            count[14]++;
        }
        if(SAO=='P'||SAO=='p'){
            count[15]++;
        }
        if(SAO=='Q'||SAO=='q'){
            count[16]++;
        }
        if(SAO=='R'||SAO=='r'){
            count[17]++;
        }
        if(SAO=='S'||SAO=='s'){
            count[18]++;
        }
        if(SAO=='T'||SAO=='t'){
            count[19]++;
        }
        if(SAO=='U'||SAO=='u'){
            count[20]++;
        }
        if(SAO=='V'||SAO=='v'){
            count[21]++;
        }
        if(SAO=='W'||SAO=='w'){
            count[22]++;
        }
        if(SAO=='X'||SAO=='x'){
            count[23]++;
        }
        if(SAO=='Y'||SAO=='y'){
            count[24]++;
        }
        if(SAO=='Z'||SAO=='z'){
            count[25]++;
        }
    }
    }
    cout <<"a : "<<count[0]<<endl;
    cout <<"b : "<<count[1]<<endl;
    cout <<"c : "<<count[2]<<endl;
    cout <<"d : "<<count[3]<<endl;
    cout <<"e : "<<count[4]<<endl;
    cout <<"f : "<<count[5]<<endl;
    cout <<"g : "<<count[6]<<endl;
    cout <<"h : "<<count[7]<<endl;
    cout <<"i : "<<count[8]<<endl;
    cout <<"j : "<<count[9]<<endl;
    cout <<"k : "<<count[10]<<endl;
    cout <<"l : "<<count[11]<<endl;
    cout <<"m : "<<count[12]<<endl;
    cout <<"n : "<<count[13]<<endl;
    cout <<"o : "<<count[14]<<endl;
    cout <<"p : "<<count[15]<<endl;
    cout <<"q : "<<count[16]<<endl;
    cout <<"r : "<<count[17]<<endl;
    cout <<"s : "<<count[18]<<endl;
    cout <<"t : "<<count[19]<<endl;
    cout <<"u : "<<count[20]<<endl;
    cout <<"v : "<<count[21]<<endl;
    cout <<"w : "<<count[22]<<endl;
    cout <<"x : "<<count[23]<<endl;
    cout <<"y : "<<count[24]<<endl;
    cout <<"z : "<<count[25]<<endl;
}

Measured memory_bytes: 3092
from collections import deque
import sys
sys.setrecursionlimit(10**5)

H, W = map(int, input().split())
M = [["#" for _ in range(W+2)]]+[list("#"+input()+"#") for _ in range(H)]+[["#" for _ in range(W+2)]]
seen = deque((1, 1)) #x, y
q = deque([(1, 1, 0)]) #x, y, d
depth = -1
goal = False
wall = 0
for m in M[1:H+1]:
  for b in m[1:W+1]:
    if b == "#":
      wall += 1
while q:
  x, y, d = q.popleft()
  if x == W and y == H:
    depth = d
    goal = True
    break
  for dx, dy in zip((0, 0, -1, 1), (1, -1, 0, 0)):
    if M[y+dy][x+dx] != "#" and not (x+dx, y+dy) in seen:
      seen.append((x+dx, y+dy))
      q.append((x+dx, y+dy, d+1))

if goal:
  print(W*H-wall-(depth+1))
else:
  print(-1)

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

int main(){
    long long int n, x;
    cin >> n >> x;

    vector<long long int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    long long int total = 0;
    for(int i=0; i<n; i++){
        total += a[i];
        if(total == x){
            cout << i+1 << endl;
            return 0;
        }
        else if(total > x){
            cout << i << endl;
            return 0;
        }
    }
    cout << n-1 << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,n) for(int i=1; i<=(n); i++)

int main() {
	int h,w;
    cin>>h>>w;
    vector<string> grid(h);
    for(int i=0; i<h; i++){
        cin>>grid[i];
    }
    
    vector<vector<int>> dist(h+1,vector<int>(w+1,5000));
    dist[1][1]=0;
    //距離定義
    
    int chgL,chgU;
    //距離決定時の色変更分
    
    while(dist[h][w]>4000){ //ゴール探索するまでor200times
        rep2(i,h){
            rep2(j,w){ //各マスについて
                if(dist[i][j]>4000&&(dist[i][j-1]<4000||dist[i-1][j]<4000)){
                    //最前線判定
                    
                    chgL=0;
                    chgU=0;
                    if(j>1){
                        if(grid[i-1][j-1]!=grid[i-1][j-2])chgL=1;
                    }
                    if(i>1){
                        if(grid[i-1][j-1]!=grid[i-2][j-1])chgU=1;
                    }
                    dist[i][j]=min(dist[i][j-1]+chgL,dist[i-1][j]+chgU);
                    
                }
            }
        }
        
    }
    int a=dist[h][w];
    if(grid[0][0]=='.')cout<<(a+1)/2;
    else cout<<(a/2+1);
	return 0;
}

Measured memory_bytes: 256
N,M=gets.split.map &:to_i
S=N.times.map{gets.split.map &:to_i}
C=M.times.map{gets.split.map &:to_i}
puts S.map{|a,b|
  r=-1
  e=10**9
  M.times do |i|
    c,d=C[i]
    f=(a-c).abs+(b-d).abs
    next if e <= f
    e=f
    r=i
  end
  r+1
}


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

int main() {
  int N, M,K;
 cin >> N >> M;
 K = N+M;
 if (N > 8){
     cout << ":(";
 }
 else if(M > 8){
     cout << ":(";
 }
 else if (K > 16){
     cout << ":(";
 }
 else{
     cout << "Yay!";
 }
}

Measured memory_bytes: 256
n, *h = map(int, open(0).read().split())

cnt = min(h)
vector = [cnt] * n
flg = False

for i in range(100):
    pre = -2
    for j in range(n):
        
        if vector[j] < h[j]:
            vector[j] += 1
            pre = j
            if pre == n - 1:
                cnt += 1
        else:
            if pre == j - 1:
                cnt += 1

print(cnt)

Measured memory_bytes: 3064
#include <iostream>
#include<vector>
#include<map>
using namespace std;

int main() {
	long long h,w,n;cin>>h>>w>>n;
	vector<long long> a(n),b(n);
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
	}
//	vector<map<long long,long long>> v;
//	for(int i=0;i<=h;i++){
//		map<long long,long long> m;
//		v.push_back(m);
//	}
	map<long long,map<long long,long long>> v;
	vector<long long> ans(10,0);
	ans[0]=(w-2)*(h-2);
	for(int i=0;i<n;i++){
		for(int j=-1;j<=1;j++){
			for(int k=-1;k<=1;k++){
				long long t=a[i]+j;
				long long y=b[i]+k;
//				cout<<t<<' '<<y<<endl;
				if((t>=2)*(t<=h-1)*(y>=2)*(y<=w-1)){
					ans[v[t][y]]--;
					ans[v[t][y]+1]++;
					v[t][y]++;
				}
			}
		}
	}
	for(int i=0;i<=9;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}


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

int main() {

  int a, b;
  char op;
  int ans;
  
  int stop = 0;
  while ( stop == 0 ) {
    cin >> a >> op >> b;
    if (op == '+') {
      ans = a + b;
    } else if (op == '-') {
      ans = a - b;
    } else if (op == '*') {
	  ans = a * b;
    } else if (op == '/') {
	  ans = a / b;
    } else {
      stop = 1;
      break;
    }
    cout << ans << endl;
  }
  
  
  
  return 0;
}


Measured memory_bytes: 3088
import java.util.Arrays;
import java.util.Scanner;

public class Main{

	static Scanner s=new Scanner(System.in);

	public static void main(String __[]){
		while(true) {
			input();
			if(in.charAt(0)=='0') return;
			solve();
		}
	}

	static String in;
	private static void input(){
		in=s.next();
	}

	private static void solve(){
		int[] x=new int[in.length()];
		for(int i=0;i<in.length();i++)
			x[i]=in.charAt(i)-'0';
		System.out.println(Arrays.stream(x).parallel().sum());
	}
}

Measured memory_bytes: 33844
sentence = []
cnt = -1
h = 0
for string in iter(input, "-"):
    cnt += 1
    if cnt == 0:
        w = str(string)
    elif cnt == 1:
        h = int(string)
        h_cnt = 1
    elif h_cnt == h:
        to_move = w[:int(string)]
        w = w[int(string):] + str(to_move)
        print(w)
        cnt = -1
    else:
        to_move = w[:int(string)]
        w = w[int(string):] + str(to_move)
        h_cnt += 1


Measured memory_bytes: 5600
using System;
using System.Linq;

namespace _20190315_03 {
    class Program {
        static void Main(string[] args) {
            Console.ReadLine();
            var line = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).OrderByDescending(x => x).ToArray();
            var longest = line[0];
            var sum = line.Skip(1).Sum();
            if (longest < sum) {
                Console.WriteLine("Yes");
            } else {
                Console.WriteLine("No");
            }
        }
    }
}


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

int main() {
    int n, result = 0, prev, count = 1;
    cin >> n >> prev;
    for (int a; cin >> a; ) {
        if (a == prev) {
            count++;
        } else {
            result += count / 2;
            count = 1;
        }
        prev = a;
    }
    result += count / 2;
    cout << result;
    return 0;
}

Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main{
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		while (true){
			int n = Integer.valueOf(sc.nextLine());
			if(n == 0) break;
			Map<Character, Character> map = new TreeMap<>();
			for(int i = 0; i < n; i++){
				String line = sc.nextLine();
				char from = line.charAt(0);
				char to = line.charAt(2);
				map.put(from, to);
			}
			StringBuilder builder = new StringBuilder();
			int m = Integer.valueOf(sc.nextLine());
			for(int i = 0; i < m; i++){
				char in = sc.nextLine().charAt(0);
				builder.append(map.getOrDefault(in, in));
			}
			System.out.println(builder.toString());
		}
		sc.close();
	}
}

Measured memory_bytes: 154336
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
    int N;
    while(cin >> N){
	int x = 0,r = 1;
	for(int i = 0,j = 0 ; i < N ; i++,j++){
	    if(j == 2){ r *= 3; j = 0; }
	    x += r;
	}
	cout << x << endl;
    }
    return 0;
}

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

int f[1069][1069][2],da[1069][1069],w,h,a[1069][1069];
int cal(int x,int y,int turn){
    if (f[x][y][turn]!=-1)return f[x][y][turn];
    if (x>=w) return 0;
        int re;
    if (turn==0){
        re=-1e9;
        if (y+1<=h) re=max(re,cal(x,y+1,1-turn));
        re=max(re,cal(x+1,y,1-turn)-da[x+1][h]+2*da[x+1][y]);
    }
    else { re=1e9;
        if (y+1<=h) re=min(re,cal(x,y+1,1-turn));
        re=min(re,cal(x+1,y,1-turn)-da[x+1][h]+2*da[x+1][y]);

    }
    return f[x][y][turn]=re;
}
int main(){
    scanf("%d%d",&w,&h);
    for (int i=1;i<=h;i++)
        for (int j=1;j<=w;j++) scanf("%d",&a[j][i]);
    for (int i=1;i<=w;i++)
        for (int j=1;j<=h;j++) da[i][j]=da[i][j-1]+a[i][j];
    memset(f,-1,sizeof(f));
    cout<<abs(cal(0,0,0))<<endl;
}



Measured memory_bytes: 20564
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const long double EPS = 1e-10;

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  s += '0';
  char c = s[0];
  int ans = 0;
  rep(i, n + 1) {
    if (s[i] != c) {
      ans++;
      c = s[i];
    }
  }
  cout << ans << endl;

  
  return 0;
}

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

int main() {
    string S;
    cin >> S;
    string alphabets = "abcdefghijklmnopqrstuvwxyz";
    set<char> data;
    for (char s : S) {
        data.insert(s);
    }
    string ans = "None";
    for (char alphabet : alphabets) {
        if (data.count(alphabet) == 0) {
            ans = alphabet;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 512
n, a, b = map(int, input().split())

if n == b and abs(a - b) == 1:
    print('Borys')
elif abs(a - b) % 2 == 0:
    print('Alice')
elif abs(a - b) % 2 != 0:
    print('Borys')
else:
    print('Draw')

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <iomanip>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define All(v) (v).begin(),(v).end()
typedef long long ll;

ll ceildiv(ll a,ll b){
    if(a%b)return a/b+1;
    else return a/b;
}

int main(){
    int N;cin >> N;
    vector<int> T(N),A(N);
    rep(i,N)cin >> T[i] >> A[i];
    ll tak=T[0],ao=A[0];
    for(int i=1;i<N;i++){
        ll j=max(ceildiv(tak,T[i]),ceildiv(ao,A[i]));
        tak=T[i]*j;
        ao=A[i]*j;
    }
    cout << tak+ao << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M, K = map(int, readline().split())
MOD = 998244353

def solve():
    m1pows = [1 for i in range(K + 1)]
    m1pows[0] = M * pow(M - 1, N - 1 - K, MOD) % MOD
    for i in range(1, K + 1):
        m1pows[i] = m1pows[i - 1] * (M - 1) % MOD
    cs = 1
    ans = 0
    for i in range(K + 1):
        ans += cs * m1pows[K - i]
        ans %= MOD
        cs *= (N - 1 - i) * pow(i + 1, MOD - 2, MOD)
        cs %= MOD
    return ans


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 80932
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
//const int MOD = (int) 1e9 + 7;
const int MOD = 119 << 23 | 1;
const int FFTMOD = 119 << 23 | 1;
const int INF = (int) 1e9 + 23111992;
const ll LINF = (ll) 1e18 + 23111992;
const ld PI = acos((ld) -1);
const ld EPS = 1e-6;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ull isqrt(ull k) {ull r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int mrand() {return abs((int) mt());}
inline int mrand(int k) {return abs((int) mt()) % k;}
#define db(x) cerr << "[" << #x << ": " << (x) << "] ";
#define endln cerr << "\n";

void chemthan() {
    double x; cin >> x;
    cout << prec(9) << pow(x / 3, 3) << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 384
from collections import defaultdict
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def sieve(n):
    res = [i for i in range(n)]
    for i in range(2, int(n**.5)+1):
        if res[i] < i:
            continue
        for j in range(i**2, n, i):
            if res[j] == j:
                res[j] = i
    return res


U = 10**6+1
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(lambda: 0)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


pf = defaultdict(lambda: 0)

for a in A:
    for p, q in prime_factor(a).items():
        if pf[p] < q:
            pf[p] = q

x = 1
for p, q in pf.items():
    x *= pow(p, q, MOD)
x %= MOD

print(sum(x*pow(a, MOD-2, MOD) for a in A) % MOD)

Measured memory_bytes: 44148
#include <cstdio>
#include <vector>
#include <algorithm>
#define abs std::abs
#define minf std::min
#define maxf std::max
typedef long long ll;
typedef long double ld;

int N;
int t, nt;
int x, y;
int nx, ny;

int main() {
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i) {
        scanf("%d%d%d", &nt, &nx, &ny); 

        t += abs(x - nx) + abs(y - ny);
        // printf("T = %d\n", t);
        if(t > nt) {
            printf("No\n");
            return 0;
        }

        if(t < nt && ((abs(t - nt) % 2) == 1)) {
            printf("No\n");
            return 0;
        }
        
        x = nx;
        y = ny;
    } 

    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int inf = 1e9;
#define rep(i, n) for (int i = 0; i < n; i++)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dxx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dyy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

const int MAX = 100;
int cost[MAX][MAX];
int n;

void dijkstra() {
    int d[n];
    bool seen[n] = {};
    rep (i, n) { d[i] = inf; }
    d[0] = 0;
    while (1) {
        int minc = inf, now;
        rep (i, n) {
            if (minc > d[i] && !seen[i]) {
                minc = d[i];
                now = i;
            }
        }
        seen[now] = 1;
        if (minc == inf) break;
        rep (i, n) {
            if (cost[now][i] != inf && !seen[i]) {
                if (d[i] > cost[now][i] + d[now]) {
                    d[i] = cost[now][i] + d[now];
                }
            }
        }
    }
    rep (i, n) { cout << i << " " << d[i] << "\n"; }
    return;
}

int main() {
    cin >> n;
    rep (i, n) rep (j, n) cost[i][j] = inf;
    rep (i, n) {
        int now, k, next, c;
        cin >> now >> k;
        rep (i, k) {
            cin >> next >> c;
            cost[now][next] = c;
        }
    }
    dijkstra();
}


Measured memory_bytes: 3120
# coding: utf-8
# Your code here!
import sys
lines = sys.stdin.read()
line= str.lower(lines)
line2=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

for i in line2:
    print(str(i)+" : "+str(line.count(i)))


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

int main() {
    int n;
    cin >> n;
    if(n % 10 == 3){
        cout << "bon";
    }else if(n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8 ){
        cout << "pon";
    }else{
        cout << "hon";
    }
}

Measured memory_bytes: 3652
#include <stdio.h>

int
main(int argc, char *argv[])
{
  int n, a[200];
  scanf("%d", &n);
  for(int i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }
  
  int min = 1000000000;
  int max = 1;
  for(int i = 0; i < n; i++){
    if(min > a[i]) min = a[i];
    if(max < a[i]) max = a[i];
  }
  
  printf("%d\n", max - min);
  
  return 0;
}

Measured memory_bytes: 128
class Dice:
    def __init__(self):
        self.faces=[]

    def rotate(self, direction):
        tmp = self.faces.copy()

        if direction =="N":
            self.faces[5-1] = tmp[1-1]
            self.faces[1-1] = tmp[2-1]
            self.faces[2-1] = tmp[6-1]
            self.faces[6-1] = tmp[5-1]
        if direction =="S":
            self.faces[5-1] = tmp[6-1]
            self.faces[1-1] = tmp[5-1]
            self.faces[2-1] = tmp[1-1]
            self.faces[6-1] = tmp[2-1]
        if direction =="W":
            self.faces[4-1] = tmp[1-1]
            self.faces[1-1] = tmp[3-1]
            self.faces[3-1] = tmp[6-1]
            self.faces[6-1] = tmp[4-1]
        if direction =="E":
            self.faces[3-1] = tmp[1-1]
            self.faces[1-1] = tmp[4-1]
            self.faces[4-1] = tmp[6-1]
            self.faces[6-1] = tmp[3-1]
        return 0

    def spin(self):
        self.faces[4-1], self.faces[2-1],self.faces[5-1],self.faces[3-1] =\
        self.faces[2-1], self.faces[3-1],self.faces[4-1],self.faces[5-1]

        return 0

dices = []
lines = int(input())
for i in range(lines):
    dices.append(Dice())
    dices[i].faces=[int(x) for x in input().split(" ")]

for i, d1 in enumerate(dices):
    for d2 in dices[i+1 :]:
        for _ in range(3):
            for _ in range(4):
                for ___ in range(4):
                    #print("d1: {}".format(d1.faces))
                    #print("d2: {}".format(d2.faces))
                    if d1.faces == d2.faces:
                        print("No")
                        exit()
                    d2.spin()
                d2.rotate("W")
            d2.rotate("N")

print("Yes")

Measured memory_bytes: 7824