Submission #774377

#	Time	Username	Problem	Language	Result	Execution time	Memory
774377		CyberCow	Virus Experiment (JOI19_virus)	C++17	14 / 100	42 ms	9696 KiB

virus

//#include <bits/stdc++.h>
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);
const int N = 5005;
int aj[805][805];
int dz[805][805];
int a[805][805];

void solve()
{
    int n, i, j, x, y, r, m, k;
    cin >> k >> n >> m;
    char c;
    string s;
    cin >> s;
    string ss = s + s + s;
    map<char, int> tarb;
    for ( i = 0; i < s.size(); i++)
    {
        tarb[s[i]] = 1;
    }
    int qw = 0, qe = 0, tip = 0, qan = 0;
    if (ss[0] == 'E')
        tip = 1;
    for ( i = 0; i < ss.size(); i++)
    {
        if((tip == 0 && ss[i] == 'E'))
        {
            qw = max(qw, qan);
            qan = 1;
            tip = 1;
        }
        else if ((tip == 1 && ss[i] == 'W'))
        {
            qe = max(qe, qan);
            qan = 1;
            tip = 0;
        }
        else
        {
            qan++;
        }
    }
    if (tarb.size() == 1)
    {
        if (s[0] == 'E')
        {
            qe = 1e9;
            qw = 0;
        }
        else
        {
            qe = 0;
            qw = 1e9;
        }
    }
    for ( i = 1; i <= n; i++)
    {
        for ( j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    for ( i = 1; i <= n; i++)
    {
        for ( j = 2; j <= m; j++)
        {
            if (a[i][j - 1] != 0 && a[i][j - 1] <= qe)
            {
                dz[i][j] = dz[i][j - 1] + 1;
            }
        }
        for ( j = m - 1; j > 0; j--)
        {
            if (a[i][j + 1] != 0 && a[i][j + 1] <= qw)
            {
                aj[i][j] = aj[i][j + 1] + 1;
            }
        }
    }
    int ans = 1e9;
    for ( i = 1; i <= n; i++)
    {
        for (j = 1; j <= m; j++)
        {
            if (a[i][j] != 0)
                ans = min(ans, dz[i][j] + aj[i][j] + 1);
        }
    }
    int qq = 0;
    for ( i = 1; i <= n ; i++)
    {
        for ( j = 1; j <= m; j++)
        {
            if (a[i][j] != 0 && dz[i][j] + aj[i][j] + 1 == ans)
                qq++;
        }
    }
    cout << ans << '\n' << qq;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

virus.cpp: In function 'void solve()':
virus.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for ( i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
virus.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for ( i = 0; i < ss.size(); i++)
      |                  ~~^~~~~~~~~~~
virus.cpp:35:18: warning: unused variable 'x' [-Wunused-variable]
   35 |     int n, i, j, x, y, r, m, k;
      |                  ^
virus.cpp:35:21: warning: unused variable 'y' [-Wunused-variable]
   35 |     int n, i, j, x, y, r, m, k;
      |                     ^
virus.cpp:35:24: warning: unused variable 'r' [-Wunused-variable]
   35 |     int n, i, j, x, y, r, m, k;
      |                        ^
virus.cpp:37:10: warning: unused variable 'c' [-Wunused-variable]
   37 |     char c;
      |          ^

• Subtask 1: 14 / 14
• Subtask 2: 0 / 6
• Subtask 3: 0 / 80